Le vocabulaire des graphes
Ce que ce chapitre apporte
- Traduire un énoncé en graphe : que sont les sommets, que sont les arêtes.
- Décider si le graphe est orienté, pondéré, simple.
- Calculer un degré, appliquer le lemme des poignées de main.
- Reconnaître les graphes remarquables : complet, cycle, chaîne, biparti, arbre.
- Employer correctement chaîne, cycle, connexité, sous-graphe induit, clique.
- Prouver qu'un graphe donné ne peut pas exister.
Des points et des traits
Un graphe est la donnée d'un ensemble fini de sommets et d'un ensemble de paires de sommets, appelées arêtes.
On note l'ordre du graphe et sa taille.
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.
Ce qui compte, et cela seul : qui est relié à qui. Quand vous comparez deux graphes, ne comparez jamais les dessins, comparez les voisinages.
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.
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 », vous avez probablement deux graphes différents.
Orienté ou non, pondéré ou non
Dans un graphe non orienté, l'arête est la même que : la relation est symétrique.
Dans un graphe orienté, on parle d'arcs , et ne vaut pas .
Un graphe est pondéré quand chaque arête porte un nombre : distance, durée, coût, capacité.
Ce graphe orienté dit quelque chose qu'un graphe non orienté ne saurait pas dire : on retourne des tests au codage, mais jamais l'inverse. La flèche Tests -> Codage n'a pas de symétrique, et c'est justement l'information intéressante.
« 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.
Un graphe est simple s'il n'a ni boucle (une arête d'un sommet vers lui-même) ni arête multiple entre deux mêmes sommets. Sauf mention contraire, tous les graphes de ce module sont simples.
Le degré
Le degré d'un sommet est son nombre de voisins.
Dans un graphe orienté, on distingue le degré entrant et le degré sortant .
Sur le graphe ci-dessous, lisez les degrés directement sur le dessin : comptez les traits qui touchent chaque point.
A et B ont degré 2, E et F aussi, C et D ont degré 3. La somme vaut , soit exactement deux fois les sept arêtes. Ce n'est pas une coïncidence.
Chaque arête a deux extrémités, donc elle est comptée deux fois quand on additionne les degrés.
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.
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.
[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éroulez : 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.
Se déplacer dans un graphe
Une chaîne est une suite de sommets consécutivement reliés. Elle est élémentaire si elle ne répète aucun sommet.
Un cycle est une chaîne qui revient à son point de départ sans répéter d'arête.
Un graphe est connexe si toute paire de sommets est reliée par une chaîne. Sinon il se décompose en composantes connexes.
La chaîne mise en évidence ci-dessous va de A à F en passant par C et D. Elle est élémentaire : aucun sommet n'y figure deux fois.
Dans un graphe orienté, les mots changent : on parle de chemin et de circuit, et il faut suivre le sens des flèches.
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, et aucun trajet ne mène de A à E.
1.Un énoncé décrit un graphe à 5 sommets, tous de degré 3. Que peut-on dire ?
2.« Ce graphe est connexe » signifie…
3.Pour prouver qu'un graphe n'est pas biparti, il suffit d'exhiber…
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 : toutes les paires sont reliées. Il a arêtes et tous ses sommets sont de degré .
Le cycle : sommets, arêtes, tous de degré 2.
L'arbre : connexe et sans cycle. Il a exactement arêtes, et il existe une seule chaîne élémentaire entre deux sommets quelconques.
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. Les deux groupes se lisent ici aux couleurs.
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.
Sous-graphes et cliques
Le sous-graphe induit par une partie est le graphe formé de et de toutes les arêtes de dont les deux extrémités sont dans .
Le mot induit est important : on choisit les sommets, pas les arêtes. Elles viennent avec.
Une clique est un ensemble de sommets deux à deux adjacents. On note la taille de la plus grande clique de .
Le triangle A, B, C ci-dessous est une clique de taille 3 : chacun des trois est relié aux deux autres.
La clique reviendra au chapitre sur la coloration : c'est elle qui donne la borne inférieure du nombre de couleurs nécessaires, et donc la façon de prouver qu'une solution est optimale.
Exercices type
Un graphe a 6 sommets, tous de degré 3. Combien d'arêtes ?
Par le lemme des poignées de main, .
Ici , donc et .
Vérification de cohérence : 9 arêtes pour 6 sommets, alors que le graphe complet en aurait . C'est donc possible, et un tel graphe existe effectivement, par exemple le graphe biparti complet .
Peut-on avoir un graphe à 7 sommets dont les degrés sont 6, 6, 6, 3, 3, 2, 1 ?
Non. La somme vaut , qui est impair. Or la somme des degrés vaut toujours , donc elle est paire.
Aucun graphe ne peut avoir cette suite de degrés, et il est inutile d'essayer de le construire.
Notez au passage que les autres contrôles passaient : aucun degré ne dépasse . La parité est donc bien le test qui tranche ici.
Quelle est la différence entre une chaîne et un cycle, entre un chemin et un circuit ?
Chaîne et cycle sont les mots du graphe non orienté : une chaîne est une suite de sommets consécutivement reliés, un cycle est une chaîne fermée.
Chemin et circuit sont les mots du graphe orienté : il faut alors suivre le sens des arcs.
La distinction n'est pas cosmétique. Dans un graphe orienté, l'existence d'une chaîne de u vers v ne dit rien sur l'existence d'un chemin : les flèches peuvent toutes pointer dans le mauvais sens.
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 à sommets a au moins arêtes, donc au moins 9 ici.
L'intuition : construisez le graphe en ajoutant les sommets un par un. Chaque nouveau sommet doit être relié à ce qui existe déjà, sinon il forme une composante à part. Il faut donc au minimum une arête par sommet ajouté après le premier.
Le cas d'égalité, exactement 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 en devoir : pour comparer deux graphes, on compare des invariants (nombre de sommets, d'arêtes, suite des degrés, présence d'un triangle), jamais l'allure du dessin.
La méthode
- Écris d'abord les deux phrases : « un sommet est … », « il y a une arête entre u et v si … ».
- Demande-toi si la relation est symétrique : cela décide orienté ou non.
- Compte les arêtes par les degrés quand l'énoncé donne les degrés, pas l'inverse.
- Teste la parité avant de chercher à construire un graphe décrit par ses degrés.
- Cherche un cycle impair pour réfuter le caractère biparti.
- Ne compare jamais deux dessins, compare des invariants.
- Nomme la forme quand tu la reconnais : complet, cycle, arbre, biparti. Elle apporte ses propriétés avec elle.
En résumé
- Un graphe est un ensemble de sommets et un ensemble de paires de sommets.
- Le dessin ne fait pas partie de la définition : seule l'adjacence compte.
- Orienté ou non se décide en demandant si la relation est symétrique.
- Lemme des poignées de main : , donc le nombre de sommets de degré impair est pair.
- Une chaîne relie, un cycle revient, un graphe connexe relie toute paire.
- Un graphe connexe a au moins arêtes ; avec exactement , c'est un arbre.
- a arêtes, en a , tous de degré 2.
- Un graphe est biparti si et seulement s'il n'a aucun cycle impair.
- Une clique est un ensemble de sommets deux à deux adjacents ; sa taille se note .
Et ensuite ? Un graphe dessiné au tableau doit devenir un objet en mémoire. Le chapitre suivant compare les trois façons de le représenter, et ce que chacune coûte.