Solutions
454
En ini tia li sant le par cours par l’ouver ture du som met A, nous abou tis sons aux numé ro ta tions
de la figure 3.9. Les racines A et C de la forêt que nous avons obte nue ont un unique suc ces -
seur dans leur arborescence et ne sont donc pas par consé quent des som mets d’arti cu lation.
Le som met B, qui a pour ordre de prévisite 2, a pour suc ces seur le som met G pour lequel la
hau teur cal cu lée est 3; or 3 > 2 donc Β est un som met d’arti cu lation. G est aussi un som met
d’arti cu lation puisque son suc ces seur Ε dans l’arbo res cence a une hau teur 3 égale à la valeur
de prévisite de G. Les autres som mets du graphe ne sont pas des som mets d’arti cu lation
puisque tous leurs suc ces seurs dans l’arbo res cence ont des hau teurs infé rieures au rang du
som met dans la liste de prévisite.
3.5 1) Sup po sons que le graphe ait un cycle de lon gueur impaire. Nous pou vons noter
[x 1 , x 2 , c , x 2n+1 , x 1 ] ce cycle. Si x 1 PX alors x 2 PY puisqu’une arête relie x 1 et x 2 . Alors
x 3 PX , et ainsi de suite. Donc tous les som mets d’indice impair sont des élé ment de X. Mais
{x 1 , x 2n+1 } est une arête du cycle ayant ses deux extré mi tés dans l’ensemble X, donc le graphe
ne peut pas être biparti.
Sup po sons main te nant que tous les cycles du graphe soient de lon gueur paire. Effec tuons
un par cours de ce graphe en colo rant les som mets de la manière sui vante : le som met ini tia -
li sant le par cours est coloré en bleu. À chaque fois qu’un som met est ouvert, il est coloré en
bleu si le som met ayant per mis son ouver ture est coloré en rouge, et réci pro que ment le som -
met est coloré en rouge si le som met ayant per mis son ouver ture est coloré en bleu. Ainsi à la
fin du par cours chaque som met est soit bleu soit rouge. Les arêtes du graphe cor res pon dant à
un arc de la forêt rela tive au par cours ont leurs deux extré mi tés de cou leurs dif fé rentes étant
donné la manière dont les som mets ont été colo rés.
Consi dé rons les autres arêtes [x, y] : il y a une chaîne reliant x et y dans la forêt rela tive
au par cours. L’ajout de l’arête [x, y] à cette chaîne cor res pond à un cycle, de lon gueur
paire par hypo thèse. La chaîne reliant x et y dans la forêt a donc un nombre impair d’arêtes.
Cette chaîne appar te nant à la forêt, ses som mets sont colo rés alter na ti ve ment en bleu et
rouge, les deux som mets extré mi tés de cette chaîne ont donc des cou leurs dif fé rentes. Donc
pour toute arête du graphe, l’une de ses extré mi tés est rouge et l’autre est bleue. En par -
tition nant l’ensemble des som mets sui vant leur cou leur, nous véri fions alors que le graphe
est biparti.
2) Nous venons de voir dans la démons tra tion pré cé dente com ment un par cours per met
de colo rer avec deux cou leurs les som mets d’un graphe biparti. Pour véri fier qu’un graphe
est biparti, il suf fit donc d’effec tuer un par cours et de véri fier que chaque arête a ses deux
extré mi tés de cou leurs dif fé rentes.
3.6 1) Si (y, x) est un arc arrière, en ajou tant cet arc au che min allant de x à y dans
l’arborescence du parcours nous obte nons un cir cuit dans le graphe donné.
Réci pro que ment, consi dé rons un cir cuit du graphe. Soit x le pre mier som met visité de ce
cir cuit dans l’ordre de prévisite et y le pré dé ces seur de x dans ce cir cuit. Le som met y étant
aussi un descendant de x il y a néces sai re ment un che min de x à y dans l’arbo res cence du
fait que le par cours s’effec tue en pro fon deur (cette prop riété a été mon trée dans le cas des
graphes non orien tés, il est laissé le soin au lec teur de véri fier que la démons tra tion don née
est encore valide pour les graphes orien tés), et de ce fait (y, x) est un arc arrière.
2) Nous avons vu que la com plexité d’un par cours en pro fon deur est O(max(m, n)). La
détec tion d’un arc arrière (y, x) peut se faire simul ta né ment au par cours sans ajou ter d’opé ra -
tion sup plé men taire. Il suf fit lors de la visite du som met y, au cours de l’exa men du som met
x (suc ces seur de y) de véri fier que x est ouvert.
454
En ini tia li sant le par cours par l’ouver ture du som met A, nous abou tis sons aux numé ro ta tions
de la figure 3.9. Les racines A et C de la forêt que nous avons obte nue ont un unique suc ces -
seur dans leur arborescence et ne sont donc pas par consé quent des som mets d’arti cu lation.
Le som met B, qui a pour ordre de prévisite 2, a pour suc ces seur le som met G pour lequel la
hau teur cal cu lée est 3; or 3 > 2 donc Β est un som met d’arti cu lation. G est aussi un som met
d’arti cu lation puisque son suc ces seur Ε dans l’arbo res cence a une hau teur 3 égale à la valeur
de prévisite de G. Les autres som mets du graphe ne sont pas des som mets d’arti cu lation
puisque tous leurs suc ces seurs dans l’arbo res cence ont des hau teurs infé rieures au rang du
som met dans la liste de prévisite.
3.5 1) Sup po sons que le graphe ait un cycle de lon gueur impaire. Nous pou vons noter
[x 1 , x 2 , c , x 2n+1 , x 1 ] ce cycle. Si x 1 PX alors x 2 PY puisqu’une arête relie x 1 et x 2 . Alors
x 3 PX , et ainsi de suite. Donc tous les som mets d’indice impair sont des élé ment de X. Mais
{x 1 , x 2n+1 } est une arête du cycle ayant ses deux extré mi tés dans l’ensemble X, donc le graphe
ne peut pas être biparti.
Sup po sons main te nant que tous les cycles du graphe soient de lon gueur paire. Effec tuons
un par cours de ce graphe en colo rant les som mets de la manière sui vante : le som met ini tia -
li sant le par cours est coloré en bleu. À chaque fois qu’un som met est ouvert, il est coloré en
bleu si le som met ayant per mis son ouver ture est coloré en rouge, et réci pro que ment le som -
met est coloré en rouge si le som met ayant per mis son ouver ture est coloré en bleu. Ainsi à la
fin du par cours chaque som met est soit bleu soit rouge. Les arêtes du graphe cor res pon dant à
un arc de la forêt rela tive au par cours ont leurs deux extré mi tés de cou leurs dif fé rentes étant
donné la manière dont les som mets ont été colo rés.
Consi dé rons les autres arêtes [x, y] : il y a une chaîne reliant x et y dans la forêt rela tive
au par cours. L’ajout de l’arête [x, y] à cette chaîne cor res pond à un cycle, de lon gueur
paire par hypo thèse. La chaîne reliant x et y dans la forêt a donc un nombre impair d’arêtes.
Cette chaîne appar te nant à la forêt, ses som mets sont colo rés alter na ti ve ment en bleu et
rouge, les deux som mets extré mi tés de cette chaîne ont donc des cou leurs dif fé rentes. Donc
pour toute arête du graphe, l’une de ses extré mi tés est rouge et l’autre est bleue. En par -
tition nant l’ensemble des som mets sui vant leur cou leur, nous véri fions alors que le graphe
est biparti.
2) Nous venons de voir dans la démons tra tion pré cé dente com ment un par cours per met
de colo rer avec deux cou leurs les som mets d’un graphe biparti. Pour véri fier qu’un graphe
est biparti, il suf fit donc d’effec tuer un par cours et de véri fier que chaque arête a ses deux
extré mi tés de cou leurs dif fé rentes.
3.6 1) Si (y, x) est un arc arrière, en ajou tant cet arc au che min allant de x à y dans
l’arborescence du parcours nous obte nons un cir cuit dans le graphe donné.
Réci pro que ment, consi dé rons un cir cuit du graphe. Soit x le pre mier som met visité de ce
cir cuit dans l’ordre de prévisite et y le pré dé ces seur de x dans ce cir cuit. Le som met y étant
aussi un descendant de x il y a néces sai re ment un che min de x à y dans l’arbo res cence du
fait que le par cours s’effec tue en pro fon deur (cette prop riété a été mon trée dans le cas des
graphes non orien tés, il est laissé le soin au lec teur de véri fier que la démons tra tion don née
est encore valide pour les graphes orien tés), et de ce fait (y, x) est un arc arrière.
2) Nous avons vu que la com plexité d’un par cours en pro fon deur est O(max(m, n)). La
détec tion d’un arc arrière (y, x) peut se faire simul ta né ment au par cours sans ajou ter d’opé ra -
tion sup plé men taire. Il suf fit lors de la visite du som met y, au cours de l’exa men du som met
x (suc ces seur de y) de véri fier que x est ouvert.