Éric SOPENA - sopena@labri.

fr avril 2002

ÉLÉMENTS DE THÉORIE DES GRAPHES

SOLUTION DES EXERCICES D’APPLICATION

Il est possible que certaines des solutions comportent des erreurs, de frappe ou
d’inattention… Merci au lecteur attentif de me les signaler…

1. NOTIONS DE BASE

1.1. Modélisation

Solution Exercice 1. Aucune difficulté particulière (ne pas oublier les boucles)…
1
12
2

11 3

10 4

9 5

8 6
7

Solution Exercice 2. Cette situation peut être modélisée à l’aide d’un graphe. Désignons par P le passeur, par
C la chèvre, par X le chou et par L le loup. Les sommets du graphe sont des couples précisant qui est sur la
rive initiale, qui est sur l’autre rive. Ainsi, le couple (PCX,L) signifie que le passeur est sur la rive initiale avec la
chèvre et le chou (qui sont donc sous surveillance), alors que le loup est sur l’autre rive. Une arête relie deux
sommets lorsque le passeur peut passer (sic) d’une situation à l’autre. En transportant la chèvre, le passeur
passe par exemple du sommet (PCX,L) au sommet (X,PCL). Le graphe ainsi obtenu est biparti : les sommets
pour lesquels le passeur est sur la rive initiale ne sont reliés qu’aux sommets pour lesquels le passeur est sur
l’autre rive…
Naturellement, on ne considèrera pas les sommets dont l’une des composantes est CX ou LC car ces situations
sont interdites.
Il suffit ensuite de trouver un chemin (le plus court par exemple) entre la situation initiale (PCXL,-) et la situation
finale souhaitée (-,PCXL). La figure suivante donne un tel chemin :
(PCXL,-) (PCL,X) (PCX,L) (PXL,C) (PC,XL)

(XL,PC) (C,PXL) (L,PCX) (X,PCL) (-,PCXL)

Solution Exercice 3. La solution est donnée dans les vers suivants :

« It duplex mulier, nedit una, vehit que manentem ;

Éléments de théorie des graphes - Solutions des exercices d’application page 1

Éric SOPENA - [email protected] avril 2002

Itque una, utuntur tunc duo puppe viri.

Par vadit, redeunt bini ; mulierque so rorem
Ad vehit ; ad propriam sive maritus abit. »
Pour les non latinistes, il est possible d’utiliser le même principe que dans l’exercice précédent, en notant A, B
et C les femmes, a, b et c les maris. On obtient encore un graphe biparti, selon que la barque est sur une rive
ou sur l’autre. Le schéma suivant propose une solution parmi d’autres (le graphe n’est pas représenté en
totalité)…
(aAbBcC,-) (aAbBc,C) (aAbc,BC) (aAbB,cC) (ABC,abc) (AC,abBc)

(aAbc,BC) (abc,ABC) (aA,bBcC) (AB,abcC) (C,aAbBc) (-,aAbBcC)

Dans le cas où quatre couples sont sur la berge, les sommets (aAbBcCdD,-) et (-,aAbBcCdD) sont dans des
composantes connexes distinctes. Il n’existe donc pas de chemin de l’un à l’autre et le problème n’a pas de
solution (on peut vérifier que dans la composante connexe du sommet d’arrivée, seuls figurent des sommets
correspondant à un seul mari sur la rive initiale)…
À titre d’exercice supplémentaire, on peut voir que le problème des 4 maris jaloux a une solution s’il existe une
île au milieu de la rivière permettant de déposer certaines personnes ou si la barque peut transporter trois
personnes.

Solution Exercice 4. Toujours le même principe. Les sommets sont cette fois des couples donnant le contenu
du récipient de 5 litres et celui du récipient de 3 litres. On place un arc entre deux sommets lorsqu’on peut
passer d’une configuration à l’autre. On cherche alors un chemin du sommet 0,0 au sommet 4,0… La figure
suivante montre un tel chemin (le graphe n’est pas représenté en entier…)
0,0 5,0 2,3
4,0

0,3 2,0 4,3

5,3
Etc.

3,0 3,3 0,2 5,2

Solution Exercice 5. Le jeu avec 2 tas de trois allumettes est décrit par le graphe suivant (tous les arcs sont
orientés de gauche à droite) :
0,3
2,3 0,2 0,0

3,3 2,2 1,2 0,1

1,3
1,1
Le joueur qui atteint la configuration 0,0 perd la partie. Pour gagner, on doit donc atteindre la configuration 0,1
ou 0,2. On peut vérifier qu’en jouant 1,3 au premier coup, quelle que soit la réponse de l’adversaire, on peut
atteindre ensuite 0,1 ou 0,2. Le coup gagnant au départ est donc « enlever 2 allumettes dans un tas ».

Pour trois tas de trois allumettes, c’est simplement un peu plus long ;-)…

Solution Exercice 6. Pour chacune de ces questions, on construit un graphe dont les sommets représentent les
cases de l’échiquier. Les arêtes sont alors définies ainsi :
1 et 3 : une arête relie deux cases si une dame placée sur l’une contrôle l’autre,
2 : une arête relie deux cases si un cavalier placée sur l’une peut se rendre sur l’autre.
Les 3 problèmes s’expriment alors ainsi en terme de graphes :
1 : Trouver un ensemble maximal de sommets tels qu’il n’existe aucune arête entre ces sommets (un tel
ensemble est dit indépendant).
Éléments de théorie des graphes - Solutions des exercices d’application page 2
Éric SOPENA - [email protected] avril 2002

2 : Trouver un chemin hamiltonien (c’est-à-dire un chemin passant une et une seule fois par chacun des
sommets).
3 : Trouver un ensemble minimal de sommets tel que tout sommet appartient à cet ensemble ou est relié par
une arête à au moins l’un des sommets de cet ensemble (un tel ensemble est dit dominant).

Problème des 8 Dames Dames sur échiquier 5x5 Parcours du cavalier

La figure ci-dessus donne une solution pour chacun de ces trois problèmes. Le parcours du cavalier présenté
est en fait un cycle hamiltonien (le cavalier retourne à son point de départ).

Solution Exercice 7. 1. Chaque gardien va être placé sur une arête et pourra surveiller deux carrefours
(sommets). Le graphe ayant 11 sommets, il faudra au minimum 6 gardiens. Il faut donc trouver un ensemble
(minimal) d’au moins six arêtes, tel que tout sommet est incident à au moins l’une de ces arêtes. Le schéma ci-
dessous donne une solution (arêtes épaisses).
2. Cette fois, les gardiens sont sur les sommets et surveillent les arêtes. Il faut trouver un ensemble minimal de
sommets tel que toute arête est incidente à au moins l’un de ces sommets. On constate rapidement que tout
cycle de longueur 5 doit avoir 3 sommets dans cet ensemble… Le schéma ci-dessous donne une solution
utilisant 6 sommets (sommets blancs).

Solution Exercice 8. Le premier travail consiste à dessiner le « graphe des rencontres ». Ce graphe est ce que
l’on appelle un graphe d’intervalles : chaque sommet est associé à un intervalle (le temps de présence de
l’élève dans la bibliothèque) et deux sommets sont reliés lorsque les intervalles s’intersectent (les élèves se
sont croisés). Pour notre exemple, plusieurs solutions sont alors possibles, chacune pouvant donner des ordres
d’arrivée et de départ différents. Le schéma suivant en fournit une…
A

