Théorie des graphes : Parcours en profondeur et en largeur
Télécharger PDFphilippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
Parcours en profondeur et en largeur
Math ́ematiques
TD n◦ 4
Exercice1
SoitGle graphe orient ́e ci-
contre, en partant du som-
mets= 5 faire les parcours
demand ́es en pr ́ecisant :
•l’arbre de parcours
•lalistedes
pr ́ed ́ecesseurs
•l’ordre de parcours1 23 45 67 89 1011 1213 1415 1. en largeur
(a) par ordre croissant
(b) par ordre d ́ecroissant
(c) en d ́eduire les distances
d(5,14),d(5,2) etd(5,9)
2. en profondeur
(a) par ordre croissant
(b) par ordre d ́ecroissant
(c) donner l’ordre de num ́erotationsuffixe 12 34 56 78 910 1112 1314 151 23 45 67 89 1011 1213 1415 12 34 56 78 910 1112 1314 151 23 45 67 89 1011 1213 1415 1
philippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
Parcours en profondeur et en largeur
Math ́ematiques
TD n◦ 4
Exercice2
classification des arcs1 234 5678 9
1. Construire l’arborescence du parcours en profondeur, `a partir du sommet 2 (par
ordre d ́ecroissant des num ́eros de sommet), du grapheGci-dessus.
2. Calculer les num ́erotations pr ́efixe et suffixe du parcours pr ́ec ́edent, donner les
r ́esultats sous forme de deux tableaux tels que pref(x) = num ́erotation pr ́efixe de
xet suff(x) = num ́erotation suffixe dex
3. Classer les arcs du grapheG(selon les quatre cat ́egories : arcs couvrants, arcs
r ́etrogrades, arcs directs, arcs traversiers) et les rajoutersur l’arborescence du par-
cours en profondeur, puis sur le graphe ci-dessous :1 234 5678 9
en noir les arcs couvrants
en bleu les arcs directs
en vert les arcs traversiers
en rouge les arcs r ́etrogrades4. `
A partir du parcours de cet exercice
(a) quels type d’arcs (x, y) v ́erifient pref(x)<pref(y)
(b) quels type d’arcs (x, y) v ́erifient pref(x)≥pref(y)
(c) quels type d’arcs (x, y) v ́erifient suff(x)≤suff(y)
(d) quels type d’arcs (x, y) v ́erifient suff(x)>suff(y)
5. Le d ́emontrer dans le cas g ́en ́eral.
6. En d ́eduire une m ́ethode pour d ́eterminer le type d’un arc.2 philippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
Parcours en profondeur et en largeur
Math ́ematiques
TD n◦ 4
Exercice3
Algorithme de Prim` A l’aide de l’algorithme de Prim chercher un arbre couvrant de poids optimal pour les
graphes ci-dessous :
•arbre couvrant de poids minimal deG 11 23 45 6204 120 413 1117 16
•arbre couvrant de poids minimal deG 21 234 56 715 178 51517 1210 619 168 5
•arbre couvrant de poids maximal deG 31 234 56 142 2012 96 16 194 •arbre couvrant de poids minimal deG 41 23 45 67 89 102 2016 1210 37 515 96 55 51 1411 30 719 3
philippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
Parcours en profondeur et en largeur
Math ́ematiques
TD n◦ 4
Exercice4
Parcours de graphe [DS 2010, 5pts]
SoitGle graphe orient ́e suivant :12 34 567 89101112 1. (a) Faire le parcours en largeur deGdepuis le sommets= 1 parordre croissant
des sommets et repr ́esenter l’arbre de parcours obtenu.
(b) Donner la liste de pr ́ed ́ecesseur correspondant `a l’arbre deparcours ainsi que
l’ordre de parcours des sommets.
Indication :On donnera l’ordre de parcours sous forme d’une liste telle que
ordre(x) =ordre de parcours du sommetx
2. (a) Faire le parcours en profondeur deGdepuis le sommets= 1 parordre
d ́ecroissantdes sommets et repr ́esenter l’arbre de parcours obtenu.
(b) Donner les ordres de parcours pr ́efixe et suffixe correspondant au parcours.
(c) Faire le classement des arcs :
•en noir les arcs couvrants
•en bleu les arcs directs
•en vert les arcs traversiers
•en rouge les arcs r ́etrogrades
Indication :On coloriera les arcs du graphes en gardant la mˆeme disposi-
tion des sommets que celle donn ́ee au d ́ebut du sujet (mˆeme si au broullon on
pourra trouver le type de chaque arc en se basant sur l’arbre de parcours dessin ́e
question 2)a).