Théorie des graphes : exercices corrigés pas à pas

1Sommets, arêtes et degrés

Un graphe se compose de sommets (points) et d’arêtes (lignes entre deux sommets). Dans un graphe simple, il n’y a ni boucles ni arêtes multiples.

Le degré d’un sommet est le nombre d’arêtes qui y aboutissent. Chaque arête a deux extrémités, donc elle ajoute 1 au degré de chacune. Cela donne le lemme des poignées de main :

Deux conséquences : la somme des degrés est toujours paire, et le nombre de sommets de degré impair est pair lui aussi.

• Le graphe complet K_n relie chaque paire : n(n − 1)/2 arêtes.
• Le graphe biparti complet K_m,n relie chaque sommet d’un côté à chaque sommet de l’autre : m·n arêtes.
• Un graphe k-régulier à n sommets a n·k/2 arêtes.

La matrice d’adjacence a un 1 en (i, j) quand i et j sont reliés. Pour un graphe non orienté elle est symétrique, la somme d’une ligne est un degré, et l’entrée (i, j) de Mᴸ compte les marches de longueur L de i à j.

2Euler et Hamilton

Un circuit eulérien utilise chaque arête exactement une fois et revient à son point de départ. Un chemin eulérien utilise chaque arête une fois mais peut finir ailleurs. Pour un graphe connexe :

• tous les degrés pairs : il existe un circuit eulérien ;
• exactement deux degrés impairs : il existe un chemin eulérien, d’un sommet impair à l’autre ;
• plus de deux degrés impairs : ni l’un ni l’autre.

Un circuit hamiltonien visite chaque sommet exactement une fois. Il n’existe pas de test simple par les degrés. Dans K_n il y a (n − 1)!/2 circuits hamiltoniens différents : fixez le départ, ordonnez les n − 1 autres sommets, et divisez par 2 pour les deux sens.

3Arbres

Un arbre est un graphe connexe sans cycle. Tout arbre à n sommets a exactement n − 1 arêtes. Ajouter une arête quelconque crée un cycle ; en retirer une quelconque le déconnecte.

Une forêt de c arbres à n sommets a n − c arêtes. Un graphe connexe à m arêtes conserve un arbre couvrant après suppression de m − n + 1 arêtes.

Le lemme des poignées de main compte les feuilles : Σ deg = 2(n − 1). Une forme courte est L = 2 + Σ (d − 2) sur les sommets de degré d ≥ 3. Un arbre avec deux sommets de degré 3 et le reste en feuilles a 2 + 1 + 1 = 4 feuilles.

4Dijkstra et arbres couvrants minimaux

L’algorithme de Dijkstra trouve les plus courtes distances depuis un sommet de départ dans un graphe à poids positifs ou nuls.

1. Donnez au départ la distance 0 et à tous les autres sommets ∞.
2. Fixez le sommet non fixé de plus petite distance ; sa distance est maintenant définitive.
3. Pour chaque voisin v, mettez à jour d(v) = min(d(v), d(u) + w(u, v)).
4. Répétez jusqu’à ce que la cible soit fixée.

Un arbre couvrant minimal relie tous les sommets avec le plus petit poids total. Kruskal trie les arêtes de la plus légère à la plus lourde et prend chacune sauf si elle ferme un cycle. Prim fait croître un arbre à partir d’un sommet de départ, en ajoutant toujours l’arête la plus légère qui en sort. Les deux s’arrêtent après n − 1 arêtes.

5Erreurs fréquentes

• Oublier de diviser la somme des degrés par 2 pour obtenir le nombre d’arêtes.
• Tester l’existence d’un circuit eulérien sans vérifier que le graphe est connexe.
• Fixer un sommet dans Dijkstra avant qu’il ait la plus petite distance provisoire.
• Prendre les n − 1 arêtes les plus légères sans vérifier les cycles.
• Compter les circuits hamiltoniens de K_n comme n! au lieu de (n − 1)!/2.

6À quoi ressemblent les questions d’examen

• Facile : degrés et arêtes. Vous utilisez le lemme des poignées de main, comptez les arêtes de K_n, K_m,n, des graphes réguliers et des arbres, lisez une matrice d’adjacence, ou cliquez sur le sommet d’un degré donné.
• Moyen : chemins eulériens et arbres. Vous décidez si un graphe a un circuit ou un chemin eulérien, comptez les feuilles d’un arbre, le nombre d’arêtes à retirer pour obtenir un arbre couvrant, ou les circuits hamiltoniens de K_n.
• Difficile : plus courts chemins et arbres couvrants. Vous exécutez l’algorithme de Dijkstra, trouvez le sommet fixé à un tour donné, le poids d’un arbre couvrant minimal, cliquez sur l’arête que Kruskal ou Prim ajoute ensuite, ou comptez des marches avec la matrice d’adjacence.