B C
G
G
F
B
D
C A
F E

Arrivée CEG F B D A
E D Départ C F G B D A E

Solution Exercice 9. Affecter un emploi à une personne revient à « sélectionner » une arête. Chaque personne
ne pouvant occuper qu’un seul emploi, et un emploi ne pouvant être occupé que par une seule personne, il faut
donc sélectionner un nombre maximal d’arêtes de façon telle que ces arêtes n’ont aucun sommet commun (un
Éléments de théorie des graphes - Solutions des exercices d’application page 3
Éric SOPENA - [email protected] avril 2002

tel ensemble est qualifié de stable maximal). Le schéma ci-dessous donne un tel ensemble (arêtes épaisses)
composé de 6 arêtes…
T1 T2 T3 T4 T5 T6

E1 E2 E3 E4 E5 E6

Solution Exercice 10. Considérons le graphe complet K12 à 12 sommets, chaque sommet représentant un
enfant. Le nombre d’arêtes de ce graphe est 12 x 11 / 2 = 66. Une promenade correspond à un ensemble de 6
arêtes non incidentes : chaque arête représente un rang (deux enfants) et chaque enfant ne peut appartenir
qu’à un seul rang lors d’une promenade. Ainsi, le nombre maximum de promenades est 11. Une solution
possible pour ces 11 promenades est la suivante (les enfants, ou sommets, sont désignés par 1,2,…,12) :
1-2, 3-12, 4-11, 5-10, 6-9, 7-8 2-3, 12-4, 11-5, 10-6, 9-7, 8-1
1-3, 4-2, 5-12, 6-11, 7-10, 8-9 3-4, 2-5, 12-6, 11-7, 10-8, 9-1
1-4, 5-3, 6-2, 7-12, 8-11, 9-10 4-5, 3-6, 2-7, 12-8, 11-9, 10-1
1-5, 6-4, 7-3, 8-2, 9-12, 10-11 5-6, 4-7, 3-8, 2-9, 12-10, 11-1
1-6, 7-5, 8-4, 9-3, 10-2, 11-12 6-7, 5-8, 4-9, 3-10, 2-11, 12-1
1-7, 2-12, 3-11, 4-10, 5-9, 6-8
Les cinq premières « paires » de promenades sont obtenues en découpant de deux façons complémentaires un
cycle à 12 sommets (pour la première ligne, il s’agit du cycle 1,2,3,12,4,11,5,10,6,9,7,8,1). La dernière ligne est
composée des 6 arêtes restantes.
Considérons maintenant le cas des rangs de trois. Chaque rang correspond alors à un triangle dans K12 et
chaque promenade à un ensemble de 4 triangles « disjoints ». Cette fois, une promenade utilise 4 x 3 = 12
arêtes et le nombre maximum de promenades est 5…
Je n’ai pas de solution « sous la main »…. Je publierai donc la première solution qui me parviendra… ;-)

Solution Exercice 11. Voici une liste de conditions nécessaires :

• Chaque sommet doit avoir un degré entrant égal à 2 (chaque lapin a deux parents) à l’exception
de deux sommets pour lesquels le degré entrant est nul (ces sommets correspondent aux
« Adam » et « Ève » de notre groupe de lapins…).
• Le graphe doit être sans circuit (on dit également acyclique). En effet, un lapin ne peut avoir pour
parent l’un de ses descendants…
• On doit pouvoir colorier les sommets de ce graphe en deux couleurs (male et femelle), de façon
telle que tout sommet de degré entrant égale à 2 possède un prédécesseur male et un
prédécesseur femelle.
• Il est possible que d’autres conditions soient nécessaires mais ma connaissance du mécanisme
de reproduction chez les lapins ne me permet pas d’aller plus loin… (nombre de portées
possibles, nombre de petits lapins par portée, etc.)

1.2. Degré des sommets

Solution Exercice 12. Les graphes dont tous les sommets sont de degré trois sont appelés graphes 3-reguliers
ou graphes cubiques. La figure ci-dessous montre deux graphes cubiques, ayant respectivement 4 et 6
sommets. En effet, on constate aisément qu’il n’existe pas de graphes cubiques ayant un nombre impair de
sommets : le nombre d’arêtes d’un graphe cubique à n sommets est 3n/2 qui n’est entier que lorsque n est pair.

Éléments de théorie des graphes - Solutions des exercices d’application page 4

Éric SOPENA - [email protected] avril 2002

Solution Exercice 13. Cette fois, le nombre d’arêtes d’un tel graphe est 4n/2 = 2n si n est le nombre de sommets.
De tels graphes existent toujours… dès que n est au moins égal à 5 !
Considérons par exemple le graphe dont les sommets sont les entiers de 0 à n-1 (avec n ≥ 5) et les arêtes les
paires de sommets i,j telles que j = i+1 ou j = i+2 (modulo n). On vérifie aisément que ces graphes sont 4-
réguliers (tout sommet i est relié à i-2, i-1, i+1 et i+2, toujours modulo n…).

Solution Exercice 14. Les suites (3,3,2,1,1), (3,3,2,2) et (4,2,1,1,1,1) sont graphiques, comme le montrent les
graphes A, C et D de la figure ci-dessous. Les graphes X et Y sont distincts et correspondent tous deux à la
suite (3,2,2,2,1).

A C D X Y

Solution Exercice 15. Nous savons que la somme des degrés entrants doit être égale à la somme des degrés
sortants. Nous pouvons ainsi déjà éliminer les suites [(0,2),(1,1),(1,1),(1,1)] et [(1,2),(1,2),(2,1),(2,2),(1,1)]. Les
suites [0,1),(1,1),(1,1),(1,1),(1,0)], [(1,1),(1,1),(1,1),(1,1),(1,1)], [(0,2),(1,1),(1,1),(2,0)] et [(1,2),(1,2),(2,1),(2,1)]
sont graphiques, comme le montrent respectivement les graphes A, B, D et E ci-dessous.

A B D E

Solution Exercice 16. On s’aperçoit rapidement que c’est impossible. Ainsi, dans un graphe, il existe toujours
deux sommets de même degré. La preuve de ce fait est donnée dans la solution de l’exercice 19.

Solution Exercice 17. Supposons tout d’abord qu’il existe une personne, disons A, en connaissant trois autres,
disons B, C et D, et considérons les relations entre B, C et D… Si deux d’entre elles se connaissent (par
exemple B et C) alors elles forment avec A un trio de personnes se connaissant mutuellement. Dans le cas
contraire, B, C et D forment un trio ne se connaissant pas.
Si aucune personne n’en connaît trois autres, on raisonne de façon symétrique en considérant la personne A et
trois personnes qu’elle ne connaît pas : si ces trois personnes se connaissent mutuellement, c’est gagné.
Sinon, deux personnes parmi ces trois ne se connaissant pas forment avec A un trio de personnes ne se
connaissant pas…
Le graphe suivant montre que la situation est différente pour un groupe de cinq personnes (tout triplet de
personnes contient 1 ou 2 arêtes)…

