Exercices corrigés : la théorie des graphes (math CST, secondaire 5)

a) L'ORDRE d'un graphe est son nombre de sommets : ici $6$, les relais $A$, $B$, $C$, $D$, $E$ et $F$. On compte ensuite les arêtes une par une, en suivant d'abord le contour puis les liaisons intérieures : $AB$, $BC$, $CD$, $DE$, $EF$ et $FA$ pour le tour, puis $BE$ et $AD$ qui traversent. Le graphe possède donc $8$ arêtes. Le comptage des arêtes est la première source d'erreur du chapitre : on en oublie une, ou bien on prend un croisement de traits pour un sommet. Le point où $BE$ et $AD$ se croisent au milieu de la figure n'est PAS un relais, aucun point n'y est tracé, et le graphe garde bien six sommets.

b) On compte les arêtes qui touchent chaque sommet. $\deg(A)=3$, vers $B$, $F$ et $D$ ; $\deg(B)=3$, vers $A$, $C$ et $E$ ; $\deg(C)=2$, vers $B$ et $D$ ; $\deg(D)=3$, vers $C$, $E$ et $A$ ; $\deg(E)=3$, vers $D$, $F$ et $B$ ; $\deg(F)=2$, vers $E$ et $A$. La somme vaut $3+3+2+3+3+2=16$, soit exactement le DOUBLE des $8$ arêtes. Ce n'est pas une coïncidence : chaque arête a deux extrémités, donc elle est comptée deux fois dans la somme des degrés. On retient la relation « somme des degrés $=2\times$ nombre d'arêtes », et on s'en sert comme vérification : une somme impaire signale toujours une erreur de comptage.

c) Le graphe est SIMPLE : aucune boucle, c'est-à-dire aucune arête reliant un sommet à lui-même, et aucune arête multiple, c'est-à-dire jamais deux liaisons distinctes entre les deux mêmes relais. Il est CONNEXE : depuis n'importe quel sommet on atteint tous les autres, par exemple le tour $A$, $B$, $C$, $D$, $E$, $F$ les visite tous. Il n'est PAS COMPLET : dans un graphe complet d'ordre $6$, chaque sommet serait relié aux cinq autres, donc de degré $5$, et il y aurait $\dfrac{6\times 5}{2}=15$ arêtes. Ici les degrés valent au plus $3$ et il n'y a que $8$ arêtes ; $C$ et $F$, par exemple, ne sont pas reliés.

d) Une chaîne de longueur $3$ est une suite de trois arêtes bout à bout. De $F$ à $C$ : $F$, $A$, $B$, $C$, qui emprunte $FA$, $AB$ et $BC$, trois arêtes qui existent bien sur la figure. La LONGUEUR d'une chaîne se compte en arêtes, jamais en sommets : celle-ci passe par quatre sommets et reste de longueur $3$. Un cycle de longueur $4$ est une chaîne fermée de quatre arêtes qui ne reprend jamais la même arête : $A$, $B$, $E$, $F$, $A$ convient, avec $AB$, $BE$, $EF$ et $FA$.

a) On compte : $\deg(A)=3$, vers $B$, $D$ et $C$ ; $\deg(B)=3$, vers $A$, $C$ et $D$ ; $\deg(C)=4$, vers $B$, $D$, $E$ et $A$ ; $\deg(D)=4$, vers $C$, $A$, $E$ et $B$ ; $\deg(E)=2$, vers $D$ et $C$. La somme vaut $3+3+4+4+2=16$, soit deux fois les $8$ arêtes : le comptage est cohérent. Les sommets de degré IMPAIR sont $A$ et $B$, et il y en a exactement deux.

b) Une CHAÎNE eulérienne passe une fois et une seule par chaque arête, sans obligation de revenir au point de départ ; un CYCLE eulérien fait la même chose et revient au départ. Le critère ne regarde que les degrés impairs, dans un graphe connexe : aucun sommet impair, il existe un cycle eulérien ; exactement deux sommets impairs, il existe une chaîne eulérienne, et elle part obligatoirement de l'un des deux pour arriver à l'autre ; quatre sommets impairs ou plus, il n'existe ni chaîne ni cycle. Ici il y a exactement deux sommets impairs, $A$ et $B$ : la chaîne eulérienne existe, elle relie $A$ à $B$, et le cycle eulérien est impossible.

