Le vocabulaire des graphes

Un graphe, c'est des points et des traits. Toute la théorie tient dans cette phrase, et c'est précisément ce qui la rend puissante : des problèmes qui n'ont rien à voir entre eux, un réseau électrique, un emploi du temps, des dépendances entre paquets logiciels, un plan de métro, deviennent le même objet dès qu'on les dessine ainsi. Ce chapitre pose le vocabulaire, et surtout le réflexe : reconnaître qu'un problème est un problème de graphe.

Des points et des traits

Définition

Un graphe $G = (V, E)$ est la donnée d'un ensemble fini de sommets $V$ et d'un ensemble $E$ de paires de sommets, appelées arêtes.

On note $n = |V|$ l'ordre du graphe et $m = |E|$ sa taille.

Une paire réunit deux sommets distincts, et un ensemble ne contient pas deux fois la même paire : cette définition exclut donc les boucles et les arêtes multiples.

Voici un graphe à six sommets et sept arêtes. Il n'a aucune signification : c'est un objet mathématique, et c'est tout l'intérêt.

Graphe non orienté6 sommets, 7 arêtes

Six sommets, sept arêtes. Ce graphe reviendra tout au long du chapitre.

Le dessin n'est pas le graphe

La position des points sur la page ne fait pas partie de la définition. Le même graphe peut être dessiné de mille façons, avec ou sans croisements, et deux dessins très différents peuvent représenter exactement le même objet.
Ce qui compte, et cela seul : qui est relié à qui. Pour comparer deux graphes, ne jamais comparer les dessins, mais les voisinages.

Où tout a commencé

La théorie des graphes naît en 1735 d'une question de promeneur : peut-on traverser les sept ponts de Königsberg une fois chacun ? Euler y répond sans essayer un seul itinéraire, en comptant les ponts de chaque quartier. Le chapitre de mathématiques sur les graphes déroule ce raisonnement, qui sert encore à organiser la tournée d'un facteur ou d'un camion de collecte, et pose à la main ce que ce parcours met ensuite en algorithmes.

Ce qu'on modélise

Le travail utile n'est pas de manipuler des graphes, c'est de voir qu'un problème en est un. Deux questions suffisent.

Question	Réponse pour un plan de métro	Réponse pour un emploi du temps
Qu'est-ce qu'un sommet ?	une station	un cours à placer
Qu'est-ce qu'une arête ?	deux stations voisines sur une ligne	deux cours qui ne peuvent pas être simultanés

Une fois ces deux réponses écrites, le problème change de nature : « trouver le trajet le plus court » devient un plus court chemin, « faire tenir l'emploi du temps en un minimum de créneaux » devient une coloration. Les algorithmes existent déjà ; c'est la traduction qui demande du soin.

Le test de la relation

Pour savoir si l'arête est la bonne, l'énoncer à haute voix sous forme de phrase : « il y a une arête entre u et v si … ».
Si la phrase est difficile à finir, c'est que le modèle n'est pas au point. Si elle contient un « ou », il y a probablement deux graphes différents.

Orienté ou non, pondéré ou non

Définitions

Dans un graphe non orienté, l'arête $\{u, v\}$ est la même que $\{v, u\}$  : la relation est symétrique.

Dans un graphe orienté, on parle d'arcs $(u, v)$ , et $(u, v)$ ne vaut pas $(v, u)$ .

Un graphe est pondéré quand chaque arête porte un nombre : distance, durée, coût, capacité.

Graphe orienté5 sommets, 5 arcs

Les étapes d'un projet : chaque flèche va d'une étape à celle qui peut la suivre.

Ce graphe orienté dit quelque chose qu'un graphe non orienté ne saurait pas dire : on revient des tests au codage, mais jamais de la livraison aux tests, ni de la conception à l'analyse. La flèche Tests -> Livraison n'a pas de symétrique, et c'est justement l'information intéressante. La paire Codage -> Tests et Tests -> Codage, elle, dit la boucle de correction : un graphe non orienté la réduirait à une arête ordinaire, sans pouvoir dire que c'est la seule étape où l'on revient en arrière.

La question à se poser en premier

La relation est-elle symétrique ?
« Ces deux tâches se chevauchent » l'est : si A chevauche B, alors B chevauche A, donc graphe non orienté.
« Cette tâche doit finir avant que celle-là commence » ne l'est pas, donc graphe orienté.
Se tromper ici oblige à tout reprendre plus tard, car la moitié des algorithmes ne s'appliquent qu'à l'un des deux cas.

