97
© Dunod – Toute reproduction non autorisée est un délit.
Exercices
**3.4 connexité d’un graphe
Consi dé rons le graphe ayant la matrice
d’adja cence symétrique sui vante :
1. Uti li ser un par cours de
ce graphe pour déter mi ner
son nombre de compo -
santes connexes.
2. Déter mi ner les som mets
d’arti cu lation de ce graphe
à l’aide d’un par cours en
pro fon deur.
**3.5 reconnais sance d’un graphe biparti
Nous rappellons qu’un graphe est biparti, s’il est pos sible de par tition ner l’ensemble de
ses som mets en deux sous- ensembles X et Y tels que chaque arête a du graphe ait une
extré mité x H X et l’autre extré mité y H Y. Autrement dit : il n y a pas d’arête entre deux
sommets de X (ou de Y ).
1. Mon trer qu’un graphe est biparti si et seule ment si il n’admet pas de
cycle de lon gueur impaire.
2. Mon trer qu’un par cours d’un graphe per met de déter mi ner si celui- ci
est ou non biparti.
*3.6 Détec tion de cir cuits par un par cours en profondeur
Lors d’un par cours d’un graphe orienté, un arc arrière est un arc (y, x) du graphe tel
qu’il existe un che min du som met x au som met y dans une des arborescences de la
forêt rela tive au par cours effec tué.
1. Mon trer qu’un graphe contient un cir cuit si et seule ment il existe un arc
arrière dans tout par cours en pro fon deur de ce graphe.
2. En déduire un algo rithme de complexité O(max(n, m)) qui per met de déter -
mi ner si un graphe est sans cir cuit.
3. Pour le graphe de la Figure 3.8, déterminer ses circuits : les arcs notés d’un
trait double donnent l’arborescence d’un parcours en
profondeur, de sommet initial A.
A B C D E F G H I
0
1
0
0
0
1
0
0
1
1
0
0
0
0
1
1
0
1
0
0
1
0
0
0
0
1
0
0
0
0
0
1
0
1
0
0
0
0
0
1
1
0
1
0
0
1
1
0
0
0
1
0
0
0
0
1
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
A
B
C
D
E
F
G
H
I
G
B
C
D
E
F
A