c) Une chaîne qui convient est $A$, $C$, $E$, $D$, $C$, $B$, $D$, $A$, $B$. Elle emprunte dans l'ordre $AC$, $CE$, $ED$, $DC$, $CB$, $BD$, $DA$ et $AB$ : ce sont bien les huit arêtes du graphe, chacune une seule fois. On vérifie de deux façons : la chaîne compte $9$ sommets écrits pour $8$ arêtes, ce qui est toujours le cas, et elle part d'un sommet impair pour arriver à l'autre. Remarquez qu'elle repasse par $C$ et par $D$ : c'est autorisé, une chaîne eulérienne interdit de reprendre une ARÊTE, pas de revisiter un sommet.

d) Il suffit d'ajouter une liaison directe entre les deux sommets impairs, donc une arête $AB$ supplémentaire, ou bien de retirer l'arête $AB$ existante. Dans les deux cas $A$ et $B$ changent de parité, plus aucun sommet n'a un degré impair, et le graphe possède alors un cycle eulérien. On peut le comprendre sans le critère : dans un cycle, chaque passage par un sommet consomme une arête pour y entrer et une autre pour en sortir, donc les arêtes de chaque sommet se regroupent par paires et le degré ne peut pas être impair.

a) Les degrés valent $\deg(A)=2$, $\deg(B)=2$, $\deg(C)=4$, $\deg(D)=2$ et $\deg(E)=2$, de somme $12$, soit deux fois les $6$ arêtes. Aucun degré n'est impair, donc le critère garantit l'existence d'un cycle eulérien. En voici un : $A$, $B$, $C$, $D$, $E$, $C$, $A$. Il emprunte $AB$, $BC$, $CD$, $DE$, $EC$ et $CA$, c'est-à-dire les six arêtes, chacune une seule fois, et il revient bien en $A$.

b) Un cycle hamiltonien passe une fois et une seule par chacun des CINQ sommets, puis revient au départ. Le sommet $C$ est un sommet de coupure : si on le retire, le graphe se casse en deux morceaux sans aucune liaison entre eux, l'arête $AB$ d'un côté et l'arête $DE$ de l'autre. Pour visiter $A$ et $B$ puis $D$ et $E$, il faut donc passer par $C$ ; et pour revenir au point de départ, il faut y repasser une seconde fois. Un cycle hamiltonien devrait alors utiliser deux fois le sommet $C$, ce que sa définition interdit. Il n'en existe donc aucun.

c) Oui. La chaîne $A$, $B$, $C$, $D$, $E$ passe une fois et une seule par les cinq sommets et emprunte les arêtes $AB$, $BC$, $CD$ et $DE$, qui existent toutes. Elle est hamiltonienne, mais elle n'est pas fermée : elle part de $A$ et s'arrête en $E$, ce qui est exactement ce que la partie b) rendait obligatoire. Le sommet de coupure interdit le cycle, pas la chaîne.

d) Un parcours EULÉRIEN passe par toutes les ARÊTES, un parcours HAMILTONIEN passe par tous les SOMMETS. C'est le point qui coûte le plus de points en évaluation, parce que les deux mots se ressemblent alors que les deux problèmes n'ont rien à voir : ce graphe possède un cycle eulérien et aucun cycle hamiltonien, et il existe des graphes qui font exactement l'inverse. Le réflexe à prendre est de relire l'énoncé plutôt que la figure : s'il parle de rues à déneiger ou de câbles à inspecter, ce sont des arêtes, donc de l'eulérien ; s'il parle de villes à visiter ou de clients à livrer, ce sont des sommets, donc du hamiltonien.

a) Il en faut $3$. Deux couleurs ne suffisent pas : en alternant sur le cycle, $S_1$ prend la couleur $1$, $S_2$ la couleur $2$, $S_3$ la couleur $1$, $S_4$ la couleur $2$, et arrive $S_5$, voisin de $S_4$ qui porte la couleur $2$ ET de $S_1$ qui porte la couleur $1$ : les deux couleurs lui sont interdites. Ce blocage vient de la parité, et de rien d'autre : un cycle de longueur PAIRE se colore avec deux couleurs, un cycle de longueur IMPAIRE en exige trois, et $5$ est impair. Avec trois couleurs on y arrive, par exemple $1$, $2$, $1$, $2$, $3$.