La définition du début décrit un graphe simple : aucune boucle (une arête d'un sommet vers lui-même) et au plus une arête entre deux mêmes sommets. Certains problèmes demandent davantage : deux câbles en parallèle entre deux serveurs, deux ponts entre la même rive et la même île à Königsberg. On parle alors de multigraphe, où les arêtes forment une liste dans laquelle une même paire peut revenir. Sauf mention contraire, tous les graphes de ce module sont simples.

Le degré

Définition

Le degré $\deg(v)$ d'un sommet est le nombre d'arêtes qui le touchent ; dans un graphe simple, c'est aussi son nombre de voisins.

Dans un graphe orienté, on distingue le degré entrant $\deg^-(v)$ , le nombre d'arcs qui arrivent en $v$ , et le degré sortant $\deg^+(v)$ , le nombre d'arcs qui en partent.

Sur le graphe ci-dessous, lire les degrés directement sur le dessin : compter les traits qui touchent chaque point.

Graphe non orienté6 sommets, 7 arêtes

Le graphe du début du chapitre. Le degré d'un sommet se lit en comptant les traits qui le touchent.

A et B ont degré 2, E et F aussi, C et D ont degré 3. La somme vaut $2 + 2 + 3 + 3 + 2 + 2 = 14$ , soit exactement deux fois les sept arêtes. Ce n'est pas une coïncidence.

Lemme des poignées de main

\sum_{v \in V} \deg(v) = 2m

Chaque arête a deux extrémités, donc elle est comptée deux fois quand on additionne les degrés.

La conséquence, qui sert tout le temps. La somme des degrés est paire. Donc le nombre de sommets de degré impair est lui-même pair.
Dans toute assemblée, le nombre de personnes ayant serré un nombre impair de mains est pair : d'où le nom du lemme. C'est le premier outil pour prouver qu'un graphe décrit par un énoncé ne peut pas exister.

Un raisonnement d'impossibilité, en trois lignes

« Existe-t-il un graphe à 5 sommets, chacun de degré 3 ? »
La somme des degrés vaudrait

5 \times 3 = 15

, qui devrait être égale à

2m

, donc être paire. Or 15 est impair. Un tel graphe n'existe pas, et il est inutile de chercher à le dessiner.

main.py

Sortie

>_ Prêt à exécuter…

Nécessaire n'est pas suffisant

Passer le test ne garantit pas que le graphe existe. Prendre [3, 3, 1, 1] : la somme vaut 8, elle est paire, et aucun degré ne dépasse

n - 1 = 3

. Pourtant ce graphe est impossible.
Dérouler : les deux sommets de degré 3 doivent être reliés à tous les autres, donc chacun des deux derniers sommets reçoit déjà deux arêtes, alors qu'ils devraient être de degré 1.
Le test de parité sert à éliminer vite. Pour conclure qu'un graphe existe, il faut l'exhiber, ou invoquer le théorème d'Erdős-Gallai, qui donne la condition exacte.

Vérification rapideon peut se reprendre

Sept serveurs sont reliés chacun à exactement quatre autres par un câble direct. Combien de câbles ?

Se déplacer dans un graphe

Définitions

Un chemin est une suite de sommets dont chacun est relié au suivant par une arête. Sa longueur est le nombre d'arêtes qu'il emprunte (une arête empruntée deux fois compte deux fois), et non son nombre de sommets : le chemin A, C, D, F de la figure ci-dessous a quatre sommets et une longueur de 3. Il est élémentaire s'il ne repasse par aucun sommet.

Un cycle est un chemin d'au moins une arête qui revient à son point de départ sans repasser par une arête. Il est élémentaire s'il ne repasse par aucun sommet avant de revenir au départ.

La distance $\mathrm{dist}(u, v)$ entre deux sommets est la longueur du plus court chemin qui les relie ; elle est infinie s'il n'en existe aucun.

Un graphe est connexe si toute paire de sommets est reliée par un chemin. Sinon il se décompose en composantes connexes.

Certains ouvrages disent chaîne dans un graphe non orienté et réservent « chemin » aux graphes orientés. Ce parcours dit chemin dans les deux cas, comme le chapitre de mathématiques sur les graphes : le mot ne suppose aucune flèche, et le texte précise quand le sens compte.

Le chemin mis en évidence ci-dessous va de A à F en passant par C et D. Il est élémentaire, aucun sommet n'y figure deux fois, et sa longueur vaut 3. Aucun chemin plus court ne relie A à F : $\mathrm{dist}(A, F) = 3$ .

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

Le chemin A, C, D, F : quatre sommets, trois arêtes, donc une longueur de 3.

Dans un graphe orienté, un chemin doit suivre le sens des flèches, et un chemin qui revient à son point de départ en les suivant s'appelle un circuit ; le mot cycle reste réservé au graphe non orienté. Dans le graphe des étapes d'un projet, plus haut, Codage -> Tests -> Codage est un circuit.

La connexité se dédouble aussi : un graphe orienté peut être d'un seul tenant sans qu'on puisse aller de tout sommet à tout autre en suivant les flèches. Le graphe des étapes d'un projet en est un exemple : rien ne repart de Livraison. Le chapitre sur les graphes orientés appellera fortement connexe celui où c'est possible.

Connexe ne veut pas dire complet

Un graphe connexe garantit seulement qu'un trajet existe entre deux sommets quelconques. Il peut être très long.
Un graphe complet, lui, relie directement chaque paire. Confondre les deux mène à des erreurs de comptage : un graphe connexe peut n'avoir que

n - 1

arêtes, un graphe complet en a

\frac{n(n-1)}{2}

Ce graphe-ci n'est pas connexe : il a deux composantes, A, B, C d'un côté et D, E, F de l'autre, et aucun chemin ne mène de A à E.

Graphe non orienté6 sommets, 5 arêtes

Deux composantes connexes : aucun chemin ne relie un sommet de gauche à un sommet de droite.

Les graphes qu'il faut reconnaître

Cinq formes reviennent constamment. Les reconnaître d'un coup d'œil fait gagner beaucoup de temps, parce que chacune a des propriétés connues.

Le graphe complet $K_n$  : toutes les paires sont reliées. Il a $\frac{n(n-1)}{2}$ arêtes et tous ses sommets sont de degré $n - 1$ .

Graphe non orienté4 sommets, 6 arêtes

Le graphe complet K4 : six arêtes, tous les sommets de degré 3.

Le cycle $C_n$ , pour $n \geq 3$  : $n$ sommets, $n$ arêtes, tous de degré 2.

Graphe non orienté5 sommets, 5 arêtes

Le cycle C5 : cinq sommets, cinq arêtes, tous de degré 2.

L'arbre : connexe et sans cycle. Il a exactement $n - 1$ arêtes, et il existe un seul chemin élémentaire entre deux sommets quelconques.

Graphe non orienté6 sommets, 5 arêtes

Un arbre à six sommets et cinq arêtes : connexe, sans cycle, un seul chemin élémentaire entre deux sommets.

Le chemin $P_n$  : $n$ sommets alignés et $n - 1$ arêtes ; les deux extrémités sont de degré 1, les autres de degré 2. C'est l'arbre le plus simple, et celui qui pousse un parcours en profondeur à s'enfoncer le plus loin. Le même mot désignait plus haut une suite de sommets : ici, c'est un graphe entier qui a cette forme.

Graphe non orienté5 sommets, 4 arêtes

Le chemin P5 : cinq sommets, quatre arêtes, deux extrémités de degré 1.

Le graphe biparti : les sommets se répartissent en deux groupes, et toute arête va d'un groupe à l'autre, jamais à l'intérieur. Ici, trois étudiants et trois matières, avec une arête quand l'étudiant suit la matière : une arête relie toujours une personne à une matière, jamais deux personnes ni deux matières. C'est la forme de tous les problèmes d'affectation (personnes et postes, tâches et machines). Les deux groupes se lisent aux couleurs.

Graphe non orienté6 sommets, 6 arêtes

Les étudiants d'une couleur, les matières de l'autre : aucune arête ne relie deux sommets de même couleur.

Le critère qui caractérise les bipartis. Un graphe est biparti si et seulement s'il ne contient aucun cycle de longueur impaire.
C'est le genre d'équivalence qui rend un théorème utile : pour prouver qu'un graphe n'est pas biparti, il suffit d'exhiber un triangle, ou n'importe quel cycle impair. Le chapitre sur les parcours en donnera le test algorithmique.

Vérification rapideon peut se reprendre

1.« Ce graphe est connexe » signifie…

2.Pour prouver qu'un graphe n'est pas biparti, il suffit d'exhiber…

Sous-graphes et cliques

Définition

Le sous-graphe induit par une partie $W \subseteq V$ est le graphe formé de $W$ et de toutes les arêtes de $G$ dont les deux extrémités sont dans $W$ .

Le mot induit est important : on choisit les sommets, pas les arêtes. Elles viennent avec. Sur le graphe du début du chapitre, le sous-graphe induit par C, D et E a deux arêtes, C-D et D-E : l'arête D-F ne vient pas, puisque F n'a pas été choisi. Garder C, D, E avec la seule arête C-D donnerait un sous-graphe, mais pas le sous-graphe induit.

Définition

Une clique est un ensemble de sommets deux à deux adjacents. On note $\omega(G)$ la taille de la plus grande clique de $G$ .

Le triangle A, B, C ci-dessous est une clique de taille 3 : chacun des trois est relié aux deux autres. D, E, F en forme une seconde, et aucune clique de taille 4 n'existe : $\omega(G) = 3$ .

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

La clique A, B, C, mise en évidence par ses trois arêtes. Le triangle D, E, F en est une autre.

La clique reviendra au chapitre sur la coloration : une clique de taille $k$ oblige à employer au moins $k$ couleurs, puisque ses sommets sont deux à deux voisins. Quand on trouve une coloration qui n'en emploie pas davantage, elle est prouvée optimale. Mais cela n'arrive pas toujours : le cycle $C_5$ dessiné plus haut n'a aucun triangle, sa plus grande clique est de taille 2, et il demande pourtant trois couleurs.

Mettre en pratique

Un graphe a 6 sommets, tous de degré 3. Combien d'arêtes ?

Par le lemme des poignées de main, $\sum \deg(v) = 2m$ .

Ici $\sum \deg(v) = 6 \times 3 = 18$ , donc $2m = 18$ et $m = 9$ .

Vérification de cohérence : 9 arêtes pour 6 sommets, alors que le graphe complet $K_6$ en aurait $\frac{6 \times 5}{2} = 15$ . C'est donc possible, et un tel graphe existe effectivement, par exemple le graphe biparti complet $K_{3,3}$ , où chacun de trois sommets est relié à chacun de trois autres.

Peut-on avoir un graphe à 7 sommets dont les degrés sont 6, 6, 6, 3, 3, 2, 1 ?

Non. La somme vaut $6+6+6+3+3+2+1 = 27$ , qui est impair. Or la somme des degrés vaut toujours $2m$ , donc elle est paire.

Aucun graphe ne peut avoir cette suite de degrés, et il est inutile d'essayer de le construire.

Noter au passage que les autres contrôles passaient : aucun degré ne dépasse $n - 1 = 6$ . La parité est donc bien le test qui tranche ici.

Quelle est la différence entre un chemin, un cycle et un circuit ?

Un chemin est une suite de sommets dont chacun est relié au suivant ; dans un graphe orienté, il doit en plus suivre le sens des arcs.

Un cycle est un chemin fermé d'un graphe non orienté qui ne repasse par aucune arête. Sans cette précision, l'aller-retour A B A serait un cycle, et aucun arbre ne pourrait avoir la moindre arête.

Un circuit est un chemin fermé d'un graphe orienté, qui suit le sens des arcs.

La distinction compte dès qu'il y a des flèches. Pouvoir aller de u à v en ignorant le sens des flèches ne dit rien sur l'existence d'un chemin qui les suit : elles peuvent toutes pointer dans le mauvais sens. Et un graphe orienté peut former un cycle, si l'on oublie les flèches, sans contenir aucun circuit : A -> B, B -> C, A -> C en est l'exemple le plus court.

Comment prouver qu'un graphe n'est pas biparti ?

En exhibant un cycle de longueur impaire.

Un graphe est biparti si et seulement si tous ses cycles sont de longueur paire, donc un seul cycle impair suffit à conclure. Le plus court à trouver est un triangle.

Réciproquement, pour prouver qu'un graphe est biparti, il faut exhiber la partition en deux groupes et vérifier qu'aucune arête ne reste à l'intérieur d'un groupe. Le chapitre sur les parcours montrera comment un parcours en largeur le fait automatiquement.

Un graphe connexe à 10 sommets peut-il avoir 8 arêtes ?

Non. Un graphe connexe à $n$ sommets a au moins $n - 1$ arêtes, donc au moins 9 ici.

L'intuition : partir des $n$ sommets sans aucune arête, soit $n$ composantes. Chaque arête ajoutée relie au mieux deux composantes jusque-là séparées, et fait donc baisser leur nombre d'au plus un. Pour descendre de $n$ composantes à une seule, il faut au moins $n - 1$ arêtes : avec 8 arêtes, 10 sommets gardent au moins deux composantes.

Le cas d'égalité, exactement $n - 1$ arêtes, correspond aux arbres : connexes et sans le moindre cycle.

Pourquoi dit-on qu'un dessin ne définit pas un graphe ?

Parce que seule la relation d'adjacence compte. Déplacer un point sur la feuille, croiser ou décroiser deux traits, ne change pas le graphe.

Deux dessins d'apparence très différente peuvent représenter le même graphe : on dit qu'ils sont isomorphes, c'est-à-dire qu'il existe une correspondance entre leurs sommets qui préserve les arêtes.

Conséquence pratique : deux graphes qui diffèrent par un invariant (nombre de sommets, d'arêtes, suite des degrés, présence d'un triangle) sont différents, quel que soit leur dessin. La réciproque est fausse : un cycle à huit sommets et deux carrés disjoints ont huit sommets, huit arêtes, tous leurs degrés égaux à 2 et aucun triangle, sans être le même graphe, puisque le premier est d'un seul tenant et pas le second. Pour prouver que deux graphes sont les mêmes, il faut exhiber la correspondance entre leurs sommets.

Des points et des traits

Ce qu'on modélise

Orienté ou non, pondéré ou non

Le degré

Se déplacer dans un graphe

Les graphes qu'il faut reconnaître

Sous-graphes et cliques

Mettre en pratique

Dans la bibliothèque d'exercices