Représenter un graphe en machine

Un cap pour ce chapitre

Ce que vous saurez faire

Construire une matrice d’adjacence.
Lire des listes de successeurs et de prédécesseurs.
Comparer les coûts de stockage et les usages.

Les bases utiles pour commencer

Fixer un ordre des sommets

Pour construire une matrice, on choisit un ordre des sommets, par exemple A, B, C, D. La ligne représente le sommet de départ et la colonne celui d’arrivée dans notre convention. La case M[i][j] vaut 1 si un arc va du sommet i au sommet j, et 0 sinon.

L’ordre choisi peut changer d’une représentation à l’autre ; il doit donc être indiqué. Une matrice numérique sans noms de lignes ou sans convention est difficile à interpréter. Une fois l’ordre fixé, chaque case répond directement à une question d’existence de relation entre deux sommets.

Pour lire M[2][1], traduisez d’abord les indices dans l’ordre annoncé. Avec A,B,C,D, la case concerne C vers B. Le sens ne se déduit pas du plus petit indice. Lors d’une conversion, vérifiez chaque relation en effectuant ce trajet « nom de départ, ligne, nom d’arrivée, colonne ». Cette méthode évite une transposition involontaire.

Orientation, symétrie et diagonale

Dans un graphe non orienté, une arête A-B donne une relation dans les deux sens. La matrice est alors symétrique : M[i][j] = M[j][i]. Pour un graphe orienté, cette symétrie n’est pas imposée. Une matrice symétrique peut néanmoins représenter un graphe orienté dont tous les arcs sont réciproques.

La diagonale décrit les relations d’un sommet vers lui-même, appelées boucles dans le vocabulaire des graphes. Si le modèle les exclut, la diagonale est nulle. Le convertisseur accepte des boucles pour montrer cette information, sans les confondre avec des boucles de programmation.

Conserver seulement les voisins utiles

Une liste d’adjacence associe à chaque sommet ses voisins ou successeurs. Pour A → B et A → C, l’entrée de A contient [B, C]. Il faut conserver une entrée vide pour un sommet sans successeur, sinon on risquerait de perdre l’existence d’un sommet isolé.

Une liste de prédécesseurs conserve les relations dans l’autre sens de lecture. Pour construire celle d’un sommet, on cherche qui possède un arc vers lui. Dans une matrice, les successeurs se lisent sur sa ligne et les prédécesseurs sur sa colonne.

successeurs = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": [],
    "D": []
}

Choisir selon le traitement

Une matrice de n sommets contient n² cases, même si peu de liens existent. Elle permet de tester directement une relation lorsque les indices sont connus. Une représentation par listes conserve les sommets et les liens présents ; elle peut être plus compacte pour un graphe peu dense.

Parcourir les successeurs d’un sommet est naturel avec une liste dédiée. Avec une matrice, on examine sa ligne pour trouver les 1. Il n’existe donc pas un format toujours meilleur : le nombre de liens, les opérations fréquentes et les contraintes de mémoire orientent le choix. Pour un graphe pondéré, le codage des absences doit aussi éviter de confondre « aucun lien » et un éventuel poids nul.

Compter les 1 demande une convention. Dans une matrice orientée, chaque 1 représente un arc, boucle comprise. Dans un graphe non orienté sans boucle, chaque arête produit deux 1 symétriques. Il faut alors diviser leur total par deux pour compter les arêtes. Une boucle n’est présente qu’une fois sur la diagonale et demande un traitement séparé si elle est autorisée.

Exemple suivi : matrice et listes simultanément

Avec les arcs A→B, B→C et C→A, et D isolé, la matrice dans l’ordre A,B,C,D possède les lignes [0,1,0,0], [0,0,1,0], [1,0,0,0], [0,0,0,0]. Les listes de successeurs sont A:[B], B:[C], C:[A], D:[]. Le graphe contient quatre sommets malgré seulement trois arcs.

La colonne de A indique un arc venant de C ; sa ligne indique un arc vers B. Le cycle A,B,C,A apparaît dans les deux représentations. Pour vérifier la conversion, comptez les relations puis contrôlez les cases correspondantes. La ligne vide de D conserve son absence de successeurs, et sa colonne vide montre qu’il n’a pas de prédécesseur. Supprimer D ferait perdre une information du modèle.

Choisir un format et conserver le sens des poids

Pour 100 sommets, une matrice possède 10 000 cases, quel que soit le nombre de relations. Si seuls 120 arcs existent, des listes de successeurs décrivent directement ces arcs, avec une entrée par sommet. Tester un arc précis est direct dans la matrice lorsque les indices sont connus ; parcourir uniquement les voisins présents est naturel dans une liste.

Dans un graphe pondéré, remplacer les 1 par des poids exige une convention pour l’absence. Si un coût nul est possible, zéro ne peut plus signifier à la fois absence et liaison gratuite. On peut employer une valeur distincte comme None, selon l’implémentation. Les conversions doivent conserver l’orientation, les sommets isolés, les boucles et les poids. Deux tableaux visuellement différents peuvent représenter le même graphe si leur ordre des sommets diffère, à condition de comparer les noms et non les positions seules.

À vous de faire varier les choses

Transformez vos arcs en données

Saisissez des relations comme A>B,B>C entre A, B, C et D. Changez l’orientation et observez matrice, successeurs et prédécesseurs.

Lire le résultat de l’expérience initiale

3 relation(s) représentée(s).

Lignes = départs, colonnes = arrivées. 0 saisie(s) ignorée(s). Les doublons ne créent pas de nouveaux liens.

Sommet	B	C	D	Successeurs	Prédécesseurs
A	1	1	0	B, C	aucun
B	0	0	1	D	A
C	0	0	0	aucun	A
D	0	0	0	aucun	B

Indice 2

Une liste ne contient que les relations effectivement présentes.

Comprendre la correction

La matrice comporte 10 000 cases. Une liste de successeurs donne directement les voisins à parcourir, sans scanner cent cases de ligne. La matrice permet au contraire un test direct par deux indices pour une relation précise. Le choix dépend donc des opérations fréquentes et de la densité.

Les erreurs qui méritent un détour

Inverser ligne et colonne sans annoncer une autre convention.: Notez départ en ligne et arrivée en colonne avant de remplir chaque case.
Supprimer les sommets sans successeur du dictionnaire.: Une liste vide est une information : le sommet existe même s’il n’a pas de sortie.

La fiche à garder

L’essentiel à retenir

Une matrice nécessite un ordre explicite des sommets.
Les lignes donnent les successeurs et les colonnes les prédécesseurs dans notre convention.
Le format dépend des liens et des opérations étudiées.

Cette notion au bac

Retrouvez ces idées dans un sujet complet, avec des indices, une correction expliquée et des ateliers.

Le prochain pas

Retrouver le catalogue de Terminale

Ce chapitre s’appuie sur le programme officiel de Terminale (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.