Solution Exercice 18. Un tel groupe sera représenté sous forme d’un graphe dont les sommets sont les
personnes ; une arête reliera deux sommets correspondant à des personnes se connaissant. Supposons qu’il
existe un groupe (graphe) de 9 personnes (sommets) n’ayant pas la propriété annoncée. Nous allons montrer
que nous aboutissons nécessairement à une contradiction.
Prenons tout d’abord deux personnes se connaissant, disons A et B (si personne ne se connaît, nous avons un
trio ne se connaissant pas). Les sept autres personnes peuvent alors être réparties en quatres groupes : G, le
Éléments de théorie des graphes - Solutions des exercices d’application page 5
Éric SOPENA - [email protected] avril 2002

groupe des personnes ne connaissant ni A ni B ; GA, le groupe des personnes connaissant A mais ne
connaissant pas B ; GB, le groupe des personnes connaissant B mais ne connaissant pas A ; GAB, le groupe
des personnes connaissant A et B.
Que pouvons-nous dire de ces groupes de personnes ?
• G : ce groupe est nécessairement composé de personnes se connaissant mutuellement (sinon,
deux personnes de ce groupe ne se connaissant pas formeraient avec A ou B un trio ne se
connaissant pas). Ainsi, ce groupe contient au maximum 3 personnes (sinon nous avons un
quatuor se connaissant mutuellement).
• GA : ce groupe est nécessairement composé de personnes se connaissant mutuellement (sinon,
deux personnes de ce groupe ne se connaissant pas formeraient avec B un trio ne se
connaissant pas). Ainsi, ce groupe contient au maximum 2 personnes (sinon nous avons avec A
un quatuor se connaissant mutuellement).
• GB : de façon symétrique, ce groupe est nécessairement composé de personnes se connaissant
mutuellement (sinon, deux personnes de ce groupe ne se connaissant pas formeraient avec A un
trio ne se connaissant pas). Ainsi, ce groupe contient au maximum 2 personnes (sinon nous
avons avec B un quatuor se connaissant mutuellement).
• GAB : ce groupe est nécessairement composé de personnes ne se connaissant pas (sinon, deux
personnes de ce groupe se connaissant formeraient avec A et B un quatuor se connaissant
mutuellement). Ce groupe contient donc au maximum deux personnes (sinon nous avons un trio
ne se connaissant pas).
Examinons maintenant les relations entre ces quatre groupes…
• toutes les personnes de GB connaissent toutes les personnes de G (sinon une personne de GB
et une personne de G ne se connaissant pas formeraient avec A un trio ne se connaissant pas).
L’union de G et GB est donc un ensemble de personnes se connaissant mutuellement et sa taille
est d’au plus 3 (sinon nous avons un quatuor se connaissant mutuellement).
• de façon symétrique, les personnes de G et GA se connaissent mutuellement et la taille de
l’union de G et GA est d’au plus 3.
Fort de ces observations, on peut vérifier sans peine que la seule possibilité concernant les cardinalités de ces
3 groupes est la suivante : card(G) = 1, card(GA) = 2, card(GB) = 2 et card(GAB) = 2 (avec A et B, nous
retrouvons bien nos 9 personnes…). Posons alors G = {U}, GA = {T1, T2}, GB = {Z1, Z2} et GAB = {X, Y}. Le
schéma correspondant est donné ci-dessous, figure (a).
Considérons maintenant les relations entre GAB et GA, GB… Tout sommet de GA ou GB doit être relié à au
moins un sommet de GAB (sinon nous avons un trio ne se connaissant pas). Par contre, les deux sommets de
GA (ou de GB) ne peuvent être reliés au même sommet de GAB, sinon, ils formeraient avec A (ou B) un
quatuor se connaissant mutuellement. Nous obtenons ainsi la figure (b) ci-dessous (du fait des symétries, une
seule solution est possible).
Qu’en est-il des relations entre GA et GB ? Z1 est nécessairement voisin de T2, sinon Z1, T2 et X forment un
trio ne se connaissant pas. De la même façon, Z2 est nécessairement voisin de T1 (voir figure (c)).
Pour conclure sur une contradiction, il nous reste à regarder les relations entre G et GAB… U est
nécessairement relié à X ou Y, sinon U,X,Y serait un trio ne se connaissant pas. Si U est relié à X, alors X,U,T1
et Z2 forment un quatuor se connaissant mutuellement et si U est relié à Y, alors U,Y,T2 et Z1 forment un
quatuor se connaissant mutuellement. Dans les deux cas, nous obtenons la contradiction recherchée…
X Y X Y X Y

T1 Z1 T1 Z1 T1 Z1

T2 A B Z2 T2 A B Z2 T2 A B Z2

U U U

figure (a) figure (b) figure (c)

Le graphe suivant montre que la propriété n’est plus vérifiée pour un groupe de 8 personnes :

Éléments de théorie des graphes - Solutions des exercices d’application page 6

Éric SOPENA - [email protected] avril 2002

Solution Exercice 19. Construisons un graphe dont les sommets représentent les personnes et plaçons une
arête entre deux sommets lorsque les personnes correspondantes sont amies. Dire que deux personnes ont le
même nombre d’amis revient à dire que deux sommets dans le graphe ont même degré…
Nous allons montrer qu’il n’existe aucun graphe dont tous les sommets ont des degrés distincts. Supposons
qu’un tel graphe existe et qu’il possède n sommets. Le degré maximal d’un sommet est donc n-1. Si tous les
degrés des sommets sont distincts, on a donc nécessairement un sommet de degré 0, un sommet de degré 1,
…, un sommet de degré n-1. Du fait de la présence d’un sommet de degré 0, disons x0, il est impossible d’avoir
un sommet de degré n-1 ! (en effet, celui-ci devrait être relié à tous les autres, y compris x0). On obtient ainsi
une contradiction.

Solution Exercice 20. Supposons que nous avons n associations et considérons le graphe complet Kn dont les
sommets représentent les associations (toute paire d’associations est donc reliée par une arête). Deux
associations ayant toujours exactement un membre en commun, nous pouvons étiqueter l’arête reliant ces deux
associations par le membre en question. Par ailleurs, chaque personne étant membre d’exactement deux
associations, une même personne ne peut pas étiqueter deux arêtes distinctes (sinon elle appartiendrait à au
moins trois associations). Les arêtes sont donc en bijection avec les personnes…
Finalement, chaque association comprenant exactement trois personnes, tous les sommets du graphe complet
sont de degré 3. Il s’agit donc de K4 ! Le nombre d’associations est donc de 4 (nombre de sommets) et le
nombre de personnes de 6 (nombre d’arêtes = 4 x 3 / 2).

1.3. Graphes eulériens

Solution Exercice 21. De tels tracés sont possibles si le graphe correspondant admet un chemin eulérien, c’est-
à-dire s’il contient exactement 0 ou 2 sommets de degré impair. La réponse est donc positive uniquement pour
la deuxième figure…

