Introduction aux Graphes et Leurs Représentations

1. Qu'est-ce qu'un graphe ? Définitions et typologie

Un graphe est un modèle mathématique permettant de représenter des relations entre des objets. De manière informelle, un graphe est un ensemble de points (les sommets) reliés par des lignes (les arêtes).

Pour une introduction visuelle rapide aux différents types de graphes, je vous propose de visionner cette courte vidéo.

Maintenant que vous avez une intuition visuelle, formalisons ces concepts. En théorie des graphes, la rigueur est primordiale.

Un graphe $G$ est un couple $G=(S,A)$ où :

• $S$ est un ensemble fini de sommets (ou nœuds, vertices en anglais). Le nombre de sommets, $|S|$, est appelé l'ordre du graphe.
• $A$ est un ensemble de paires de sommets, appelées arêtes (edges) ou arcs.

La nature de ces paires définit le type de graphe :

• Graphe non orienté : Les arêtes sont des paires non ordonnées $\{u,v\}$. Si une arête relie $u$ et $v$, on dit que $u$ et $v$ sont adjacents. Le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes.
• Graphe orienté (ou digraphe) : Les arêtes, appelées arcs, sont des couples ordonnés $(u,v)$, signifiant qu'il existe une liaison de $u$ vers $v$.
  • On dit que $v$ est un successeur de $u$, et $u$ un prédécesseur de $v$.
  • Le degré sortant d'un sommet ($d^{+}(u)$) est le nombre d'arcs qui partent de $u$.
  • Le degré entrant d'un sommet ($d^{-}(u)$) est le nombre d'arcs qui arrivent à $u$.

L'image ci-dessous illustre bien ces notions pour un graphe orienté.

Enfin, on distingue :

• Graphe non pondéré : Toutes les arêtes ont une importance égale.
• Graphe pondéré : Une valeur (un poids) est associée à chaque arête ou arc. Ce poids peut représenter une distance, un coût, une capacité, etc.

Pour une définition formelle et complète de cette terminologie, je vous invite à lire la section suivante du polycopié de Christine Solnon (CNRS).

2. Représentations d'un graphe en machine

Comment traduire cette structure abstraite en une structure de données concrète ? Il existe deux approches classiques, chacune avec ses avantages et ses inconvénients.

La vidéo suivante, bien qu'en anglais, offre une explication particulièrement claire et détaillée de ces deux représentations et de leurs compromis.

Synthétisons et formalisons ce que vous venez de voir.

a) Matrice d'adjacence

Pour un graphe d'ordre $n$ (avec des sommets numérotés de 0 à $n-1$), on utilise une matrice $M$ de taille $n\times n$.

• Graphe non pondéré : $M[i][j]=1$ s'il existe une arête entre $i$ et $j$, et 0 sinon. Pour un graphe non orienté, la matrice est symétrique.
• Graphe pondéré : $M[i][j]$ contient le poids de l'arête $(i,j)$. S'il n'y a pas d'arête, on utilise une valeur spéciale : $+\infty$ pour un problème de plus court chemin, 0 ou une autre valeur sentinelle selon le contexte.

Avantages :

• Vérifier l'existence d'une arête $(i,j)$ se fait en temps constant $O(1)$.

Inconvénients :

• L'espace mémoire requis est toujours en $\Theta (|S{|}^2)$, même si le graphe a très peu d'arêtes.
• Lister tous les voisins d'un sommet $i$ requiert de parcourir toute la ligne $i$, soit un coût en $\Theta (|S|)$.

b) Listes d'adjacence

On utilise un tableau (ou une liste) de taille $n$, où l'entrée $i$ pointe vers une liste chaînée contenant tous les voisins du sommet $i$.

• Graphe non pondéré : La liste pour le sommet $i$ contient les identifiants de ses voisins.
• Graphe pondéré : La liste contient des paires (voisin, poids).
• Graphe non orienté : Chaque arête $\{u,v\}$ apparaît deux fois : $v$ est dans la liste de $u$, et $u$ dans la liste de $v$.

Avantages :

• L'espace mémoire est en $\Theta (|S|+|A|)$, ce qui est très efficace pour les graphes creux (où $|A|\ll |S{|}^2$).
• Lister tous les voisins d'un sommet $i$ est optimal : le coût est proportionnel à son degré, $O(\text{deg}(i))$.

Inconvénients :

• Vérifier l'existence d'une arête $(i,j)$ requiert de parcourir la liste d'adjacence de $i$, soit un coût en $O(\text{deg}(i))$ dans le pire cas.

3. Analyse comparative et choix de la représentation

Le choix entre matrice et listes d'adjacence est un arbitrage classique en algorithmique. Il dépend de la densité du graphe et des opérations que l'on souhaite effectuer.

• Un graphe est dit dense si $|A|$ est proche de $|S{|}^2$.
• Un graphe est dit creux (ou épars) si $|A|$ est beaucoup plus petit que $|S{|}^2$.

La plupart des graphes rencontrés en pratique (réseaux sociaux, web, réseaux routiers) sont creux.

Regardons la fin de la vidéo précédente pour une excellente synthèse de cette comparaison.

Pour renforcer ces notions avec une lecture en français et des exemples concrets, consultez la section suivante.

En résumé, pour la préparation à l'Agrégation, retenez la règle générale : sauf indication contraire, privilégiez les listes d'adjacence. C'est la représentation la plus polyvalente et la plus performante pour la majorité des problèmes algorithmiques sur les graphes, qui sont souvent creux.

4. Exercice d'application

Pour vous assurer d'avoir bien assimilé ces concepts, réalisez l'exercice suivant.

Énoncé :
Soit le graphe non orienté suivant :

1. Donnez sa représentation par matrice d'adjacence.
2. Donnez sa représentation par listes d'adjacence.

Prenez le temps de construire ces deux représentations sur papier. Une fois terminé, vous pouvez vérifier votre travail avec la correction fournie dans le document ci-dessous.

Conclusion

Aujourd'hui, nous avons jeté les bases indispensables à l'étude des graphes. Nous avons vu qu'au-delà de la diversité de leurs apparences, les graphes peuvent être décrits et manipulés de manière rigoureuse.

Points clés à retenir :

• Un graphe est un couple $G=(S,A)$. Sa nature dépend de si les arêtes/arcs dans $A$ sont des paires ordonnées ou non, et si elles portent un poids.
• Les deux représentations fondamentales sont la matrice d'adjacence et les listes d'adjacence.
• La matrice d'adjacence est efficace pour les graphes denses et pour tester rapidement l'existence d'une arête ($O(1)$), mais son coût en mémoire ($\Theta (|S{|}^2)$) est souvent prohibitif.
• Les listes d'adjacence sont la norme pour les graphes creux. Elles optimisent l'espace ($\Theta (|S|+|A|)$) et le parcours des voisins d'un sommet ($O(\text{degreˊ})$).
• Le choix de la représentation est un arbitrage crucial qui dépend de la structure du graphe et des algorithmes à implémenter.

Prochaine étape :
Maintenant que nous savons représenter un graphe, comment l'explorer ? Dans notre prochaine leçon, nous aborderons notre premier algorithme de parcours : le parcours en largeur (BFS - Breadth-First Search). Nous verrons comment l'implémenter et comment il nous permet de résoudre un problème fondamental : trouver le plus court chemin en nombre d'arêtes.