Graphs & paths

Bonjour, et bienvenue dans cette leçon ! Aujourd’hui, nous allons introduire quelques définitions de base liées aux graphes.

Définitions de base

La théorie des graphes est probablement l’un des sous-domaines les plus courants des mathématiques discrètes. Les graphes sont des structures mathématiques utilisées pour représenter les relations entre objets.

Mathématiquement, un graphe est composé d’un ensemble fini de sommets, $V$, et d’un ensemble d’arêtes, $E$. On peut donc désigner un graphe par un couple $G = (V, E)$ composé de $V$ et $E$.

Un graphe est souvent représenté par des cercles pour les sommets et des lignes pour les arêtes.

Quelques exemples : les graphes peuvent être utilisés pour représenter les relations entre membres d'une famille dans un arbre généalogique, où les membres seraient représentés comme des sommets et leurs relations comme des arêtes...

Ou, de manière similaire, pour représenter les interactions moléculaires dans un organisme biologique...

Ou, les réseaux neuronaux dans le cerveau...

Les hyperliens entre sites web...

Ou, simplement, un labyrinthe, où les cellules peuvent être représentées comme des sommets, et les cellules adjacentes non séparées par un mur peuvent être reliées par des arêtes.

C’est exact. Il existe plusieurs façons de définir les graphes. Dans le cas le plus simple, les arêtes indiquent quelles paires de sommets sont connectées, et lesquelles ne le sont pas. Cela signifie que $E$ devient un ensemble de paires de sommets.

Une paire $\{u,v\}$ est un ensemble non ordonné contenant deux éléments distincts, $u$ et $v$. Étant donné qu'ils ne sont pas ordonnés, les paires $\{u,v\}$ et $\{v,u\}$ sont identiques.

L'ordre d'un graphe est le nombre de sommets qu'il contient, ici 7 dans l'exemple.

La taille du graphe est le nombre d'arêtes, qui est 9 dans cet exemple.

Comme vous pouvez le voir, c’est une manière simple et efficace de visualiser un graphe.

Mais cela peut aussi être trompeur, car la création d’une figure comme celle-ci nécessite de prendre des décisions arbitraires sur les coordonnées des sommets et la forme des lignes.

Cela peut être vu dans la figure suivante, qui montre deux graphes qui semblent différents. Cependant, ces deux graphes sont identiques dans le sens où ils ont exactement le même ensemble de sommets et le même ensemble d'arêtes.

Les graphes ont été introduits pour la première fois par Euler en 1736.

Il s'intéressait à prouver formellement que personne ne pouvait parcourir la ville de Königsberg en traversant chacun de ses ponts exactement une fois. Pour le prouver, il a montré que commencer et finir au même point nécessiterait que le graphe contienne 0 ou 2 masses terrestres avec un nombre impair de ponts. Comme les masses terrestres de Königsberg contenaient toutes un nombre impair de ponts, ce parcours était impossible.

Dans certains cas, les arêtes peuvent être orientées, ce qui signifie qu’un sommet $u$ peut être connecté à un sommet $v$, même si $v$ n’est pas connecté à $u$. Dans ces cas, les arêtes sont constituées de couples de sommets, tels que, par exemple, $(u,v)$.

Les couples sont plus informatifs que les paires car l’ordre des sommets dans le couple a un sens.

Par exemple, le couple $(u,v)$ est distinct du couple $(v,u)$ si $u$ et $v$ sont eux-mêmes distincts, tandis que la paire $\{u,v\}$ et la paire $\{v,u\}$ sont identiques. Lorsqu'on utilise des couples, les graphes sont appelés digraphes. Nous ne considérerons dans ce cours que des graphes dont les arêtes sont des paires, mais il est utile de noter que les algorithmes présentés ici s'appliquent aussi aux digraphes.

La matrice d’adjacence et les graphes pondérés

Comme dans les exemples précédents, il est préférable d'indexer les sommets de 1 à $n$, qui est l'ordre du graphe. Lorsque les sommets du graphe sont indexés de manière appropriée, une autre façon de représenter un graphe est d'utiliser une matrice.