b) Le moyeu $M$ est relié aux cinq sommets du cycle, donc sa couleur doit différer de toutes celles employées sur le cycle. Comme le cycle en consomme déjà $3$ au minimum, il en faut au moins $4$ en tout, et $4$ suffisent puisqu'il suffit de donner à $M$ une quatrième couleur. Le nombre chromatique vaut donc $4$. Une réponse de coloration se justifie toujours en deux temps, et c'est là que se joue la moitié des points : on exhibe une coloration à $4$ couleurs pour montrer que $4$ suffisent, et on montre que $3$ ne peuvent pas suffire pour montrer que $4$ sont nécessaires. Une coloration exhibée sans cette seconde moitié ne prouve rien.

c) Par exemple : $S_1$ rouge, $S_2$ bleu, $S_3$ rouge, $S_4$ bleu, $S_5$ vert, et $M$ jaune. On vérifie arête par arête. Sur le cycle : rouge-bleu, bleu-rouge, rouge-bleu, bleu-vert, vert-rouge, aucune paire identique. Sur les cinq arêtes du moyeu : jaune contre rouge, bleu, rouge, bleu et vert, jamais jaune contre jaune. Les dix arêtes sont donc correctement colorées.

d) Oui, il descend à $3$. Une fois $S_5$ retiré, il ne reste du cycle qu'une chaîne $S_1$, $S_2$, $S_3$, $S_4$, qui se colore en alternant deux couleurs, et le moyeu $M$ prend la troisième. On ne peut pas descendre à $2$, car le graphe contient encore le triangle $M$, $S_1$, $S_2$, dont les trois sommets sont deux à deux reliés. C'est la minoration la plus utile du chapitre : un triangle force $3$ couleurs, et plus généralement un groupe de $k$ sommets tous reliés entre eux force $k$ couleurs.

a) Le réseau cherché est un ARBRE : il relie les six quartiers, donc il est connexe, et il ne doit contenir aucun cycle, sinon on pourrait retirer une arête de ce cycle en gardant tout le monde relié et en payant moins cher. Or un arbre à $n$ sommets possède toujours exactement $n-1$ arêtes. Avec $6$ quartiers, le réseau comptera donc $5$ liaisons. Ce compte se pose AVANT tout calcul : il sert de garde-fou, une solution à $4$ ou à $6$ arêtes est fausse quel que soit son coût.

b) On trie les arêtes par coût croissant, puis on prend chacune si elle ne ferme pas un cycle avec celles déjà retenues. Le tri donne $EF$ à $3$, $FA$ à $4$, $AE$ à $5$, $CD$ à $6$, $BC$ à $7$, $DE$ à $9$, $BE$ à $10$, $AB$ à $12$, $CE$ à $15$. On prend $EF$ puis $FA$. On examine ensuite $AE$, qui fermerait le triangle $A$, $E$, $F$ : on l'ÉCARTE. On prend $CD$, puis $BC$, puis $DE$ qui relie enfin le groupe $\{B, C, D\}$ au groupe $\{A, E, F\}$. Cinq arêtes sont retenues, $EF$, $FA$, $CD$, $BC$ et $DE$, les six quartiers sont reliés, la construction s'arrête.

c) Le coût total vaut $3+4+6+7+9=29$, soit $29$ milliers de dollars. On vérifie de deux façons : cinq termes pour cinq arêtes, comme annoncé en a) ; et chacune des six lettres apparaît au moins une fois dans la liste $EF$, $FA$, $CD$, $BC$, $DE$, ce qui garantit qu'aucun quartier n'a été oublié. Aucun réseau reliant les six quartiers ne peut coûter moins de $29$, c'est ce que garantit la méthode des arêtes croissantes.