Solution Exercice 22. On peut associer un graphe à cette figure (en réalité un multigraphe car nous aurons des
arêtes multiples) de la façon suivante : les sommets représentent les régions (y compris la région extérieure) et
deux sommets sont reliés par autant d’arêtes que le nombre de segments communs de leurs régions (voir ci-
dessous).
Le problème revient alors à effectuer un chemin eulérien dans ce graphe. Or, ce graphe contient 4 sommets de
degré impair… c’est donc impossible.

Solution Exercice 23. La figure suivante représente les ponts de Koenigsberg et le graphe non orienté associé
au problème classique. Le problème consistant à emprunter deux fois chaque pont, dans un sens puis dans
l’autre, revient à chercher un cycle eulérien dans le graphe orienté obtenu en modélisant chaque pont par deux
arcs de directions opposées. On peut observer que le graphe orienté ainsi obtenu est tel que tout sommet
Éléments de théorie des graphes - Solutions des exercices d’application page 7
Éric SOPENA - [email protected] avril 2002

possède un degré entrant égal à son degré sortant (cela est vrai pour tout graphe orienté obtenu à partir d’un
graphe non orienté en remplaçant chaque arête par deux arcs de directions opposées…). Le graphe orienté est
donc eulérien et le parcours suivant le prouve (les ponts, ou arcs, sont désignés par AB, BC, BD, AC1, AC2,
CD1, CD2 dans un sens puis BA, DB, CD1, etc. dans l’autre sens) :
AB, BD, DC1, CA1, AC1, CD1, DB, BA, AC2, CB, BC, CD2, DC2, CA2
A
A
A

B C
B C B C

D D
D

Solution Exercice 24. Pour qu’un graphe soit eulérien, il faut et il suffit que tous ses sommets soient de degré
pair. Si un graphe contient k sommets impairs, il est possible de rajouter un nouveau sommet x, relié à ces k
sommets. Dans le graphe obtenu, les k sommets considérés sont devenus pairs… Cependant, le degré de x
étant k, le graphe n’est toujours pas eulérien si k était impair…
Remarquons qu’il est possible de rajouter des arêtes entre les sommets de degré impair dans le graphe
d’origine… Mais l’ajout d’une telle arête, entre deux sommets impairs a et b par exemple, fait que le nombre de
sommets impairs devient k-2, qui a la même parité que k…
La réponse est donc : ce n’est possible que si le nombre de sommets impairs est pair…

Solution Exercice 25. Les dominos sont au nombre de 4 + 3 + 2 + 1 = (4 x 5) / 2 = 10 :

1-2, 1-3, 1-4, 1-5, 2-3, 2-4, 2-5, 3-4, 3-5, 4-5
Considérons maintenant le graphe complet K5 à 5 sommets. Ce graphe possède 10 arêtes, chaque arête
correspondant à une paire de sommets distincts… c’est-à-dire à un domino. Former une boucle fermée avec
ces dominos revient donc à trouver un cycle eulérien (passant par toutes les arêtes, donc utilisant tous les
dominos) dans K5. Une solution possible est la suivante : 1-2, 2-3, 3-4, 4-5, 5-1, 1-3, 3-5, 5-2, 2-4, 4-1.
Les dominos doubles peuvent être insérés sans difficulté dans cette suite. En terme de graphes, les dominos
doubles correspondent à une boucle sur un sommet et cette boucle peut être « parcourue » lorsqu’on atteint le
sommet en question pour la première fois par exemple…
Si l’on considère le même problème avec des faces numérotées de 1 à n, on doit raisonner sur le graphe
complet à n sommets. Or, nous savons qu’un graphe admet un cycle eulérien si et seulement si il est connexe
et ne possède que des sommets de degré pair. Dans le cas des graphes complets, cela n’est vrai que si le
nombre de sommets est impair…

2. PROBLÈMES DE COLORATION

Solution Exercice 26. Il suffit de considérer par exemple un cycle ayant un nombre impair de sommets. Si l’on
rajoute à ce graphe un sommet relié à tous les sommets du cycle, on obtient un graphe de nombre chromatique
4 ne contenant pas de K4. On peut itérer cette construction de façon à obtenir, pour tout k, un graphe de
nombre chromatique k ne contenant pas de Kk. Un résultat plus puissant, dû à Erdös, montre que pour tout k, il
existe un graphe de nombre chromatique k sans triangle, et même sans cycle de longueur inférieure à un entier
p donné, quel que soit p…

1 1

3 2 3 2
4

2 1 2 1

Solution Exercice 27. Les graphes suivants ont respectivement pour nombre chromatique 3, 2 et 3 :

Éléments de théorie des graphes - Solutions des exercices d’application page 8

Éric SOPENA - [email protected] avril 2002

1 2 2 1 1 2 2 1

1 3 2
2

3 1 1 1 1
2 2
2

Solution Exercice 28. Le graphe modélisant le carrefour est représenté ci-dessous. Son nombre chromatique est
égal à 4 (il est 4-coloriable et contient un K4 regroupant les sommets AC, BD, CD et DA). Un ensemble de
sommets de même couleur, par exemple ED, AC, AE et CA regroupe un ensemble de trajets pouvant
s’effectuer en même temps (aucune incompatibilité). Le nombre chromatique correspond alors au nombre
minimum de « cycles » que doivent respecter les feux de signalisation de ce carrefour. Pour notre exemple,
nous aurons :
1. ED, AC, AE et CA 2. BA, BE, BD et EC 3. DC et DA 4. CD
D’autres solutions (4-colorations) sont naturellement possibles…

1 AC
ED 1
AE
2 1
EC

BA
3 2
DA

3 BE
2
DC
2
4 BD
CD 1
CA

Solution Exercice 29. Voici deux colorations du graphe de Petersen. La première utilise 7 comme plus grand
entier, la deuxième 19…
Dans le premier cas, on peut vérifier que pour colorier ainsi un cycle à 5 sommets, la meilleure solution est 1-4-
1-4-7. Ainsi, il n’est pas possible de n’utiliser que des entiers inférieurs à 7.
Dans le deuxième cas, remarquons que deux sommets quelconques sont à distance au plus 2 (on dit que le
graphe est de diamètre 2). Toutes les couleurs doivent donc être distinctes et « espacées » de 2. La meilleure
solution utilise ainsi les entiers impairs 1,3,5,…,19.
1 1

4 11
4 4 7 5
1 7 13 19

1 7 17
15

7 1 3 9

Solution Exercice 30. On reprend le « graphe des rencontres » proposé dans l’exercice 8. Il reste alors à
proposer une coloration du graphe utilisant un nombre minimum de couleurs. Chaque couleur correspondra à
une place assise. La coloration suivante montre que 4 places sont nécessaires… et suffisantes car le graphe
contient une clique (sous-graphe complet) à 4 sommets (B-E-F-G).

Éléments de théorie des graphes - Solutions des exercices d’application page 9

Éric SOPENA - [email protected] avril 2002

A
2

G 4 B
2

1
C
F
1

E 3 1 D

3. PROBLÈMES DE CHEMINS

