Solutions
452
Solu tionS deS exer ciceS du cha pitre 3
3.1 1) G
1
(A) 5 5F, C6; G
1
(B) 5 5A, B, C, D6; G
2
(A) 5 5B, F6; G
2
(B) 5 5B6
2) d
2
A 5 2 ; d
2
B 5 1 ; d
2
C 5 3 ; d
2
D 5 2 ; d
2
E 5 2 ; d
2
F 5 2
d
1
A 5 2 ; d
1
B 5 4 ; d
1
C 5 1 ; d
1
D 5 3 ; d
1
E 5 0 ; d
1
F 5 2 ;
E est une “sor tie” car le som met E n’a pas de suc ces seur : d
1
E 5 0 car G
1
(E) 5 [ .
Si l’on sup prime la boucle (B, B), alors B devient une entrée.
NB : la somme des demi- degrés inté rieurs (resp. exté rieurs) de tous les som mets est égale
au nombre d’arcs : en effet cette somme revient à comp ter les arcs par leur extré mité ini tiale
(resp. terminale), ici m = 12.
3) (B, D, C, D, E) est un che min simple : aucun de ses arcs n’est emprunté plu sieurs fois ;
mais ce che min n’est pas élé men taire : il passe deux fois par D.
4) Puisque le graphe com porte une sor tie, le som met E qui est sans suc ces seur, aucun
cir cuit ne peut pas ser par E ; en par ti cu lier, pas un cir cuit hamiltonien.
Si G com porte un che min hamiltonien, celui- ci doit par tir de l’entrée B (sup pri mer la
boucle) pour arri ver à la sor tie E. On trouve alors faci le ment le che min hamiltonien (B, A,
C, D, F, E).
5) G com por tant une sor tie, il n’est pas for te ment connexe : depuis E il n’existe pas de
che min vers les autres som mets. Mais l’ajout de l’arc (E, B) le rendrait fortement connexe.
6) B est néces sai re ment la racine des arbo res cences cherc hées. En voici deux :
B
A
C
E
D
F
B
A
C
D
E
F
Une troi sième arbo res cence (par ti cu lière, car sans rami fi ca tion) est le che min hamiltonien du 4.
3.2 On cherche un par cours (non orienté) pas sant par tous les points une fois et une seule.
En termes de graphes : une chaîne (ou un cycle) eulérienne.
Sup po sons le pro blème pos sible avec le point (sommet) de départ d dif fé rent du point
(sommet) d’arri vée a. Dans le dia gramme les degrés de d et de a seraient alors impairs ; les
autres som mets étant des points de pas sage, leur degré serait pair. Si d et a étaient confon dus,
tous les som mets du dia gramme auraient un degré pair. Bref le pro blème est pos sible si ce
dia gramme com porte au plus 2 som mets de degré impair. Or dans le dia gramme des 7 ponts,
les 4 som mets ont un degré impair (d A = d C = d D = 3 et d B = 5) : le pro blème est impos sible.
Avec un hui tième pont ajouté entre A et D, le pro blème est pos sible en par tant de B et en
finis sant en C (ou l’inverse).
3.3 1) Toute arête a deux extré mi tés : si l’on somme tous les degrés des sommets on compte
chaque arête deux fois ; cette somme vaut donc 2m (rap pel : m désigne le nombre d’arêtes
du graphe)
452
Solu tionS deS exer ciceS du cha pitre 3
3.1 1) G
1
(A) 5 5F, C6; G
1
(B) 5 5A, B, C, D6; G
2
(A) 5 5B, F6; G
2
(B) 5 5B6
2) d
2
A 5 2 ; d
2
B 5 1 ; d
2
C 5 3 ; d
2
D 5 2 ; d
2
E 5 2 ; d
2
F 5 2
d
1
A 5 2 ; d
1
B 5 4 ; d
1
C 5 1 ; d
1
D 5 3 ; d
1
E 5 0 ; d
1
F 5 2 ;
E est une “sor tie” car le som met E n’a pas de suc ces seur : d
1
E 5 0 car G
1
(E) 5 [ .
Si l’on sup prime la boucle (B, B), alors B devient une entrée.
NB : la somme des demi- degrés inté rieurs (resp. exté rieurs) de tous les som mets est égale
au nombre d’arcs : en effet cette somme revient à comp ter les arcs par leur extré mité ini tiale
(resp. terminale), ici m = 12.
3) (B, D, C, D, E) est un che min simple : aucun de ses arcs n’est emprunté plu sieurs fois ;
mais ce che min n’est pas élé men taire : il passe deux fois par D.
4) Puisque le graphe com porte une sor tie, le som met E qui est sans suc ces seur, aucun
cir cuit ne peut pas ser par E ; en par ti cu lier, pas un cir cuit hamiltonien.
Si G com porte un che min hamiltonien, celui- ci doit par tir de l’entrée B (sup pri mer la
boucle) pour arri ver à la sor tie E. On trouve alors faci le ment le che min hamiltonien (B, A,
C, D, F, E).
5) G com por tant une sor tie, il n’est pas for te ment connexe : depuis E il n’existe pas de
che min vers les autres som mets. Mais l’ajout de l’arc (E, B) le rendrait fortement connexe.
6) B est néces sai re ment la racine des arbo res cences cherc hées. En voici deux :
B
A
C
E
D
F
B
A
C
D
E
F
Une troi sième arbo res cence (par ti cu lière, car sans rami fi ca tion) est le che min hamiltonien du 4.
3.2 On cherche un par cours (non orienté) pas sant par tous les points une fois et une seule.
En termes de graphes : une chaîne (ou un cycle) eulérienne.
Sup po sons le pro blème pos sible avec le point (sommet) de départ d dif fé rent du point
(sommet) d’arri vée a. Dans le dia gramme les degrés de d et de a seraient alors impairs ; les
autres som mets étant des points de pas sage, leur degré serait pair. Si d et a étaient confon dus,
tous les som mets du dia gramme auraient un degré pair. Bref le pro blème est pos sible si ce
dia gramme com porte au plus 2 som mets de degré impair. Or dans le dia gramme des 7 ponts,
les 4 som mets ont un degré impair (d A = d C = d D = 3 et d B = 5) : le pro blème est impos sible.
Avec un hui tième pont ajouté entre A et D, le pro blème est pos sible en par tant de B et en
finis sant en C (ou l’inverse).
3.3 1) Toute arête a deux extré mi tés : si l’on somme tous les degrés des sommets on compte
chaque arête deux fois ; cette somme vaut donc 2m (rap pel : m désigne le nombre d’arêtes
du graphe)