d) L'arête $AE$, de coût $5$, a été écartée. Au moment où on l'examine, $A$ et $E$ appartiennent déjà au même groupe, reliés par le chemin $A$, $F$, $E$ : l'ajouter créerait le cycle $A$, $E$, $F$, et un arbre n'a pas de cycle. Le point important est qu'on écarte ici une arête PEU CHÈRE sans état d'âme : le critère de rejet n'est jamais le coût, c'est la création d'un cycle. L'erreur classique consiste à prendre $AE$ parce que $5$ est petit, et à se retrouver avec six arêtes pour six sommets, donc avec un cycle et une facture inutilement plus lourde.

a) On avance de proche en proche depuis $A$, en notant pour chaque sommet la plus petite durée connue pour l'atteindre. Depuis $A$ : $F$ à $4$, $E$ à $5$, $B$ à $12$. En passant par $F$ on atteindrait $E$ en $4+3=7$, ce qui est pire que $5$ : on garde $5$. Depuis $E$ : $D$ à $5+9=14$, $B$ à $5+10=15$ donc on garde $12$, et $C$ à $5+15=20$. Depuis $B$ : $C$ à $12+7=19$, ce qui améliore $20$. Depuis $D$ : $C$ à $14+6=20$, sans amélioration. La plus petite durée pour $C$ est donc de $19$ minutes, par la chaîne $A$, $B$, $C$.

b) On teste d'autres chemins pour se convaincre : $A$, $E$, $C$ vaut $5+15=20$ ; $A$, $E$, $D$, $C$ vaut $5+9+6=20$ ; $A$, $F$, $E$, $D$, $C$ vaut $4+3+9+6=22$ ; $A$, $E$, $B$, $C$ vaut $5+10+7=22$. Toutes ces durées dépassent $19$, ce qui confirme le résultat. Cette vérification vaut des points en évaluation : une réponse de plus court chemin donnée sans aucune comparaison n'est pas justifiée, on a seulement montré qu'un chemin existe.

c) L'arbre de valeurs minimales retenait $EF$, $FA$, $CD$, $BC$ et $DE$. Il ne contient PAS l'arête $AB$. Pour aller de $A$ à $C$ en restant dessus, il faut donc suivre $A$, $F$, $E$, $D$, $C$, soit $4+3+9+6=22$ minutes, trois minutes de plus que le trajet optimal.

d) Ce sont deux problèmes différents, et l'un ne résout jamais l'autre. L'arbre de valeurs minimales rend minimale la somme TOTALE des liaisons construites : c'est la bonne réponse quand on installe des câbles ou des routes une fois pour toutes. La chaîne de poids minimal rend minimal le coût d'UN trajet entre deux sommets donnés : c'est la bonne réponse quand on circule sur un réseau qui existe déjà. Ici l'arbre coûte $29$ au total mais impose $22$ minutes de $A$ à $C$, alors que le meilleur trajet en demande $19$. Avant de calculer, il faut donc décider ce que l'énoncé veut rendre minimal, la somme de tout le réseau ou la longueur d'un seul parcours.

a) On suit les flèches en respectant leur sens. Trois chemins mènent de $D$ à $F$ : le chemin par $A$ puis $C$, de durée $5+4+2=11$ jours ; le chemin par $B$ puis $C$, de durée $3+6+2=11$ jours ; le chemin par $B$ puis $E$, de durée $3+7+3=13$ jours. Il n'y en a pas d'autre : depuis $D$ on ne peut partir que vers $A$ ou vers $B$, et depuis $C$ comme depuis $E$ on ne peut qu'aboutir à $F$.

b) La durée minimale du chantier est de $13$ jours, et le chemin critique est celui qui passe par $B$ puis $E$. Le raisonnement est celui qui surprend le plus dans ce chapitre : on cherche la durée MINIMALE du projet et on retient pourtant le chemin le PLUS LONG. C'est que le chantier n'est terminé que lorsque sa dernière tâche l'est ; tant que la suite la plus longue n'est pas achevée, le chantier ne l'est pas non plus, même si toutes les autres tâches sont bouclées depuis deux jours. Le plus long chemin impose donc le minimum réalisable.