Solution Exercice 31. Dans un « tournoi », un ensemble de n individus (ou équipes) se rencontrent deux à deux,
chaque rencontre se soldant par la victoire de l’un et la défaite de l’autre… Ceci peut être représenté à l’aide
d’un graphe dont les sommets correspondent aux individus et tel qu’un arc va du sommet A vers le sommet B si
la rencontre correspondante a vu la victoire de A sur B…
Supposons qu’un tournoi T possède un circuit C = x1x2…xkx1 de longueur k > 3 (en effet, pour k=3, il n’y a rien à
prouver). Nous allons d’abord montrer que T possède un circuit de longueur 3.
Considérons n’importe quel sommet du circuit C, x1 par exemple. Nous affirmons qu’il existe nécessairement un
arc xixi+1 dans T, avec 1 < i < k, tel que x1xi et xj+1x1 sont des arcs (en d’autres termes, x1xixi+1x1 forme un
circuit). On peut exhiber un tel arc en « tournant » autour de C de la façon suivante :
• posons i=2 ; si x3x1 est un arc, nous avons gagné (x1x2x3x1 est un circuit) ; dans le cas contraire,
x1x3 est un arc et nous pouvons poser i=3…
• en continuant de la sorte, nous allons nécessairement trouver un arc xixi+1 ayant la propriété
cherchée car xkx1 est un arc de T (au pire, la solution sera donc l’arc xk-1xk).
Nous allons terminer la preuve en montrant que dès que nous avons un circuit de taille k’ composé de sommets
de C, avec 3 ≤ k’ < k-1, nous avons nécessairement un circuit de taille k’+1, toujours composé de sommets de
C (nous montrons ainsi une propriété plus forte que celle annoncée dans l’exercice).
Soit donc C’ = y1y2…yk’y1 un circuit composé de sommets de C et notons X l’ensemble des sommets de C non
utilisés dans C’.
Supposons qu’il existe un sommet x de X qui soit successeur de certains sommets de C’ et prédécesseur
d’autres sommets de C’. Dans ce cas, il y a nécessairement un arc yjyj+1 dans C’ tel que yj est prédécesseur de
x et yj+1 est successeur de x. Nous avons alors un circuit de longueur k’+1 : y1y2…yjxyj+1…xk’x1 (nous avons pris
ici un « raccourci » dans l’écriture car l’arc yjyj+1 peut être l’arc yky1…).
Si on ne peut trouver un tel sommet x, cela signifie que l’ensemble X peut être partitionné en deux sous-
ensembles S et P respectivement composés des sommets successeurs de tous les sommets de C’ et des
sommets prédécesseurs de tous les sommets de C’. Aucun de ces deux sous-ensembles ne peut être vide car
nous savons qu’un circuit unit les sommets x1,…,xk. Pour la même raison, il existe nécessairement un sommet s
dans S et un sommet p dans P tel que sp est un arc dans T. (Dans le cas contraire, l’ensemble S (ou P) n’aurait
que des prédécesseurs (ou des successeurs) parmi les autres sommets et le circuit initial C ne pourrait exister).
Nous avons alors un circuit de longueur k’+1, donné par y1spy3…yk’y1 (voir figure ci-dessous).

y3 P
p

C' y2

y1 s
S

Finalement, la figure suivante montre un tournoi à 6 sommets ne possédant aucun circuit de longueur
supérieure à 3 (ce tournoi est composé de 2 circuits de longueur 3 réunis par des arcs ayant tous la même
direction) :
Éléments de théorie des graphes - Solutions des exercices d’application page 10
Éric SOPENA - [email protected] avril 2002

Solution Exercice 32. Pour un sommet donné, il est nécessaire de calculer la somme des longueurs des plus
courts chemins de ce sommet aux autres sommets. La figure suivante donne cette valeur pour le sommet A,
puis pour tous les sommets du graphe. Le meilleur sommet de stockage est donc le sommet X…
24 26

A 24 17 16 17 20

X
26
1+1+1+1+2+3+4+4 = 17 24

Solution Exercice 33. On peut essayer d’énumérer les cycles de longueur 5 par rapport au nombre d’arêtes
« extérieures » qu’ils contiennent. La figure suivante montre les « schémas » de cycles correspondants et le
nombre de tels cycles obtenus par rotation… Le nombre total de cycles de longueur 5 est donc 12…

5 arêtes extérieures 2 arêtes extérieures 1 arêtes extérieures 0 arêtes extérieures

1 5 5 1

Même principe pour les cycles de longueur 6, au nombre de 10 :

3 arêtes extérieures 1 arête extérieure

5 5

Les cycles de longueur 8, au nombre de 15 :

4 arêtes extérieures 2 arêtes extérieures 2 arêtes extérieures

5 5 5

Et enfin les cycles de longueur 9, au nombre de 20 :

Éléments de théorie des graphes - Solutions des exercices d’application page 11

Éric SOPENA - [email protected] avril 2002

4 arêtes extérieures 3 arêtes extérieures 3 arêtes extérieures 2 arêtes extérieures

5 5 5 5

Solution Exercice 34. Un nombre premier correspond à un sommet de degré entrant 2 puisqu’il doit être divisible
par 1 et lui-même (n’oublions pas la boucle présente en chaque sommet), ou de degré entrant 1 (car 1 est
premier et n’est divisible que par lui même).
Si l’on considère un chemin allant de 1 à n, le produit des valeurs des arcs qui le composent vaut
nécessairement n… On peut alors, dans le graphe précédent, ne conserver que les arcs dont la valeur est un
nombre premier et qui ne sont pas des boucles. Tout sommet n est alors tel qu’il existe un unique chemin de 1
à n, dont les valeurs d’arcs donnent la décomposition en facteurs premiers.

Solution Exercice 35. Le calcul peut se faire directement… On obtient le tableau suivant :

A B C D E F G
A 0 8 10 15 18 20 24
B 22 0 2 7 10 12 16
C 19 20 0 5 8 10 14
D 14 20 22 0 3 5 14
E 11 17 19 9 0 2 11
F 21 15 17 7 10 0 9
G 27 6 8 13 16 18 0

Solution Exercice 36. À partir du sommet C, nous obtenons :

Initial : poids = ∞, ∞, 0, ∞, ∞, ∞, ∞ venant de : -, -, C, -, -, -, - Π=∅
choix de C : poids = ∞, ∞, 0, 5, ∞, ∞, 14 venant de : -, -, C, C, -, -, C Π = {C}
choix de D : poids = ∞, ∞, 0, 5, 8, ∞, 14 venant de : -, -, C, C, D, -, C Π = {C,D}
choix de E : poids = 19, ∞, 0, 5, 8, 10, 14 venant de : E, -, C, C, D, E, C Π = {C,D,E}
choix de F : poids = 19, ∞, 0, 5, 8, 10, 14 venant de : E, -, C, C, D, E, C Π = {C,D,E,F}
choix de G : poids = 19, 20, 0, 5, 8, 10, 14 venant de : E, G, C, C, D, E, C Π = {C,D,E,F,G}
choix de A : poids = 19, 20, 0, 5, 8, 10, 14 venant de : E, G, C, C, D, E, C Π = {A,C,D,E,F,G}
choix de B : poids = 19, 20, 0, 5, 8, 10, 14 venant de : E, G, C, C, D, E, C Π = {A,B,C,D,E,F,G}
fin de l’algorithme….
À partir du sommet F, nous obtenons :
Initial : poids = ∞, ∞, ∞, ∞, ∞, 0, ∞ venant de : -, -, -, -, -, F, - Π=∅
choix de F : poids = ∞, ∞, ∞, 7, ∞, 0, 9 venant de : -, -, -, F, -, F, F Π = {F}
choix de D : poids = ∞, ∞, ∞, 7, 10, 0, 9 venant de : -, -, -, F, D, F, F Π = {D,F}
choix de G : poids = ∞, 15, ∞, 7, 10, 0, 9 venant de : -, G, -, F, D, F, F Π = {D,F,G}
choix de E : poids = 21, 15, ∞, 7, 10, 0, 9 venant de : E, G, -, F, D, F, F Π = {D,E,F,G}
choix de B : poids = 21, 15, 17, 7, 10, 0, 9 venant de : E, G, B, F, D, F, F Π = {B,D,E,F,G}
choix de C : poids = 21, 15, 17, 7, 10, 0, 9 venant de : E, G, B, F, D, F, F Π = {B,C,D,E,F,G}
choix de A : poids = 21, 15, 17, 7, 10, 0, 9 venant de : E, G, B, F, D, F, F Π = {A,B,C,D,E,F,G}
fin de l’algorithme….