La matrice d'adjacence d'un graphe est une matrice ayant autant de lignes et de colonnes que l'ordre du graphe. La matrice d'adjacence est construite en mettant un 1 à la ligne $i$ et à la colonne $j$ si $\{i,j\}$ est une arête, et un 0 sinon. Voici un exemple de graphe et sa matrice d'adjacence correspondante.

Vous devez noter que la matrice d’adjacence d’un graphe est toujours symétrique.

Les matrices d’adjacence peuvent être généralisées pour prendre des valeurs autres que 0 et 1, ce qui permet de définir des graphes pondérés.

Les graphes pondérés sont particulièrement utiles lorsque les arêtes représentent des distances ou des délais entre sommets, car les valeurs dans la matrice d’adjacence peuvent être utilisées pour indiquer ces quantités.

Pour prendre un exemple, un graphe pondéré peut modéliser les distances entre les grandes villes des États-Unis, et les poids des connexions peuvent être utilisés pour représenter ces distances. En plus des distances, les poids peuvent représenter des occurrences, des proximités, des relations, etc.

Chemins et distances géodésiques

Un chemin est une séquence ordonnée d'arêtes distinctes, obtenue à partir d'une séquence de sommets en joignant chaque paire de sommets consécutifs par l'arête correspondante. Les deux sommets extrêmes de la séquence sont appelés les extrémités du chemin.

Regardez ce graphe. Dans cet exemple, $(\{v_1,v_2\}, \{v_2,v_6\}, \{v_4,v_6\}, \{v_3,v_4\})$ est un chemin, obtenu à partir de la séquence de sommets $(v_1,v_2,v_6,v_4,v_3)$.

Les chemins sont souvent confondus avec les marches. Une marche est une séquence de sommets telle que chaque paire de sommets consécutifs forme une arête dans le graphe. La différence est que, dans un chemin, une arête ne peut pas apparaître deux fois.

Par exemple, $(v_1, v_2, v_4, v_2)$ dans le graphe précédent est une marche, mais la séquence correspondante $(\{v_1,v_2\}, \{v_2, v_4\}, \{v_2,v_4\})$ n'est pas un chemin, à cause de la répétition de l'arête $\{v_2,v_4\}$.

Un cycle dans un graphe est un chemin dont les extrémités sont identiques.

Par exemple, dans le graphe précédent $(\{v_2,v_6\}, \{v_4,v_6\}, \{v_3,v_4\}, \{v_2,v_3\})$ est un cycle obtenu à partir de la séquence de sommets $(v_2, v_6, v_4, v_3, v_2)$.

La longueur d’un chemin est la longueur de la séquence d’arêtes. Pour les graphes pondérés, la longueur correspond à la somme des poids.

S'il existe au moins un chemin reliant deux sommets $u$ et $v$, il existe un chemin le plus court. La plupart des leçons suivantes seront consacrées à apprendre comment trouver les chemins les plus courts entre deux sommets dans un graphe.

Enfin, un graphe est dit connexe si pour toute paire de sommets, il existe un chemin ayant ces sommets comme extrémités.

Tous les graphes exemples que nous avons considérés jusqu'à présent sont connexes. En voici un qui ne l'est pas.

Graphes standards

Certains graphes sont très utiles car ils peuvent apparaître dans de nombreuses situations.

Par exemple, nous rencontrons des arbres tout le temps : dans les systèmes de fichiers, dans les graphes généalogiques, dans les compétitions sportives où les tournois sont souvent représentés sous forme d'arbres, etc.

Les arbres sont des graphes connexes sans cycle.

Notez que les arbres sont souvent confondus avec les arbres enracinés, dans lesquels les sommets connectés ont une relation spécifique entre eux. Les arbres enracinés peuvent être définis en choisissant un sommet arbitraire comme racine de l'arbre.

Un autre exemple de graphe standard est le graphe complet. Un graphe complet inclut toutes les arêtes possibles, et est souvent un bon choix pour tester les capacités ou le temps de calcul d'un algorithme qui opère sur des graphes.

Les labyrinthes peuvent aussi être représentés comme des graphes. Dans ce cas, les sommets peuvent représenter les cellules du labyrinthe, et les arêtes peuvent être définies comme des cellules voisines qui ne sont pas séparées par un mur.

Mots de conclusion

Merci pour votre attention ! J’ai vraiment apprécié parler de la théorie des graphes avec vous aujourd’hui.