c) La tâche de $D$ à $A$ appartient au chemin par $A$ puis $C$, qui dure $11$ jours alors que le chantier en dure $13$. Sa marge vaut $13-11=2$ jours. Concrètement, l'équipe qui l'exécute peut commencer avec deux jours de retard, ou prendre deux jours de plus que prévu, sans décaler la fin du chantier ; un troisième jour, en revanche, rendrait ce chemin critique à son tour. Les tâches du chemin critique, elles, ont une marge NULLE : le moindre retard sur l'une d'elles retarde la livraison d'autant. C'est ce que sert à repérer un chemin critique, savoir où un retard coûte cher et où il ne coûte rien.

d) Non, il n'en gagne que deux. En ramenant cette tâche à $3$ jours, le chemin par $B$ puis $E$ tombe à $3+3+3=9$ jours, mais les deux autres chemins n'ont pas bougé et durent toujours $11$ jours chacun. Le chantier dure donc $11$ jours au lieu de $13$ : le gain est de $2$ jours pour $4$ jours d'accélération payés. C'est le piège classique de l'optimisation d'un projet : accélérer une tâche critique déplace le problème, un autre chemin devient critique et bloque le gain. Pour descendre sous $11$ jours, il faudrait maintenant accélérer les DEUX nouveaux chemins critiques à la fois.

1) FAUX. Les deux notions ne portent pas sur les mêmes objets : l'eulérien parle des arêtes, l'hamiltonien des sommets. Le papillon de l'exercice 3 en est le contre-exemple : tous ses degrés sont pairs, donc il possède un cycle eulérien, et pourtant son sommet de coupure interdit tout cycle hamiltonien. Énoncé correct : un graphe connexe dont tous les sommets ont un degré pair possède un cycle eulérien, ce qui ne dit RIEN de l'existence d'un cycle hamiltonien.

2) FAUX. Chaque arête a deux extrémités, donc elle est comptée dans le degré de deux sommets. Énoncé correct : la somme des degrés vaut le DOUBLE du nombre d'arêtes. Deux conséquences à connaître : cette somme est toujours paire, et le nombre de sommets de degré impair est lui aussi toujours pair. C'est pourquoi on ne rencontre jamais un graphe ayant exactement trois sommets impairs, et pourquoi une réponse annonçant une somme de degrés impaire est fausse sans même regarder la figure.

3) FAUX. L'arbre de valeurs minimales rend minimal le coût TOTAL du réseau, pas la longueur d'un trajet particulier. L'exercice 6 le montre chiffres à l'appui : sur l'arbre, aller de $A$ à $C$ demande $22$ minutes, alors que le réseau complet permet $19$ minutes par $A$, $B$, $C$. Énoncé correct : l'arbre de valeurs minimales relie tous les sommets au coût total le plus faible ; le trajet le plus court entre deux sommets se cherche séparément, sur le graphe entier.

4) FAUX, et c'est l'affirmation qui coûte le plus cher en évaluation. Le chemin critique est le PLUS LONG chemin du réseau. La durée du projet est celle de sa dernière tâche achevée, donc le projet ne peut pas finir avant que la plus longue suite de tâches enchaînées soit terminée. Énoncé correct : le chemin critique est le chemin de durée maximale entre le début et la fin, et cette durée maximale EST la durée minimale du projet.

5) FAUX. Le nombre de sommets ne décide de rien : un graphe à six sommets et sans aucune arête se colore avec une seule couleur, et le réseau de relais de l'exercice 1 se colore avec deux couleurs. Énoncé correct : le nombre chromatique est au PLUS égal au nombre de sommets, cas atteint seulement par le graphe complet où tous les sommets sont deux à deux reliés ; il est au MOINS égal à la taille du plus grand groupe de sommets tous reliés entre eux, un triangle imposant déjà trois couleurs.

a) C'est un problème EULÉRIEN. L'énoncé dit que le camion doit déneiger chaque RUE : ce sont les arêtes qui doivent toutes être parcourues, pas les intersections. Un problème hamiltonien serait celui d'un livreur devant passer chez chaque client une fois, les clients étant placés aux intersections. Le mot à chercher dans l'énoncé est toujours celui-là : ce qui doit être visité est-il porté par les traits ou par les points ?

