Graphes et représentations

Un graphe possède des sommets et des liens. Les sommets représentent les objets retenus dans le modèle : arrêts, pages, personnes ou tâches. Dans un graphe non orienté, une arête relie deux sommets sans distinguer un départ et une arrivée. Dans un graphe orienté, un arc va d’un sommet vers un autre. Un arc de u vers v ne donne pas automatiquement un arc de v vers u. Nous travaillons ici avec des graphes simples, sans arcs multiples pour une même paire ordonnée, et non pondérés. Les graphes plus généraux peuvent porter des poids ou d’autres informations.

Un successeur de u est atteint par un arc qui part de u. Un prédécesseur de u est à l’origine d’un arc qui arrive en u. Dans un graphe non orienté, on parle de voisins et la relation est réciproque. Un sommet peut n’avoir aucun lien : il reste un sommet du graphe. Le modèle doit aussi dire ce qu’un lien signifie. Une arête entre deux villes peut désigner une liaison directe ; elle ne doit pas être ajoutée seulement parce qu’un trajet comportant plusieurs étapes existe. Un chemin est une suite de liens, pas nécessairement un lien unique.

Pour n sommets, une matrice d’adjacence possède n lignes et n colonnes. Il faut d’abord fixer l’ordre des sommets. Nous choisissons A, B, C, D, à la fois pour les lignes et pour les colonnes. La case de ligne u et de colonne v vaut 1 s’il existe un arc de u vers v, et 0 sinon. Une ligne décrit donc les successeurs du sommet correspondant ; une colonne permet de lire ses prédécesseurs. Inverser ces rôles revient à représenter les arcs dans l’autre sens.

Dans un graphe non orienté, la matrice est symétrique : la case de ligne u et colonne v est égale à celle de ligne v et colonne u. Cela traduit la réciprocité de chaque arête. La diagonale décrit les boucles, c’est-à-dire les liens d’un sommet vers lui-même ; elle est nulle dans nos exemples sans boucle. Une ligne nulle dans un graphe orienté signifie absence de successeur, pas forcément isolement. Pour qu’un sommet soit isolé, il ne doit avoir ni lien entrant ni lien sortant.

Une représentation par listes de successeurs associe à chaque sommet la liste des sommets atteints directement. En Python, un dictionnaire convient : les clés sont les sommets et les valeurs des listes. Notre graphe devient {"A" : ["B"], "B" : ["C"], "C" : ["A", "D"], "D" : []}. La clé D est conservée même si sa liste est vide. On peut construire de même les listes de prédécesseurs en inversant le rôle du départ et de l’arrivée. Pour un graphe non orienté, chaque arête apparaît dans la liste des deux extrémités.

Le choix de représentation dépend des opérations. Une matrice réserve n² cases et permet de consulter directement une relation entre deux indices. Des listes de successeurs mémorisent les sommets et les liens présents ; pour un graphe orienté avec m arcs, leur volume est de l’ordre de n + m. Tester si v figure parmi les successeurs de u demande alors une recherche dans cette liste. L’économie de mémoire ne rend pas toutes les opérations plus rapides. On compare donc un besoin précis, comme parcourir tous les voisins ou tester très souvent un lien particulier.

La création par compréhension fabrique ici une nouvelle liste pour chaque ligne. Il faut vérifier cette indépendance pendant la mise au point. Pour revenir d’une matrice vers les successeurs, on parcourt chaque ligne et on ajoute le sommet de colonne pour chaque 1. Un aller-retour entre représentations doit conserver l’ensemble des arcs, même si l’ordre des successeurs change. Comparer les ensembles de voisins peut donc être plus pertinent que comparer des listes caractère par caractère.

Une figure lisible aide à vérifier quelques liens, mais elle ne remplace pas la définition des données. Deux dessins placent parfois les mêmes sommets à des endroits différents : ils décrivent le même graphe si les relations sont conservées. Inversement, deux réseaux visuellement semblables peuvent différer par le sens d’une seule flèche. Pendant une trace, choisis un arc et vérifie sa présence dans les trois formes : dessin, liste de successeurs et case de matrice. Ce contrôle local répété évite les erreurs d’orientation systématiques.

S’entraîner : ouvre l’espace Exercices du site.