Solution Exercice 37. Il suffit de dessiner le graphe dont les sommets sont les villes et les arcs les dessertes de
la compagnie, en valuant chaque arc par la durée du vol correspondant. Un algorithme de plus court chemin
permet alors de résoudre le problème.
Pour prendre en compte les durées d’escale, deux méthodes sont possibles :
1. Modifier l’algorithme précédent, en incluant dans le calcul du coût d’un chemin les durées d’escale…

Éléments de théorie des graphes - Solutions des exercices d’application page 12

Éric SOPENA - [email protected] avril 2002

2. Transformer le graphe selon le principe décrit ci-dessous. L’algorithme reste alors le même, en choisissant
« correctement » les sommets de départ et d’arrivée (sans escale) : on part donc de Départ2 et on arrive en
Arrivée1…

1h10 1h10
3h40 (durée escale) 3h40
0h30
devient :
X X1 X2
2h20 1h50 2h20 1h50

4. PROBLÈMES D’ORDONNANCEMENT

Solution Exercice 38. En utilisant la méthode MPM, nous obtenons le graphe ci-dessous. Les dates au plus tôt et
au plus tard sont calculées « par niveaux »… Les tâches critiques, et le chemin critique sont indiqués en gras.
Le temps minimum de réalisation de l’ensemble est lisible sur le sommet FIN : 1170 jours.

A
0 0

120

B
120 120

180 180
180

C D E
300 327 300 300 300 510

3 30 30

G F 60 60

330 330 330 480

240 90 90
240

J H
570 570 570 630

240
180
240 180 240
180

I K L
810 1140 810 810 810 930

360
30 240

FIN
1170 1170

Éléments de théorie des graphes - Solutions des exercices d’application page 13

Éric SOPENA - [email protected] avril 2002

Solution Exercice 39. La solution dépendra tout naturellement du problème considéré ;-)

5. PROBLÈMES D’AUTOMATES

5.1. automates simples

Solution Exercice 40. L’automate suivant reconnaît les entiers souhaités en écriture normalisée. Toutes les
transitions non représentées vont vers un états puits.

0_à _9
0 C D

2_à _9

A
0_à _9
E H
1

0_1_2

D 3 0_à _8
F I

4_à _9

Solution Exercice 41. Voici les automates correspondants. Toutes les transitions non représentées vont vers un
états puits.
♦ les multiples de 3 : aucune difficulté particulière, on raisonne « modulo 3 »…
2_5_8

0_3_6_9
1_4_7
init
mod 1

2_5_8 2_5_8
0_3_6_9

1_4_7 1_4_7
1_4_7

mod 0 mod 2

0_3_6_9
2_5_8
0_3_6_9

♦ les multiples de 9 : il suffit de généraliser l’exemple précédent… Un état « init » et 9 états,

« mod 0 » à « mod 8 ». On obtient ainsi un « graphe complet » à 9 sommets (non dessiné
ici… ;-).
♦ les multiples de 10 : il faut reconnaître les entiers terminés par 0… La difficulté réside
dans le fait que l’automate doit rester déterministe. Ainsi, lorsqu’on lit un 0, on va dans
l’état d’acceptation, quitte à en revenir dès qu’un chiffre différent de 0 apparaît…

Éléments de théorie des graphes - Solutions des exercices d’application page 14

Éric SOPENA - [email protected] avril 2002

1_à _9 0
0

pas
OK
OK

1_à _9

♦ les multiples de 100 : même principe, avec deux zéros pour finir…
1_à _9 0
0

pas 0
presque
OK OK
OK

1_à _9
1_à _9

♦ les multiples de 1000 : one more time… and one more zero…
1_à _9

1_à _9 0
0

pas bientôt 0 0
presque
OK OK OK OK

1_à _9
1_à _9

♦ les multiples de 50 : cette fois, les entiers doivent être terminés par 00 ou 50.
1_à _4_et_6_à _9

1_à _4_et_6_à _9 0
5
0_5

pas bientôt 0
OK OK
OK

5
1_à _4_et_6_à _9

♦ les multiples de 25 : cette fois, les entiers doivent être terminés par 00, 25, 50 ou 75. Il
faut bien penser à la « signification » des états de l’automate…

Éléments de théorie des graphes - Solutions des exercices d’application page 15

Éric SOPENA - [email protected] avril 2002

1_3_4_6_8_9

1_3_4_6_8_9 0
5
0_5

pas lu 0 0 lu 00
1_3_4_6_8_9
OK ou 5 ou 50

2_7
5 5

2_7 2_7
0 0
1_3_4_6_8_9 1_3_4_6_8_9

lu 2 5
lu 25
ou 7 ou 75

2_7

2_7

♦ les multiples de 250 : cette fois, les entiers doivent être terminés par 000, 250, 500 ou
750. Même principe que pour le précédent…
1_3_4_6_8_9

1_3_4_6_8_9

1_3_4_6_8_9 5
0_5

pas lu 0 0 lu 00
1_3_4_6_8_9
OK ou 5 ou 50

2_7
5 5

0
2_7 5
2_7
0 0
1_3_4_6_8_9 1_3_4_6_8_9

mult
250
0
lu 2 5
lu 25
ou 7 ou 75

2_7

2_7
2_7

♦ les multiples de 6 : ils sont multiples de trois… et pairs ! On peut ainsi partir de l’automate
reconnaissant les multiples de trois et le « modifier » afin de séparer les pairs et les
impairs sur l’état final (en séparant également les transitions arrivant et sortant de cet
état)…

Éléments de théorie des graphes - Solutions des exercices d’application page 16

Éric SOPENA - [email protected] avril 2002

2_5_8

0_3_6_9
1_4_7
init
mod 1

3_9 2_8 2_5_8

0_6

1_4_7
1_4_7

1_4_7 4

mod 0 mod 2
5
pair
0_3_6_9
2_5_8
3_9 1_7
0_6
0_6 2_5_8
mod 0
impair

3_9