b) On calcule les degrés : $\deg(P)=2$, $\deg(Q)=3$, $\deg(R)=2$, $\deg(S)=2$, $\deg(T)=3$, $\deg(U)=2$, de somme $14$, soit deux fois les $7$ rues. Il y a exactement deux intersections de degré impair, $Q$ et $T$ : la chaîne eulérienne existe et elle part obligatoirement de l'une des deux pour arriver à l'autre. Un parcours possible depuis $Q$ : $Q$, $P$, $S$, $T$, $U$, $R$, $Q$, $T$. Il emprunte $QP$, $PS$, $ST$, $TU$, $UR$, $RQ$ et $QT$, soit les sept rues, chacune une fois. La distance parcourue vaut $4+3+4+4+3+4+3=25$ km, c'est-à-dire exactement la longueur totale du réseau : c'est la signature d'un parcours sans répétition.

c) Partir de $P$ et y revenir en passant par toutes les rues exigerait un cycle eulérien, donc aucune intersection de degré impair. Or il y en a deux, $Q$ et $T$ : c'est impossible sans répétition. Le camion devra donc repasser par certaines rues, et le moins coûteux est de répéter le plus court trajet entre les deux intersections impaires, ici la rue $QT$ elle-même, longue de $3$ km. La distance minimale vaut $25+3=28$ km. On vérifie la cohérence du résultat : $28$ km dépasse bien les $25$ km de réseau, et l'écart de $3$ km correspond à une rue réellement parcourue deux fois.

d) Non, et cela n'arrangerait rien. Ajouter la rue $PT$ ferait passer $P$ de $2$ à $3$ et $T$ de $3$ à $4$. Les intersections de degré impair deviendraient $P$ et $Q$ : il y en aurait toujours deux, et le cycle eulérien resterait impossible. Pour l'obtenir, il faudrait ajouter une rue entre les DEUX intersections impaires actuelles, donc une seconde rue entre $Q$ et $T$ : chacune passerait à $4$, tous les degrés seraient pairs, et le camion pourrait partir de $P$, tout déneiger et rentrer au garage sans jamais répéter une rue.

a) Les sommets sont les six examens, $M$, $P$, $C$, $B$, $H$ et $A$. Une arête relie deux examens lorsqu'un élève au moins est inscrit aux deux, c'est-à-dire lorsqu'ils sont INCOMPATIBLES et doivent tomber dans des plages différentes. Le graphe obtenu est celui de la figure. Attention au sens de la modélisation : ici une arête signifie une interdiction, et non une compatibilité. Placer les examens dans le minimum de plages revient alors exactement à colorer ce graphe avec le minimum de couleurs, une couleur étant une plage horaire.

b) Les trois examens $M$, $P$ et $C$ sont deux à deux en conflit : $M$ avec $P$, $M$ avec $C$, et $P$ avec $C$. Ils forment un triangle dans le graphe, donc ils exigent à eux seuls trois plages différentes. Deux plages ne peuvent donc pas suffire, quel que soit l'ordre choisi pour les trois autres examens.

c) Trois plages suffisent. Plage 1 : mathématique et biologie. Plage 2 : physique et histoire. Plage 3 : chimie et anglais. On vérifie les huit conflits un par un : $M$ et $P$ sont en 1 et 2 ; $M$ et $C$ en 1 et 3 ; $P$ et $C$ en 2 et 3 ; $C$ et $B$ en 3 et 1 ; $B$ et $H$ en 1 et 2 ; $H$ et $M$ en 2 et 1 ; $A$ et $P$ en 3 et 2 ; $A$ et $B$ en 3 et 1. Aucun couple en conflit ne partage une plage, et la partie b) a montré que trois est un minimum : le nombre chromatique du graphe vaut $3$ et l'horaire tient en trois plages.

d) Non. Aucun élève n'est inscrit à la fois en anglais et en chimie, sinon le couple $A$, $C$ figurerait dans la liste des conflits et une arête relierait ces deux sommets ; or $A$ n'est relié qu'à $P$ et à $B$. Deux examens placés dans la même plage sont précisément ceux qu'aucune arête ne relie, c'est la définition même d'une coloration valide. L'élève confond deux choses différentes : suivre deux matières, et être inscrit aux deux examens de la même session.