Maths discrètes, 2012-2013 Université Paris-Sud

Corrigé du devoir no 2
Exercice 1.
a) Un graphe à 6 sommets de degrés 1, 2, 3, 4, 5, 5 existe, voici deux exemples (le premier avec
une boucle, le second sans boucle) :

Remarque : ce ne peut pas être un graphe simple en raison de la question b), un tel graphe a
donc nécessairement des arêtes multiples ou des boucles.
b) Supposons que G soit un graphe simple à 6 sommets A, B, C, D, E, F de degrés respec-
tifs 1, 2, 3, 4, 5, 5. Le sommet E est de degré 5 donc, comme G est un graphe simple,
E est nécessairement voisin des 5 autres sommets A, B, C, D, F . De même, F est voisin de
A, B, C, D, E. Par conséquent, A est voisin de E et F . Mais ceci contredit le fait que A est de
degré 1. Conclusion : un tel graphe n’existe pas.
Exercice 2. On peut représenter le tournoi par un graphe dont les sommets représentent les
équipes et les arêtes les parties jouées.
a) On peut reformuler la question comme suit dans le langage de la théorie des graphes :
existe-t-il un graphe à 7 sommets dont tous les sommets sont de degré 5 ?
Si S est l’ensemble des sommets du graphe, on a alors
X
d(s) = 7 × 5 = 35,
s∈S

ce qui contredit le théorème des poignées de mains. Un tel graphe n’existe donc pas. Il est
impossible de faire jouer 5 parties à chaque équipe.
b) On peut reformuler la question comme suit dans le langage de la théorie des graphes :
existe-t-il un graphe à 7 sommets dont tous les sommets sont de degré 4 ?
X
Notons que d(s) = 7 × 4 = 28 (où S est l’ensemble des sommets), donc ceci ne contredit pas
s∈S
le théorème des poignées de mains (mais ce théorème ne garantit pas l’existence d’un graphe).
Voici deux tels graphes qui conviennent. Il est donc possible de faire jouer 4 parties à chaque
équipe.

• •
~  ** @@ ~  ** @@
~~~  ** @@@ ~~~  ** @@@
~  * @@ ~  * @@
~ ~~  ** @@ ~ ~~  ** @@
W
•/ JJWWWWW~~  ** @@ggggt • W
•/ JJWWWWW~~  ** @@ggggt •
W  g W  g
J ~
// JJ~ WWWW W
~ J  W Wg g g *g* gggg @t@t@tt  J ~
// JJ~ WWWW W
~ J  W Wg g g *g* gggg @t@t@tt 
//~~ JJ g ggggWWWW* W tt @@ //~~ JJ g ggggWWWW* W tt @@
g
~~/g/ ggggJgJJJ * WtWtWWWWW @ g
~~/g/ ggggJgJJJ * WtWtWWWWW @
• UgUgU//U  JJ t t*t*  W • gUUgU//U  JJ t t*t*  W
//UUUU JJ ttt ** iiii ii • //UUUU JJ ttt ** iiii ii •
// UUUtUtUttJJiJiJiii**i  // UUUtUtUttJJiJiJiii**i 
/  ttitiiiUiUiUUUJUJJ *  /  ttitiiiUiUiUUUJUJJ * 
• iti •
U
• iti •
U
Exercice 3.
a) On représente la situation par un graphe dont les sommets sont les 10 villes, et il y a une
arête entre deux villes s’il à a des trains entre elles. On peut aller de n’importe quelle ville
à n’importe quelle autre ville en train si le graphe est connexe. Appliquons l’algorithme de
distance en partant du sommet A. On obtient les étiquettes ci-dessous. On en déduit que le
graphe est connexe, donc on peut aller de n’importe quelle ville à n’importe quelle autre ville
en train.
A (0) B (1)

J (2)
C (1)

D (2)
I (1)

E (2)
H (3)
F (3)
G (2)

b) Le nombre minimum de trains qu’il faut prendre pour aller de A à F est la distance entre
A et F dans le graphe. L’algorithme de distance en partant de A (ci-dessus) montre que cette
distance est 3. Il faut donc prendre au minimum 3 trains, autrement dit il faut changer au moins
2 fois de train. Les deux itinéraires possibles sont : ABGF et AIGF .
c) La question revient à savoir s’il existe un chemin eulérien d’extrémités A et F dans le graphe
ci-dessus. Le graphe est connexe par la question a). Les degrés des extrémités sont impairs
(d(A) = 3, d(F ) = 1) et les degrés des autres sommets sont pairs (d(B) = 6, d(C) = d(D) =
d(E) = d(G) = d(I) = 4, d(H) = d(J) = 2). Donc, par le théorème d’Euler, il existe un
chemin eulérien d’extrémités A et F. Conclusion : il est possible de faire un voyage partant de
A, arrivant en F et empruntant une fois et une seule chaque train.
d) Les gares B et I étant fermées, on supprime toutes les arêtes ayant B ou I comme extrémité.
On obtient un nouveau graphe, dessiné ci-dessous. L’algorithme de distance partant de A dans
ce graphe montre que F est dans la composante connexe de A. Donc il est encore possible d’aller
en train de A à F. Dans ce graphe, la distance entre A et F est égale à 4, donc il faut prendre
au minimum 4 trains, autrement dit il faut changer de trains 3 fois au minimum.
A (0) B

J (4)
C (1)

D (2)
I

E (2)
H (3)
F (4)
G (3)