Solution Exercice 42. L’automate suivant reconnaît les heures sous une forme « normalisée » (03:07 pour trois
heures et 7 minutes). Le premier symbole doit être 0, 1 ou 2. Si c’est 2, alors seuls 1, 2 ou 3 sont autorisés
ensuite. Les minutes sont sur deux chiffres et doivent commencer par 0, 1, 2, 3, 4 ou 5…

0_à _9
0_1
deux_points 0_à _5
A D E F G
0_à _9
2
1_2_3

Solution Exercice 43. Le mois de février 2002 comportant 28 jours, nous obtenons l’automate ci-dessous. Il est
nécessaire de distinguer les jours 29 ou 30 (interdits en février) et les jours 31. Ces jours aboutissent
respectivement dans les états « 29_30 » et « 31 ». Il suffit alors de ne retenir par la suite que les mois où ces
jours sont autorisés…
J

/ 0 0_à _9
0_à _9
B E F
1 OK
0_1_2
K
0_1 0_à _8

2 1_3_4_5_6_7_8_9
A 1
C
9 / 0
29_30 G L
3
0

D
1_3_5_7_8
M
1
0
/
31 I 0_2
1
N

5.2. automates avec actions

Solution Exercice 44. Les éléments de cet automate seront les suivants :
• événements : interrogation orale, interrogation surprise, fin de journée, début de journée.
Éléments de théorie des graphes - Solutions des exercices d’application page 17
Éric SOPENA - [email protected] avril 2002

• actions : répondre, ne pas répondre, remettre une bonne copie, remettre une copie moyenne, se
reposer
• états : en forme, fatigué, au repos
L’automate peut alors être représenté ainsi (on suppose qu’à sa « naissance », l’élève est au repos…). Les
actions sont données entre accolades.
Interrogation orale
Interrogation orale
{répondre} {ne pas répondre}

En_Forme Interrogation surprise

Fatigué
{remettre bonne copie}
Interrogation surprise
{remettre copie moyenne}

Fin de journée Fin de journée

{se reposer} {se reposer}

Début de journée
{rien}
Au_Repos

Solution Exercice 45. Aucune difficulté particulière. Deux états, « éteint » et « allumé » permettent de distinguer
les réactions du téléphone aux événements que sont les touches…
L’automate correspondant est le suivant :
Touche non ON {rien} Touche non OFF {bip}

ON {bip}

Eteint
Allumé

OFF {bip}

Solution Exercice 46. Cette fois, il est nécessaire de distinguer les états de fonctionnement selon le mode
« normal » ou « silencieux »… De la même façon, on distinguera les états d’arrêt, selon que le téléphone a été
arrêté en mode « normal » ou « silencieux »…
L’automate est alors le suivant :
Touche non ON Touche non OFF non MUTE {bip}
{rien}

ON {bip}

Eteint_Normal
Allumé_Normal

OFF {bip}

Touche non ON {rien} MUTE {bip} MUTE {bip}

ON {bip}

Eteint_Silence Allumé_Silence

OFF {rien}

Touche non OFF non MUTE {rien}

Éléments de théorie des graphes - Solutions des exercices d’application page 18

Éric SOPENA - [email protected] avril 2002

Solution Exercice 47. Nous commençons par énumérer les événements et les actions… Les états sont alors
nécessités par le fait que notre « animal » peut avoir des réactions distinctes aux événements…
événements : rivière, belette, enfant, coucher du soleil, lever du jour, rêve pluie, rêve belette.
actions : boire, croquer, chanter, se laver et s’endormir, se réveiller, rien (lorsque l’événement « rêve » survient,
on subit l’événement…).
états : faim et soif, faim, soif 1, soif 2, ni faim ni soif 1, ni faim ni soif 2, endormi, rêvé belette, rêvé pluie.
Comme pour l’exercice du téléphone, il faut mémoriser les différents états de « réveil », selon le rêve effectué,
afin de se retrouver dans le bon état au lever du jour… Par ailleurs, il est nécessaire de « compter » les
belettes, c’est-à-dire de distinguer les états où l’on a croqué une belette des états où l’on en a croqué deux…
L’automate correspondant est alors le suivant :

Faim rivière
enfant enfant
et Soif Faim
{chanter} {boire} {chanter}

belette belette
{croquer} {croquer}

enfant
Soif 1 rivière enfant
{chanter} ni Faim ni
Soif 1 {chanter}
{boire}

belette belette
{croquer} {croquer}

enfant rivière ni Faim ni enfant

Soif 2
{chanter} Soif 2 {chanter}
{boire}

lever du jour
{se réveiller}

lever du jour
coucher de soleil
{se réveiller}

