Théorie des graphes : Parcours en profondeur et en largeur
Télécharger PDFExercice 1 : Parcours en profondeur et en largeur
Soit G le graphe orienté ci-dessous. En partant du sommet 5, effectuer les parcours demandés en précisant :
- l’arbre de parcours
- la liste des prédécesseurs
- l’ordre de parcours
1. Parcours en largeur
(a) Par ordre croissant des sommets :
Effectuer un parcours en largeur en commençant par le sommet 5 et en visitant les sommets par ordre croissant.
(b) Par ordre décroissant des sommets :
Effectuer un parcours en largeur en commençant par le sommet 5 et en visitant les sommets par ordre décroissant.
(c) En déduire les distances :
Calculer les distances d(5,14), d(5,2) et d(5,9) à partir du parcours en largeur.
2. Parcours en profondeur
(a) Par ordre croissant des sommets :
Effectuer un parcours en profondeur en commençant par le sommet 5 et en visitant les sommets par ordre croissant.
(b) Par ordre décroissant des sommets :
Effectuer un parcours en profondeur en commençant par le sommet 5 et en visitant les sommets par ordre décroissant.
(c) Donner l’ordre de numérotation suffixe :
12 34 56 78 910 1112 1314 15
Exercice 2 : Classification des arcs
1. Construire l’arborescence du parcours en profondeur à partir du sommet 2, par ordre décroissant des numéros de sommet, du graphe G ci-dessus.
2. Calculer les numérotations préfixe et suffixe du parcours précédent et présenter les résultats sous forme de deux tableaux, où pref(x) = numéro de rotation préfixe de x et suff(x) = numéro de rotation suffixe de x.
3. Classer les arcs du graphe G selon les quatre catégories : arcs couvrants, arcs rétrogrades, arcs directs et arcs traversiers, puis les rajouter sur l’arborescence du parcours en profondeur et sur le graphe ci-dessous :
- en noir les arcs couvrants
- en bleu les arcs directs
- en vert les arcs traversiers
- en rouge les arcs rétrogrades
4. À partir du parcours de cet exercice
(a) Quels types d’arcs (x, y) vérifient pref(x) < pref(y) ?
(b) Quels types d’arcs (x, y) vérifient pref(x) ≥ pref(y) ?
(c) Quels types d’arcs (x, y) vérifient suff(x) ≤ suff(y) ?
(d) Quels types d’arcs (x, y) vérifient suff(x) > suff(y) ?
5. Le démontrer dans le cas général.
6. En déduire une méthode pour déterminer le type d’un arc.
Exercice 3 : Algorithme de Prim
À l’aide de l’algorithme de Prim, chercher un arbre couvrant de poids optimal pour les graphes suivants :
- Arbre couvrant de poids minimal du graphe G1
- Arbre couvrant de poids minimal du graphe G2
- Arbre couvrant de poids maximal du graphe G3
- Arbre couvrant de poids minimal du graphe G4
Exercice 4 : Parcours de graphe
Soit G le graphe orienté suivant :
12 34 56 78 910 1112
1. Parcours en largeur
(a) Effectuer le parcours en largeur de G depuis le sommet s = 1 par ordre croissant des sommets et représenter l’arbre de parcours obtenu.
(b) Donner la liste des prédécesseurs correspondant à l’arbre de parcours ainsi que l’ordre de parcours des sommets.
Indication : L’ordre de parcours sera donné sous forme de liste où ordre(x) = ordre de parcours du sommet x.
2. Parcours en profondeur
(a) Effectuer le parcours en profondeur de G depuis le sommet s = 1 par ordre décroissant des sommets et représenter l’arbre de parcours obtenu.
(b) Donner les ordres de parcours préfixe et suffixe correspondant au parcours.
(c) Classer les arcs du graphe G selon les quatre catégories :
- en noir les arcs couvrants
- en bleu les arcs directs
- en vert les arcs traversiers
- en rouge les arcs rétrogrades
Indication : Les arcs du graphe seront colorés en conservant la même disposition des sommets que celle donnée au début du sujet.
FAQ
Qu’est-ce qu’un parcours en largeur (BFS) ?
Un parcours en largeur explore un graphe niveau par niveau, en commençant par un sommet donné et en visitant tous ses voisins avant de passer à leurs voisins, etc.
Qu’est-ce qu’un parcours en profondeur (DFS) ?
Un parcours en profondeur explore un graphe en plongeant aussi loin que possible le long de chaque branche avant de revenir en arrière.
Comment déterminer les distances entre deux sommets lors d’un parcours en largeur ?
Les distances sont déterminées en comptant le nombre d’arcs traversés depuis le sommet de départ jusqu’au sommet cible dans l’arbre de parcours.