Les graphes

Un plan de métro, un réseau électrique, un ordre de montage, la liste des amis de quelqu'un : à chaque fois, des objets et des liens entre eux. Un graphe est l'objet mathématique qui ne retient que ça (qui est relié à qui) et qui jette tout le reste. Cette abstraction brutale est exactement ce qui permet de traiter de la même façon un itinéraire routier et un planning de tâches.

Définitions

Définition

Un graphe $G = (V, E)$ est la donnée d'un ensemble V de sommets (ou nœuds) et d'un ensemble E d'arêtes, chaque arête reliant deux sommets.

Ce qui compte, c'est uniquement la relation « est relié à ». La position des points sur le dessin, la longueur ou la courbure des traits n'ont aucune signification.

C'est le point le plus important du chapitre, et le plus contre-intuitif. Les deux figures ci-dessous sont le même graphe : mêmes sommets, mêmes paires reliées, dans les deux cas les arêtes (A,B), (B,C), (C,D) et (D,A). Seule la disposition change.

Graphe non orienté4 sommets, 4 arêtes

Quatre sommets, quatre arêtes, posés sans réfléchir. Deux traits se croisent au milieu, et ce croisement ne signifie rien : ce n'est pas un sommet, rien ne s'y passe.

Graphe non orienté4 sommets, 4 arêtes

Le même graphe, les mêmes quatre arêtes, après avoir seulement déplacé les points. Plus aucun croisement, et pourtant rien n'a changé : un graphe n'a pas de forme.

Un graphe n'est donc pas un dessin : c'est une liste de paires. Le dessin n'est qu'un moyen commode de la lire, et l'on a le droit de le refaire autrement chaque fois que cela arrange. C'est même le premier réflexe devant un exercice : redessiner pour que les arêtes ne se croisent plus, comme on vient de le faire ici.

Le vocabulaire minimal