{se laver et s'endormir}

rêvé rêve pluie rêvé

belette endormi
pluie
rêve belette {rien}
{rien}

6. PROBLÈMES DIVERS

6.1. Arbres, arbres couvrants

Solution Exercice 48. Il est possible de classer ces différents arbres selon le nombre de feuilles (sommets sans
fils) par exemple. Une façon de procéder peut-être plus « visuelle » consiste à les classer selon la longueur du
plus long chemin dans l’arbre (on cherche ensuite à rajouter les « sommets manquants », sans les raccrocher
aux extrémités du chemin pour ne pas le rallonger…). Nous obtenons ainsi :
• 3 arbres à 5 sommets :

longueur 4 longueur 3 longueur 2

• 6 arbres à 6 sommets :

Éléments de théorie des graphes - Solutions des exercices d’application page 19

Éric SOPENA - [email protected] avril 2002

longueur 5 longueur 4 longueur 4 longueur 3 longueur 3 longueur 2

• 11 arbres à 7 sommets :

longueur 6 longueur 5 longueur 5

longueur 4

longueur 4 longueur 4
longueur 4 longueur 4 longueur 3

longueur 3 longueur 2

Solution Exercice 49. Pour rajouter le mot SORT, il suffit de prolonger l’arbre à l’aide d’une nouvelle « branche »
(voir figure (a)).
Le mot SOU est « déjà présent » dans l’arbre… simplement, il se termine sur un sommet interne de l’arbre, et
non sur une feuille. Il est donc nécessaire de distinguer, parmi les sommets internes (non feuilles) de l’arbre,
ceux qui correspondent à un mot du dictionnaire… Il suffit par exemple pour cela de « marquer » (ou colorier)
ces sommets à l’aide d’une marque particulière… Il est également possible (mais non nécessaire) de marquer
les feuilles de l’arbre… (voir figure (b)).

A S A S

B C O B C O

A I T U R A I T U R

T M E U T T T M E U T T

E E E E E E

L L

figure (a) figure (b)

Pour rechercher un mot dans un tel arbre, il suffit de partir de la racine et de « chercher » les lettres du mot une
à une. Lorsqu’on est sur un sommet et que l’on cherche une lettre, on parcourt les fils de ce sommet (les fils
sont triés de gauche à droite par ordre alphabétique). Si la lettre n’est pas présente, le mot n’est pas dans le
dictionnaire. Dans le cas contraire, on rejoint le fils trouvé et l’on passe à la lettre suivante… Si l’on trouve la
dernière lettre du mot, et que le sommet correspondant est marqué, le mot est bien présent dans le dictionnaire.

Solution Exercice 50. Il est possible, pour chacun des sommets du graphe, de calculer le nombre de traversées
à la nage nécessaires si l’école est implantée dans le village correspondant… On obtient alors :

Éléments de théorie des graphes - Solutions des exercices d’application page 20

Éric SOPENA - [email protected] avril 2002

(2x8 + 2x3 + 7x2 + 4x9 + 1x5 + 2x3 = 83)

2
2 8 0
83 59
1
59
3
2
5
5
99 1
2 199
9
125 3
87

Nous avons ainsi le choix entre deux villages qui obtiennent le meilleur score (59)…

Solution Exercice 51. Il suffit de prendre le temps de les énumérer…

• nous obtenons 4 arbres couvrants pour le premier graphe :

• 8 arbres couvrants pour le deuxième graphe :

• et 16 arbres couvrants pour le troisième graphe :

6.2. Graphes hamiltoniens

Solution Exercice 52. Désignons par 1,2,…,9 les 9 personnes et considérons le graphe complet K9 à 9 sommets.
Une composition de la table correspond à un cycle hamiltonien de K9 (un cycle passant une et une seule fois
par chaque sommet). Si deux compositions de table correspondent à deux cycles ayant une arête commune,
cela signifie que les deux personnes reliées par cette arête se retrouvent côte à côte… Ainsi, le problème
revient à déterminer le nombre de cycles hamiltoniens disjoints de K9…
Le graphe K9 possédant 9 x 8 / 2 = 36 arêtes et chaque cycle utilisant 9 arêtes, ce nombre est au maximum
égal à 4… Il vaut effectivement 4, comme le prouvent les 4 cycles hamiltoniens disjoints suivants :
1,2,3,9,4,8,5,7,6 — 1,3,4,2,5,9,6,8,7 — 1,4,5,3,6,1,7,9,8 — 1,5,6,4,7,2,8,1,9

Éléments de théorie des graphes - Solutions des exercices d’application page 21

Éric SOPENA - [email protected] avril 2002

Remarque. Ces cycles hamiltoniens ne sont pas obtenus « par hasard » (c’est également le cas pour la solution
de l’exercice 10). En les observant attentivement, on peut remarquer qu’ils sont construits de la façon suivante :
premier cycle : 1,2,3,N,4,N-1,5,N-2,6,N-3,etc., où N représente le nombre total de sommets…
deuxième cycle : on conserve le « 1 » et on ajoute 1 aux autres éléments, avec la règle N+1 = 2.
chaque cycle est alors obtenu du précédent en conservant le « 1 » et en ajoutant 1 aux autres éléments
(toujours avec la règle N+1=2…
Avec 10 élèves, nous avons 10 x 9 / 2 = 45 arêtes, soit 4 cycles hamiltoniens disjoints possibles (chaucn
utilisant 10 arêtes). Avec 11 élèves, nous avons 11 x 10 / 2 = 55 arêtes, soit 5 cycles hamiltoniens disjoints
possibles (chacun utilisant 11 arêtes). Dans les deux cas, il est possible de trouver les cycles correspondants :
pour 10 :
1,2,3,10,4,9,5,8,6,7 — 1,3,4,2,5,10,6,9,7,8 — 1,4,5,3,6,2,7,10,8,9 — 1,5,6,4,7,3,8,2,9,10
Lorsque N est pair, comme 10 ici, les arêtes restantes forment un couplage (elles sont non incidentes). En effet,
il nous reste ici les arêtes 1-6, 2-10, 3-9, 4-8, 5-7 (voir également la solution de l’exercice 10).

pour 11 :
1,2,3,11,4,10,5,9,6,8,7 — 1,3,4,2,5,11,6,10,7,9,8 — 1,4,5,3,6,2,7,11,8,10,9
1,5,6,4,7,3,8,2,9,11,10 — 1,6,7,5,8,4,9,3,10,2,11
En règle générale, k solutions sont possibles pour n = 2k+1 ou n = 2k+2 (plus un couplage pour n = 2k+2).

Revenons au cas des 9 personnes, cette fois avec une table de 4 places et une table de 5 places… Il s’agit
toujours de décomposer le graphe complet en ensembles disjoints de 9 arêtes, mais cette fois, chaque
ensemble doit correspondre à un cycle de 4 arêtes + un cycle de 5 arêtes. Avec trois tables de 3, chaque
ensemble doit correspondre à trois tirangles…
Le nombre maximum de solutions discuté précédemment reste donc valable dans ces deux situations : nous
aurons au plus 36 / 9 = 4 solutions… Là encore, on peut trouver 4 solutions :
une table de 4 et une table de 5 :
Je n’ai pas de solution « sous la main », mais je publierai la première
solution qui me parviendra… ;-)
trois tables de 3 :
(1,2,3)(4,5,6)(7,8,9) — (1,4,7)(2,5,8)(3,6,9) — (1,5,9)(2,6,7)(3,4,8) — (1,6,8)(2,4,9)(3,5,7)
Notons que pour chacune des situations de cet exercice, plusieurs solutions sont possibles…

Solution Exercice 53. L’idée de base est la même que pour l’exercice précédent, mais cette fois, du fait de
l’alternance imposée fille / garçon, on raisonne sur le graphe biparti complet K6,6 (six filles et six garçons)… Ce
graphe comprend 6 x 6 = 36 arêtes, et chaque cycle hamiltonien en nécessite 12. Il y a donc au maximum 3
solutions. En fait, trois solutions sont effectivement possibles (fi représente la i-ième fille, gi le i-ième garçon),
par exemple :
( f1,g1,f2,g2,f3,g3,f4,g4,f5,g5,f6,g6) — (f1,g3,f2,g4,f3,g5,f4,g6,f5,g1,f6,g2) — (f1,g5,f2,g6,f3,g1,f4,g2,f5,g3,f6,g4)

Solution Exercice 54. Le graphe en question (connu sous le nom de graphe de Petersen) n’est pas hamiltonien.
On peut par contre trouver un chemin hamiltonien, comme l’indique la figure ci-dessous.

Solution Exercice 55. Il s’agit cette fois de trouver des cycles hamiltoniens dans le complémentaire du graphe.
En voici un : B,C,H,A,F,G,E,D.
Que dire du nombre total de solutions ? il suffit de prendre le temps de les énumérer (ce que je n’ai pas encore
fait ;-)…

7. BIBLIOGRAPHIE
BERGE, Claude. Graphes et Hypergraphes. éd. Dunod, Paris (1970).
GONDRAN, Michel, et MINOUX, Michel. Graphes et Algorithmes. éd. Eyrolles, Paris (1979).
LABELLE, Jacques. Théorie des graphes. éd. Modulo, Québec (1981).
Éléments de théorie des graphes - Solutions des exercices d’application page 22
Éric SOPENA - [email protected] avril 2002

ROY, Bernard. Algèbre moderne et théorie des graphes orientées vers les sciences économiques et
sociales. Tome 1 : Notions et résultats fondamentaux. éd. Dunod, Paris (1969).
ROY, Bernard. Algèbre moderne et théorie des graphes orientées vers les sciences économiques et
sociales. Tome 2 : Applications et problèmes spécifiques. éd. Dunod, Paris (1970).

Éléments de théorie des graphes - Solutions des exercices d’application page 23