Orienté : les arêtes ont un sens (on les appelle alors des arcs), comme un sens interdit ou une dépendance de tâches.
Non orienté : la relation est réciproque, comme une amitié ou un câble.
Pondéré : chaque arête porte un nombre (distance, coût, durée).
Simple : ni boucle (arête d'un sommet vers lui-même), ni arête multiple entre deux mêmes sommets.

Ces mots se voient mieux qu'ils ne se lisent. Voici d'abord un graphe orienté.

Graphe orienté3 sommets, 3 arêtes

Les pages d'une boutique en ligne et les liens qui vont de l'une à l'autre. Chaque flèche ne se lit que dans un sens : depuis le panier on atteint le paiement, mais aucune flèche ne fait le chemin inverse.

Et voici un graphe qui n'est pas simple, le seul du chapitre.

Graphe non orienté3 sommets, 4 arêtes

Deux arêtes distinctes relient P à Q, ce qui en fait une arête multiple, et R est relié à lui-même par une boucle. Tout le reste du chapitre travaille sur des graphes simples, où ces deux situations sont exclues.

Un graphe simple, donc, est un graphe où l'on peut se contenter de dire « ces deux sommets sont reliés, ou ils ne le sont pas », sans jamais avoir à préciser combien de fois.

Le graphe de référence du chapitre

Tous les exemples qui suivent portent sur celui-ci, non orienté, à cinq sommets et cinq arêtes.

Graphe non orienté5 sommets, 5 arêtes

Le graphe de référence. Un triangle A, B, C prolongé par une chaîne C, D, E. Cinq sommets, cinq arêtes.

Arêtes : (A,B), (A,C), (B,C), (C,D), (D,E).

Pourquoi celui-là et pas un plus joli

Un carré aurait été plus symétrique, et c'est exactement le défaut : tous ses sommets auraient le même degré, aucun ne serait de degré impair, et il ne contiendrait aucun triangle. Trois sections du chapitre n'auraient alors rien à montrer.
Ce graphe-ci, lui, a des degrés qui vont de 1 à 3, exactement deux sommets de degré impair, un cycle et une extrémité. Chacune de ces particularités sert plus loin, et c'est pour cela qu'il a été choisi.

Degrés

Définition

Le degré d'un sommet est le nombre d'arêtes qui y aboutissent (une boucle compte double). Dans un graphe orienté, on distingue le degré entrant et le degré sortant.

Exemple travaillé. Relevons les degrés du graphe de référence, en comptant simplement les traits qui partent de chaque point.

Sommet	Ses voisins	Degré
A	B, C	2
B	A, C	2
C	A, B, D	3
D	C, E	2
E	D	1

Deux sommets se remarquent. C est le plus connecté, avec 3 voisins : c'est le point de passage obligé entre le triangle et le reste. E est de degré 1 : on l'appelle une extrémité, et un tel sommet n'est sur aucun cycle, puisqu'on ne peut en repartir que par où l'on est venu.

Graphe non orienté5 sommets, 5 arêtes

Le graphe de référence colorié par degré. Les trois sommets de degré 2 partagent une teinte ; C, seul de degré 3, et E, seul de degré 1, ont chacun la leur. Le degré ne se calcule pas : il se compte du doigt, en suivant les traits qui touchent le point.

Lemme des poignées de main

La somme des degrés de tous les sommets vaut deux fois le nombre d'arêtes.

\sum \deg(v) = 2 |E|

La démonstration tient en une phrase : chaque arête a deux extrémités, donc elle est comptée une fois dans le degré de chacune. Vérification sur l'exemple : $2 + 2 + 3 + 2 + 1 = 10 = 2 \times 5$ ✓

Le contrôle à faire systématiquement

Relever les degrés puis vérifier que leur somme vaut le double du nombre d'arêtes coûte dix secondes, et attrape la plupart des erreurs de lecture d'un énoncé : une arête oubliée, une arête comptée deux fois, un sommet mal relié.
C'est le seul contrôle gratuit du chapitre. Le faire avant toute autre question.

Deux conséquences immédiates

La somme des degrés est toujours paire. Et le nombre de sommets de degré impair est lui-même toujours pair. C'est le raccourci qui permet de répondre « non » en dix secondes à « existe-t-il un graphe à 5 sommets tous de degré 3 ? » : la somme vaudrait 15, un nombre impair, ce qui est impossible.

Chemins, cycles, connexité

Définitions

Un chemin est une suite de sommets consécutivement reliés. Sa longueur est son nombre d'arêtes, jamais son nombre de sommets. Un cycle est un chemin qui revient à son point de départ sans réemprunter deux fois la même arête. Un graphe est connexe si toute paire de sommets est reliée par au moins un chemin. Une composante connexe est un morceau connexe maximal.

La longueur se compte en arêtes

Le chemin A, C, D, E comporte quatre sommets et sa longueur vaut trois. C'est l'erreur de comptage la plus fréquente du chapitre, et elle fausse ensuite toute lecture des puissances de la matrice.
Le moyen de ne plus s'y tromper : la longueur est le nombre de pas qu'on fait, et l'on part du premier sommet sans avoir encore fait de pas.

Définition

La distance entre deux sommets est la longueur du plus court chemin qui les relie, dans un graphe non pondéré.

Exemple travaillé. Lisons ces trois notions sur le graphe de référence, une figure à la fois.

D'abord le cycle. Le triangle $A - B - C - A$ en est un : on part de A, on emprunte trois arêtes distinctes, et l'on revient à A.

Graphe non orienté5 sommets, 5 arêteschemin mis en évidence

Le cycle A, B, C, A. Sa longueur vaut 3, puisqu'on emprunte trois arêtes. C'est le seul cycle du graphe : ni D ni E ne peuvent appartenir à un cycle, car les quitter oblige à revenir par où l'on est arrivé.

Ensuite la distance. Celle de A à E vaut 3, et le chemin qui la réalise est $A - C - D - E$ .

Graphe non orienté5 sommets, 5 arêtes

0 / 4

Rien n'est encore visité.

Le plus court chemin de A à E, de longueur 3. Aucun raccourci n'existe : pour atteindre E il faut passer par D, et pour atteindre D il faut passer par C. Chacun de ces deux sommets est un passage obligé.

Enfin la connexité. Le graphe de référence est connexe : depuis n'importe lequel de ses cinq sommets on atteint les quatre autres. Pour voir ce que la connexité interdit, il faut un graphe qui ne l'est pas.

Graphe non orienté6 sommets, 4 arêtes

Un graphe qui n'est pas connexe. Il se lit en trois morceaux sans aucun trait entre eux : le triangle P, Q, R, l'arête S, T, et le sommet U tout seul.

Ce graphe compte trois composantes connexes : $\{P, Q, R\}$ , $\{S, T\}$ et $\{U\}$ . Un sommet isolé en forme une à lui seul, et cela n'a rien d'un cas particulier : c'est la définition appliquée sans exception.

Connexe se compte

« Connexe » n'est pas un jugement à porter à l'œil, c'est le résultat d'un décompte : un graphe est connexe si et seulement si il a exactement une composante connexe.
D'où la bonne question à se poser devant un graphe inconnu, qui n'est pas « est-il connexe » mais « combien a-t-il de composantes ». On part d'un sommet, on marque tout ce qu'on atteint, et s'il reste des sommets non marqués on recommence depuis l'un d'eux.

Un mot sur le vocabulaire

Beaucoup d'ouvrages français réservent chaîne au graphe non orienté et chemin au graphe orienté. La distinction est utile quand on écrit une démonstration, elle encombre quand on découvre le sujet.
Ce chapitre dit donc chemin dans les deux cas, et le précise ici une fois pour toutes.

Arbres

Définition

Un arbre est un graphe connexe sans cycle.

Propriété

Un arbre à n sommets a exactement $n - 1$ arêtes. Réciproquement, un graphe connexe à $n - 1$ arêtes est un arbre. Et entre deux sommets d'un arbre, il existe exactement un chemin qui ne repasse jamais par un sommet déjà visité.

C'est la structure la plus économique qui garde tout connecté : une arête de moins et le graphe se coupe en deux, une arête de plus et un cycle apparaît. C'est pour cela qu'un réseau qu'on veut connecter au moindre coût est toujours un arbre.

Exemple travaillé. Le graphe de référence est-il un arbre ?

Non, et deux raisons suffisent chacune à conclure. Il contient le cycle $A - B - C - A$ , et un arbre n'en a aucun. Et il a 5 sommets pour 5 arêtes, alors qu'un arbre à 5 sommets en aurait exactement 4.

Il suffit pourtant d'une seule arête en moins pour en faire un arbre. En retirant $A - B$ , le triangle s'ouvre, le graphe reste connexe, et il ne reste que 4 arêtes.

Graphe non orienté5 sommets, 4 arêtes

Le graphe de référence privé de l'arête A-B. Quatre arêtes pour cinq sommets, aucun cycle, toujours connexe : c'est un arbre. Entre deux sommets quelconques, il ne reste plus qu'une seule route sans retour en arrière.

Ce que l'unicité du chemin entraîne

Dans le graphe de départ, on va de A à C soit directement, soit par B. Dans l'arbre, une seule route subsiste.
C'est un avantage et une fragilité. Un avantage, parce qu'il n'y a jamais d'ambiguïté ni de calcul à faire pour choisir un itinéraire. Une fragilité, parce que la moindre arête coupée déconnecte le graphe : un arbre n'a aucune redondance, par construction.

Graphes orientés sans cycle (DAG)

Un DAG (Directed Acyclic Graph) est un graphe orienté sans cycle. On ne peut jamais revenir en arrière en suivant les flèches. C'est la structure des dépendances : tâches d'un projet, prérequis d'un cursus, ordre de compilation.

Graphe orienté6 sommets, 6 arêtes

Un chantier en six tâches. Chaque flèche se lit « doit être terminé avant ». Aucun circuit n'est possible, sans quoi une tâche devrait précéder elle-même.

Tri topologique

Un DAG admet toujours un tri topologique : un ordre des sommets tel que chaque flèche aille de gauche à droite. Autrement dit, un planning où aucune tâche ne commence avant ses prérequis.

Exemple travaillé. Trions le chantier. La méthode tient en une boucle : on cherche une tâche dont tous les prérequis sont déjà placés, on la place, et on recommence.

Aucune flèche n'arrive sur Fondations : elle part donc en premier. Une fois placée, Murs et Réseaux n'attendent plus rien, et l'on peut prendre l'un ou l'autre. Disons Murs, puis Réseaux. Toiture n'attendait que Murs, elle suit. Cloisons attendait Réseaux et Toiture, toutes deux placées, elle suit à son tour. Reste Peinture.

Un ordre valide est donc : Fondations, Murs, Réseaux, Toiture, Cloisons, Peinture. Et l'autre choix en donne un tout aussi valide : Fondations, Réseaux, Murs, Toiture, Cloisons, Peinture.

Le tri topologique n'est pas unique, et cela se comprend : Murs et Réseaux ne dépendent pas l'un de l'autre, donc rien n'impose leur ordre. Ils pourraient même se faire en même temps, ce qui est exactement l'information qu'un chef de chantier cherche.

Pourquoi « sans cycle » est la condition

S'il existait un circuit, disons une tâche X qui attend Y et une tâche Y qui attend X, aucun ordre ne pourrait les placer : X devrait figurer avant Y, et Y avant X.
C'est ainsi qu'un outil de compilation détecte une dépendance circulaire : il cherche un tri topologique, ne le trouve pas, et le signale. L'absence de cycle n'est pas une hypothèse commode, c'est exactement ce qui rend le planning possible.

Représentations

Liste d'adjacence

À chaque sommet on associe la liste de ses voisins.

Liste d'adjacence

A: : {B, C}
B: : {A, C}
C: : {A, B, D}
D: : {C, E}
E: : {D}

Liste d'arêtes

(A, B)
(A, C)
(B, C)
(C, D)
(D, E)

Les deux écritures les plus économes du graphe de référence, calculées à partir des mêmes arêtes que le dessin. La matrice est symétrique, parce que le graphe n'est pas orienté. Sa diagonale est nulle, parce qu'aucun sommet n'est son propre voisin. La somme d'une ligne donne le degré du sommet correspondant.

Économe en mémoire quand le graphe a peu d'arêtes, et pratique pour parcourir les voisins d'un sommet : la ligne de C donne ses trois voisins d'un coup, sans rien avoir à chercher ailleurs.

Notons que chaque arête y figure deux fois, une fois dans chaque sens : l'arête (A,B) apparaît dans la ligne de A et dans celle de B. C'est la même redondance que celle du lemme des poignées de main, et l'on retrouve d'ailleurs les degrés en comptant les éléments de chaque ligne : 2, 2, 3, 2, 1.

La liste d'arêtes, à droite, est encore plus compacte : les cinq paires, et rien d'autre. Elle est parfaite pour transporter un graphe d'un programme à un autre, et mauvaise pour l'interroger, puisque répondre à « qui sont les voisins de C » demande de la relire en entier.

Matrice d'adjacence

Définition

La matrice d'adjacence M d'un graphe à n sommets est la matrice n × n dont le coefficient $m_{ij}$ vaut 1 s'il existe une arête de i vers j, et 0 sinon. Pour un graphe pondéré, on y met le poids au lieu de 1.

Pour le graphe de référence, en rangeant les sommets dans l'ordre A, B, C, D, E :

Matrice d'adjacence
	A	B	C	D	E	d
A	0	1	1	0	0	2
B	1	0	1	0	0	2
C	1	1	0	1	0	3
D	0	0	1	0	1	2
E	0	0	0	1	0	1

La matrice d'adjacence du graphe de référence, avec la colonne des degrés à droite. La matrice est symétrique, parce que le graphe n'est pas orienté. Sa diagonale est nulle, parce qu'aucun sommet n'est son propre voisin. La somme d'une ligne donne le degré du sommet correspondant.

Trois lectures immédiates, et chacune est un contrôle.

La matrice d'un graphe non orienté est symétrique : le coefficient en ligne A colonne C vaut celui en ligne C colonne A, puisque l'arête est la même.

La somme d'une ligne donne le degré du sommet : la ligne C porte trois 1, et C est bien de degré 3.

La diagonale est nulle dès que le graphe est simple, puisqu'un 1 sur la diagonale signifierait une boucle.

L'ordre des sommets est une convention, pas une donnée

Ranger les sommets dans l'ordre A, B, C, D, E est un choix. En les rangeant autrement, on obtient une matrice différente qui décrit exactement le même graphe : ses lignes et ses colonnes ont simplement été permutées.
D'où une règle de rédaction : toujours annoncer l'ordre retenu avant d'écrire la matrice. Sans cela, elle ne veut rien dire.

Puissances de la matrice d'adjacence

C'est le point de rencontre entre ce chapitre et celui sur les matrices.

Théorème

Le coefficient $(i, j)$ de la matrice $M^k$ est le nombre de chemins de longueur exactement k allant du sommet i au sommet j.

L'idée de la démonstration tient en une ligne, et elle vaut la peine d'être suivie une fois. Le coefficient $(i,j)$ de $M^2$ vaut $\sum_k m_{ik}\, m_{kj}$ . Chaque terme de cette somme vaut 1 si et seulement s'il existe à la fois une arête de i vers k et une de k vers j, c'est-à-dire un chemin en deux étapes passant par k. La somme parcourt tous les k possibles : elle compte donc exactement les chemins de longueur 2.

Voici $M^2$ sur le graphe de référence, calculée à partir des mêmes arêtes que le dessin :

Matrice d'adjacence
	A	B	C	D	E
A	2	1	1	1	0
B	1	2	1	1	0
C	1	1	3	0	1
D	1	1	0	2	0
E	0	0	1	0	1

La matrice M² du graphe de référence. Chaque case compte les chemins de longueur exactement 2, et les zéros en disent autant que les autres. La matrice est symétrique, parce que le graphe n'est pas orienté. Sa diagonale est nulle, parce qu'aucun sommet n'est son propre voisin. La somme d'une ligne donne le degré du sommet correspondant.

Quatre coefficients méritent d'être lus, et chacun se vérifie sur le dessin.

$(A, D) = 1$ . Un seul chemin de longueur 2 va de A à D : $A - C - D$ . Il faut passer par un voisin commun, et C est le seul.

Graphe non orienté5 sommets, 5 arêteschemin mis en évidence

L'unique chemin de longueur 2 de A à D, celui que compte le coefficient (A, D) de M². Le 1 du tableau, c'est ce dessin : un coefficient de M² est toujours un nombre de trajets en deux pas, qu'on peut suivre du doigt.

$(A, E) = 0$ . Aucun chemin de longueur 2 entre A et E, ce qui est normal puisque leur distance vaut 3. Un zéro dans $M^2$ ne dit pas que les sommets sont déconnectés, seulement qu'aucun chemin de cette longueur précise n'existe.

$(C, D) = 0$ , alors que C et D sont voisins. C'est le coefficient qui surprend, et c'est le plus instructif : $M$ compte les chemins de longueur 1, $M^2$ ceux de longueur exactement 2. Aller de C à D en deux pas demanderait un sommet intermédiaire relié aux deux, et il n'y en a aucun.

La diagonale donne les degrés : 2, 2, 3, 2, 1. Ce n'est pas une coïncidence. Un chemin de longueur 2 qui part de A et y revient consiste à aller chez un voisin puis à en revenir : il y en a donc autant que A a de voisins.

Chemin de longueur k, et non plus court chemin

M^k

compte les chemins de longueur exactement k, aller-retours compris. Il ne donne ni la distance, ni les plus courts chemins.
La confusion se voit sur la diagonale :

(A,A) = 2

dans

M^2

ne veut évidemment pas dire que la distance de A à lui-même vaut 2.

Pousser d'un cran fait apparaître autre chose.

Matrice d'adjacence
	A	B	C	D	E
A	2	3	4	1	1
B	3	2	4	1	1
C	4	4	2	4	0
D	1	1	4	0	2
E	1	1	0	2	0

La matrice M³, qui compte les chemins de longueur exactement 3. Sa diagonale n'est plus celle des degrés. La matrice est symétrique, parce que le graphe n'est pas orienté. Sa diagonale est nulle, parce qu'aucun sommet n'est son propre voisin. La somme d'une ligne donne le degré du sommet correspondant.

La diagonale de $M^3$ vaut 2, 2, 2, 0, 0. Revenir à son point de départ en trois pas exige un triangle, et le graphe en contient un seul, $A - B - C$  : ses trois sommets portent un 2, qui compte le triangle parcouru dans les deux sens, et les deux autres portent un 0. Une diagonale non nulle dans $M^3$ est donc exactement la trace d'un cycle de longueur 3, et c'est le moyen le plus court de détecter un triangle sans jamais le chercher.

Le coefficient $(A, E)$ reste nul dans $M$ et dans $M^2$ , et cesse de l'être dans $M^3$  : la première puissance où il s'allume donne la distance entre les deux sommets. C'est une façon d'obtenir les distances qu'aucun dessin ne fournit aussi mécaniquement, même si elle coûte cher dès que le graphe grandit.

Plus court chemin : l'algorithme de Dijkstra

Dans un graphe pondéré à poids positifs, on cherche le chemin de coût total minimal entre deux sommets. Dijkstra le trouve sans explorer toutes les possibilités.

Principe

On maintient pour chaque sommet une distance provisoire depuis le départ, initialisée à $+\infty$ (sauf le départ, à 0). À chaque étape :

choisir le sommet non traité de plus petite distance provisoire ;
le marquer comme définitivement traité ;
mettre à jour ses voisins : si passer par lui améliore leur distance, remplacer la valeur et noter le prédécesseur.

On s'arrête quand tous les sommets sont traités.

Exemple travaillé. On reprend le graphe de référence et l'on donne un poids à chaque arête. Cherchons le plus court chemin de A à E.

Graphe non orienté et pondéré5 sommets, 5 arêtes

Le graphe de référence, pondéré. Chaque nombre est un coût : une distance, une durée, un prix.

À chaque étape, on choisit le sommet non traité de plus petite distance, on le fige, et on met à jour ses voisins. La valeur en gras est celle qu'on fige.

Étape	B	C	D	E	On fige
départ	∞	∞	∞	∞	A
depuis A	1 (par A)	5 (par A)	∞	∞	B
depuis B	1	3 (par B)	∞	∞	C
depuis C	1	3	6 (par C)	∞	D
depuis D	1	3	6	8 (par D)	E

Le plus court chemin de A à E vaut 8, par A → B → C → D → E.

Le détour est plus court que la route directe

Regardons la deuxième ligne. L'arête directe

A - C

coûte 5, et c'est la première valeur inscrite pour C. À l'étape suivante, passer par B donne

1 + 2 = 3

 : la valeur tombe de 5 à 3, et le chemin retenu comporte une arête de plus.
C'est tout l'intérêt de l'algorithme, et la raison pour laquelle on ne peut pas se contenter de regarder le dessin. Le chemin le plus court en nombre d'arêtes n'est pas celui de coût minimal, et rien ne permet de deviner lequel gagne avant d'avoir calculé.

Graphe non orienté et pondéré5 sommets, 5 arêteschemin mis en évidence

Le plus court chemin de A à E, en évidence. Il emprunte quatre arêtes pour un coût de 8, là où la route par A-C en emprunterait trois pour un coût de 10.

Le point qui fait la différence

Notons le prédécesseur à chaque mise à jour, pas seulement la distance. Sans lui, on obtient la longueur du plus court chemin mais on est incapable de dire quel chemin c'est, et c'est presque toujours la deuxième question.

Une limite à connaître

Dijkstra suppose des poids positifs ou nuls. Avec un poids négatif, il peut se tromper : il fige une distance en la croyant définitive, alors qu'un détour par une arête négative ferait mieux.

Parcours eulériens

Définition

Un parcours eulérien emprunte chaque arête exactement une fois. S'il revient à son point de départ, c'est un circuit eulérien.

C'est le problème des ponts de Königsberg, à l'origine de toute la théorie des graphes, et c'est aussi celui du facteur qui veut passer une seule fois dans chaque rue.

La ville était coupée par une rivière en quatre quartiers, reliés par sept ponts. La question posée en 1735 était de savoir si l'on pouvait se promener en empruntant chaque pont une fois et une seule.

Graphe non orienté4 sommets, 7 arêtes

Les sept ponts de Königsberg. Deux ponts relient le Nord à l'île, deux autres le Sud à l'île, et trois relient les rives à la pointe Est.

Euler a compris que la géographie ne comptait pour rien : ni la taille des quartiers, ni la longueur des ponts, ni leur disposition. Seul le nombre de ponts par quartier importe. C'est l'acte de naissance de la discipline, et c'est exactement l'abstraction annoncée en tête de ce chapitre.

Les degrés valent 5 pour l'île, et 3 pour chacun des trois autres quartiers. Quatre sommets de degré impair. Le théorème ci-dessous dit que la promenade est impossible, et il le dit sans avoir essayé le moindre itinéraire.

Théorème d'Euler

Un graphe connexe admet

un circuit eulérien si et seulement si tous ses sommets sont de degré pair ;
un parcours eulérien (départ et arrivée différents) si et seulement s'il a exactement deux sommets de degré impair, et le parcours doit alors partir de l'un et finir sur l'autre.

Dans tous les autres cas, il n'en existe pas.

Le critère est purement local : on compte les degrés, on conclut. Aucun parcours à essayer, aucune recherche.

L'intuition derrière le théorème vaut d'être dite, car elle rend le résultat évident. Chaque fois qu'un parcours traverse un sommet, il y entre par une arête et en ressort par une autre : il consomme les arêtes par paires. Un sommet de degré impair ne peut donc être que le départ ou l'arrivée, là où une arête reste célibataire. Et comme un parcours n'a qu'un départ et qu'une arrivée, il ne peut y avoir plus de deux sommets impairs.

Exemple travaillé. Le graphe de référence admet-il un parcours eulérien ?

Ses degrés sont 2, 2, 3, 2, 1. Deux sommets sont de degré impair, C et E. Le théorème répond donc : pas de circuit, mais un parcours, et il doit partir de C et finir en E, ou l'inverse.

En voici un, au départ de E : $E - D - C - A - B - C$ . Les cinq arêtes y passent une fois chacune.

Graphe non orienté5 sommets, 5 arêtes

0 / 6

Rien n'est encore visité.

Un parcours eulérien du graphe de référence, au départ de E. Avancer pas à pas : les cinq arêtes sont empruntées une fois chacune, et le parcours s'achève en C, l'autre sommet de degré impair.

À manipuler

Dérouler le parcours arête par arête et vérifier qu'aucune n'est empruntée deux fois. Revenir ensuite au début et essayer de refaire le même trajet en partant de A : il faut s'arrêter avant d'avoir tout couvert. A est de degré pair, et un parcours qui y entre doit en ressortir autant de fois. Le théorème ne dit donc pas seulement qu'un tel parcours existe, il dit par où le commencer.

On ne choisit pas son point de départ

Essayer de partir de A ne mène nulle part, et ce n'est pas une question d'habileté : c'est impossible. A est de degré pair, donc tout parcours qui y passe doit en ressortir autant de fois qu'il y entre.
Partir d'un sommet pair reviendrait à le compter comme départ sans avoir d'arrivée en face, ce que le décompte des paires interdit. Le théorème ne dit donc pas seulement s'il existe un parcours, il dit où le commencer.

Eulérien ≠ hamiltonien

Un parcours eulérien passe par toutes les arêtes une fois ; un parcours hamiltonien passe par tous les sommets une fois. Le premier a un critère simple (les degrés), le second n'en a aucun : c'est un problème réputé difficile. Inutile donc de chercher un « théorème de Hamilton » aussi commode que celui d'Euler, il n'en existe pas.

Coloration

Définition

Colorer un graphe, c'est attribuer une couleur à chaque sommet de sorte que deux sommets reliés n'aient jamais la même couleur. Le nombre chromatique $\chi(G)$ est le nombre minimal de couleurs nécessaires.

L'application classique : des créneaux de réunion qui ne doivent pas se chevaucher (deux réunions reliées si une même personne est attendue aux deux), des fréquences radio à attribuer sans interférence, des variables à ranger dans les registres d'un processeur.

Calculer $\chi$ est difficile en général. On procède donc par encadrement.

Minorant : si le graphe contient une clique de taille k, c'est-à-dire k sommets tous reliés deux à deux, alors $\chi \geq k$ . Ces k sommets exigent en effet k couleurs à eux seuls.
Majorant : $\chi \leq \Delta + 1$ , où Δ est le degré maximal. La raison tient en une phrase : en coloriant les sommets un par un, celui qu'on traite a au plus Δ voisins déjà coloriés, donc il reste toujours une couleur libre parmi $\Delta + 1$ .

On encadre, puis on exhibe une coloration atteignant le minorant : c'est ce qui prouve l'égalité.

Exemple travaillé. Quel est le nombre chromatique du graphe de référence ?

Il contient le triangle A, B, C, qui est une clique de taille 3. Donc $\chi \geq 3$ .
Son degré maximal vaut 3, celui de C. Donc $\chi \leq 4$ .
L'encadrement donne $3 \leq \chi \leq 4$ , ce qui ne suffit pas à conclure : il faut exhiber une coloration.
En trois couleurs : A et D reçoivent la première, B et E la deuxième, C la troisième. Aucune arête ne relie alors deux sommets de même couleur, et c'est ce qu'il fallait obtenir.
Une coloration en 3 existe, et 3 est le minorant : donc $\chi = 3$ .

Graphe non orienté5 sommets, 5 arêtes

Une coloration en trois couleurs. A et D partagent la même sans être voisins, de même que B et E : rien n'interdit à deux sommets éloignés d'avoir la même couleur, c'est même ce qui permet d'en économiser.

Pourquoi il faut les deux moitiés du raisonnement

Exhiber une coloration en 3 couleurs prouve seulement que

\chi \leq 3

 : peut-être qu'avec plus d'astuce, 2 suffiraient.
Trouver un triangle prouve seulement que

\chi \geq 3

 : peut-être qu'ailleurs dans le graphe, une contrainte plus forte exigerait 4.
C'est la rencontre des deux qui conclut, et une copie qui n'en donne qu'une moitié n'a pas répondu à la question.

Les graphes bipartis

Définition et propriété

Un graphe est biparti si l'on peut répartir ses sommets en deux camps de sorte que toute arête aille d'un camp à l'autre, aucune ne restant à l'intérieur d'un camp.

C'est le cas si et seulement si le graphe ne contient aucun cycle de longueur impaire, ce qui équivaut à $\chi \leq 2$ .

Exemple travaillé. Le graphe de référence est-il biparti ? Appliquons le test de proche en proche, en partant de A.

A va dans le premier camp. Ses voisins B et C vont donc dans le second. Mais B et C sont reliés entre eux, et ils sont maintenant dans le même camp : l'arête (B,C) reste à l'intérieur d'un camp, ce que la définition interdit.

Le test échoue, et il échoue à cause du triangle : $A - B - C - A$ est un cycle de longueur 3, donc impaire. Le graphe de référence n'est pas biparti.

Le carré du début de chapitre, lui, l'est.

Graphe non orienté4 sommets, 4 arêtes

Le carré est biparti : A et C dans un camp, B et D dans l'autre, et chaque arête franchit la frontière. Deux couleurs suffisent, et il en faut deux dès qu'il existe une arête.

Le test qui se fait à l'œil

Pour savoir si un graphe est biparti, on colorie de proche en proche : un sommet au hasard dans le premier camp, tous ses voisins dans le second, tous les voisins de ceux-là dans le premier, et ainsi de suite.
Si le procédé se termine sans conflit, le graphe est biparti. S'il arrive qu'un sommet doive être des deux couleurs à la fois, on vient de refermer un cycle impair, et c'est la preuve qu'il ne l'est pas.

Les degrés, autant de fois qu'il faut

Deux résultats du chapitre s'énoncent en une ligne et ne se vérifient jamais : la somme des degrés vaut deux fois le nombre d'arêtes, et le nombre de sommets de degré impair est toujours pair. Le second se déduit du premier, et l'exercice le fait constater avant de le démontrer.

Compter les degrés d'un graphe tiré au sort

Un graphe non orienté de sommets A, B, C, D, E, dont les arêtes sont AC, AD, BE, CD, DE.

Le degré du sommet A
La somme des degrés de tous les sommets
Le nombre d'arêtes
Le nombre de sommets de degré impair

La dernière réponse est paire quel que soit le graphe. Ce n'est pas une propriété du graphe proposé, c'est une propriété de tous les graphes, et elle sert de contrôle : une réponse impaire signale nécessairement une erreur de comptage.

Où la démarche dérape

Un dénombrement en deux lignes, dont le résultat est exactement deux fois trop grand.

Des câbles comptés deux fois

Une seule étape est fausse. Désigner laquelle.

Un réseau relie $n$ machines, et chaque machine est reliée à exactement 3 autres. On cherche le nombre de câbles.

À calculer soi-même

Quatre comptages, tous fondés sur les définitions du début du chapitre. Aucun ne demande de dessiner le graphe.

Compter sans dessiner

1.
Un graphe possède 12 arêtes. Combien vaut la somme des degrés de ses sommets ?
2.
Combien d'arêtes possède le graphe complet à 8 sommets ?
3.
Combien d'arêtes possède un arbre à 15 sommets ?
4.
Combien d'arêtes possède le graphe biparti complet $K_{3,4}$ ?

Exercices type

Existe-t-il un graphe simple à 6 sommets dont les degrés sont 5, 5, 4, 3, 2, 1 ?

Somme des degrés : $5+5+4+3+2+1 = 20$ , ce qui est pair → il y aurait 10 arêtes. Le lemme des poignées de main ne l'interdit donc pas.

Mais regardons plus finement : deux sommets sont de degré 5, donc chacun est relié à tous les autres. Le sommet de degré 1 est alors relié à ces deux-là, ce qui lui fait un degré d'au moins 2. Contradiction : ce graphe n'existe pas.

La leçon : le lemme des poignées de main est une condition nécessaire, pas suffisante.

Un graphe a 8 sommets et 7 arêtes. Est-ce un arbre ?

Il a bien $n - 1 = 7$ arêtes, ce qui est la bonne quantité, mais seulement s'il est connexe.

S'il ne l'est pas, on peut par exemple avoir un cycle de 4 sommets d'un côté et un chemin de 4 sommets de l'autre.

Graphe non orienté8 sommets, 7 arêtes

Huit sommets, sept arêtes, et pourtant ce n'est pas un arbre : il n'est pas connexe, et il contient le cycle P, Q, R, S, P. Le compte des arêtes était bon, l'hypothèse manquait.

Le compte y est, 4 + 3 = 7 arêtes pour 8 sommets, et pourtant ce n'est pas un arbre.

Conclusion : on ne peut pas répondre sans savoir s'il est connexe.

Que valent les coefficients (A,A) et (E,E) de M³ dans le graphe de référence ?

Ce sont les nombres de chemins de longueur 3 partant d'un sommet et y revenant.

(A,A) = 2. A est sur le triangle A, B, C : on en fait le tour dans un sens, $A - B - C - A$ , ou dans l'autre, $A - C - B - A$ . Deux chemins, et pas un de plus.

(E,E) = 0. E n'est sur aucun cycle : il est de degré 1, et l'on ne peut en repartir que par où l'on est arrivé. Tout chemin qui quitte E et y revient a donc une longueur paire.

La leçon générale : un coefficient diagonal non nul dans $M^3$ signale que le sommet appartient à un triangle. C'est ainsi qu'on compte les triangles d'un graphe sans les chercher un par un.

Un facteur peut-il parcourir chaque rue une seule fois et revenir au dépôt ?

C'est la question du circuit eulérien. Il faut et il suffit que le graphe soit connexe et que tous les carrefours soient de degré pair.

S'il y a exactement deux carrefours de degré impair, il peut faire la tournée sans repasser deux fois, mais il finira ailleurs qu'au dépôt (en partant de l'un des deux carrefours impairs).

S'il y en a quatre ou plus, c'est impossible sans repasser par certaines rues.

Nombre chromatique d'un cycle à 5 sommets

Deux couleurs ne peuvent pas suffire. En les alternant le long du cycle, les sommets de rang impair reçoivent la première et ceux de rang pair la seconde ; comme le cycle a une longueur impaire, son premier et son dernier sommet sont tous deux de rang impair, donc de même couleur, alors qu'une arête les relie. Donc $\chi \geq 3$ .

Et 3 couleurs suffisent : on alterne deux couleurs sur les quatre premiers sommets, et on donne la troisième au cinquième, qui est voisin des deux.

$\chi = 3$ .

Graphe non orienté5 sommets, 5 arêtes

Un cycle à cinq sommets colorié en trois couleurs. On alterne deux couleurs le long du cycle, et le dernier sommet, voisin à la fois du premier et de l'avant-dernier, oblige à en sortir une troisième.

Pour un cycle de longueur paire, l'alternance se referme sans conflit et $\chi = 2$ .

Plus court chemin de S à T : S-A (2), S-B (5), A-B (1), A-T (7), B-T (3)

Graphe non orienté et pondéré4 sommets, 5 arêtes

Le graphe de l'énoncé. Deux routes mènent de S à T, et la plus courte en nombre d'arêtes n'est pas la moins coûteuse.

Dijkstra depuis S :

traité S : A à 2, B à 5
traité A (le plus petit) : B passe de 5 à $2 + 1 = 3$ (par A), T à $2 + 7 = 9$
traité B : T passe de 9 à $3 + 3 = 6$ (par B)

Distance 6, par S → A → B → T.

Graphe non orienté et pondéré4 sommets, 5 arêteschemin mis en évidence

Le plus court chemin, en évidence. Trois arêtes pour un coût de 6, là où la route S, A, T n'en demandait que deux pour un coût de 9.

Le chemin S, A, T est plus court en nombre d'arêtes et pourtant plus coûteux : c'est tout l'intérêt de l'algorithme, et la raison pour laquelle le dessin seul ne suffit jamais à répondre.

La méthode sur feuille

Redessiner le graphe proprement, quitte à déplacer les sommets pour éviter que les arêtes se croisent. La moitié des questions se lit sur un bon dessin.
Calculer tous les degrés et vérifier le lemme des poignées de main : c'est un contrôle immédiat de la lecture de l'énoncé.
Pour une question de parcours eulérien, compter les sommets de degré impair : 0 → circuit, 2 → parcours, sinon impossible.
Pour Dijkstra, faire un tableau avec une ligne par étape et noter les prédécesseurs.
Pour une coloration, encadrer : une clique pour le minorant, $\Delta + 1$ pour le majorant, puis exhiber une coloration qui atteint le minorant.
Pour un nombre de chemins, penser aux puissances de la matrice d'adjacence.

Pour aller plus loin

Ce chapitre tient en un seul endroit ce qu'il faut savoir calculer à la main. Le parcours Théorie des graphes reprend les mêmes notions en neuf chapitres, avec les figures, les parcours animés pas à pas, les arbres couvrants, les flots et les couplages. Il vaut la peine d'y aller voir si un raisonnement d'ici résiste : c'est le même objet, montré plus lentement.

Vérification rapideon peut se reprendre

1.Dans un graphe non orienté, que vaut la somme de tous les degrés ?

2.Dans le graphe de référence, le coefficient (C, D) de $M^2$ vaut 0, alors que C et D sont voisins. Pourquoi ?

3.Un graphe connexe possède exactement deux sommets de degré impair. Que peut-on dire ?

4.Un graphe contient un triangle. Que peut-on affirmer sur son nombre chromatique χ ?

Synthèse

Un graphe ne retient que « qui est relié à qui ». Le dessin n'a aucune importance.
Lemme des poignées de main : $\sum \deg = 2 |E|$ . Le nombre de sommets de degré impair est toujours pair.
Matrice d'adjacence : symétrique si le graphe est non orienté ; la somme d'une ligne donne le degré.
Le coefficient (i,j) de $M^k$ est le nombre de chemins de longueur k de i à j.
Arbre = connexe et sans cycle ⟺ connexe avec $n - 1$ arêtes. Une seule chaîne entre deux sommets.
DAG = orienté sans cycle → modélise les dépendances, admet un tri topologique.
Dijkstra : poids positifs, on fige à chaque étape le sommet non traité le plus proche, et on note les prédécesseurs.
Euler, sur un graphe connexe : circuit ⟺ tous les degrés pairs ; parcours ⟺ exactement deux degrés impairs.
Coloration : taille de la plus grande clique ⩽ $\chi$ ⩽ $\Delta + 1$ . Et $\chi \leq 2$ ⟺ biparti ⟺ aucun cycle de longueur impaire.

Définitions

Le graphe de référence du chapitre

Degrés

Chemins, cycles, connexité

Arbres

Graphes orientés sans cycle (DAG)

Représentations

Liste d'adjacence

Matrice d'adjacence

Puissances de la matrice d'adjacence

Plus court chemin : l'algorithme de Dijkstra

Parcours eulériens

Coloration

Les graphes bipartis

Les degrés, autant de fois qu'il faut

Où la démarche dérape

À calculer soi-même

Exercices type

La méthode sur feuille

Synthèse

Mettre en pratique

Plus court chemin : l'algorithme de Dijkstra