Université de M’sila Département d’informatique
Module: Optimisation des Réseaux 2ème Année Master (M2RTIC)
TD03 (2023-2024)
TD N°03 : Algorithmes de Graphes
Exercice 1.1 (Question à choix multiples (QCM))
Choisir la bonne ou les bonnes réponses.
1. Laquelle de ces affirmations concernant des arbres est fausse ?
a) la racine peut être une feuille
b) un nœud interne possède toujours au moins un fils
c) la racine possède toujours au moins un fils
d) la racine ne possède jamais de père.
2. Dans l’arbre de la Fig. 1, le nœud 5 est :
a) une feuille b) un nœud interne
c) une racine d) aucun des trois.
3. Un parcours de l’arbre de la Fig. 1 qui traite les nœuds dans l’ordre 1, 2, 3, 4, 5, 6, 7,
8, 9 puis 10 est un parcours :
a) Préfixe b) infixe c) post-fixe d) en largeur
4. Un parcours de l’arbre de la Fig. 1 qui traite les nœuds dans l’ordre 8, 4, 9, 2, 5, 1,
10, 6, 3 puis 7 est un parcours :
a) Préfixe b) infixe c) post-fixe d) en largeur
5. Un parcours de l’arbre de la Fig. 1 qui traite les nœuds dans l’ordre 8, 9, 4, 5, 2, 10,
6, 7, 3 puis 1 est un parcours :
a) Préfixe b) infixe c) post-fixe d) en largeur
6. Laquelle de ces trois affirmations est fausse ?
a) un tas est un arbre complet b) un tas est un arbre équilibré
c) un tas est un arbre binaire de recherche d) les trois sont justes.
7. Le parcours en profondeur d'un arbre binaire correspond à un fonctionnement de :
a) File (First In First Out) b) Pile (First In Last Out)
c) Liste chaînée d) Graphe orienté.
8. On souhaite calculer tous les plus courts chemins d'un nœud donné à tous les
autres nœuds dans un graphe orienté, qui peut contenir des cycles et dont les arcs
peuvent avoir des poids négatifs, mais sans cycle absorbant. Quel est le meilleur
algorithme pour résoudre ce problème ?
a) L'algorithme qui fait un tri topologique des nœuds b) Bellman-Ford
c) Dijkstra d) Floyd-Warshall.
9. L’algorithme de Dijkstra permet la recherche de plus courts chemins dans un
graphe pondère, orienté ou non. Pour qu’il fonctionne, le graphe doit avoir l’une des
propriétés suivantes, laquelle?
a) Le graphe doit être sans cycles.
b) Les poids des arcs/arêtes doivent être positifs.
c) Le graphe doit être connexe.
d) Les poids des arcs/arêtes doivent être tous différents.
Dr. Ali Dabba 1/4
Université de M’sila Département d’informatique
Module: Optimisation des Réseaux 2ème Année Master (M2RTIC)
TD03 (2023-2024)
10. Combien un graphe orienté sans cycles possédant n sommets peut-il posséder
d’arcs au maximum ?
a) n – 1 b) [n(n − 1)]/2 c) n(n − 1) d) 2n.
Exercice 1.2 (Algorithme de Dijkstra)
Soit le graphe non orienté valué de la figure suivante.
Utilisez l’algorithme de Dijkstra pour calculer le plus
court chemin entre le sommet a et le sommet j. Pour
cela, utilisez le tableau de calcul ci-dessous. La
première ligne de ce tableau correspond à l’étape
d’initialisation de l’algorithme. Chaque itération de
l’algorithme est représentée par une nouvelle ligne
dans le tableau de calcul : sélection du sommet
devant être marqué puis actualisation des sommets
adjacents. S’il y a plusieurs choix possibles pour
sélectionner le sommet à marquer, utilisez l’ordre
alphabétique.
a b c d e f g h i J 1) Donnez le chemin obtenu de a vers j
Init et son coût.
1 2) Si on cherche le plus court chemin de f
2 vers c, faut-il relancer l’algorithme ?
3 Justifiez la réponse.
4
3) Dans le cas général que faut-il faire ?
5
Justifiez la réponse.
6
7 4) Pouvez-vous utiliser d’autres
8 algorithmes à la place de l’algorithme
9 de Dijkstra ? Pourquoi utiliser celui
10 de Dijkstra plutôt qu’un autre ?
Exercice 1.3 (Algorithme de Bellman-Ford)
Soit le graphe orienté valué de la figure suivante.
Utilisez l’algorithme de Bellman-Ford pour calculer
le plus court chemin depuis le sommet a vers le
sommet b. Pour cela, utilisez le tableau de calcul
ci-dessous. La première ligne de ce tableau
correspond à l’étape d’initialisation de l’algorithme.
Chaque itération de l’algorithme correspond à une
ligne dans le tableau de calcul : actualisation de
tous les sommets du graphe pris dans l’ordre
alphabétique.
Question : Donnez le chemin obtenu et son coût.
Dr. Ali Dabba 2/4
Université de M’sila Département d’informatique
Module: Optimisation des Réseaux 2ème Année Master (M2RTIC)
TD03 (2023-2024)
a b c d e f
Init
1
2
3
4
5
6
Exercice 1.4
Des touristes sont logés dans un hôtel H. Un guide
souhaite faire visiter la région à ces touristes en
empruntant les routes signalées comme d’intérêt
touristique par l’office du tourisme. Les tronçons
de route qu’il souhaite emprunter sont représentés
sur le graphe ci-contre. Le long de chaque arête
figure la distance en kilomètres des différents
tronçons.
1) Le guide peut-il emprunter tous les tronçons
de route en passant une et une seule fois sur
chacun d’eux, en partant de l’hôtel et en y
revenant ? Justifier la réponse.
2) Le guide peut-il emprunter tous les tronçons de route en passant une et une seule
fois sur chacun d’eux, en partant de l’hôtel mais sans forcément y revenir ? Justifier
la réponse.
3) Un musée est situé en E. Déterminer le plus court chemin menant de l’hôtel H au
musée E. Justifier la réponse.
Exercice 1.5
On oriente et on pondère le graphe G ci-
dessus pour qu’il représente un réseau
d’irrigation.
➢ Le sommet A correspond au départ
d’eau, le sommet K au bassin
d’infiltration et les autres sommets
représentent les stations de
régulation.
➢ Les arêtes représentent les canaux d’irrigation et les flèches, le sens du
ruissellement.
➢ La pondération donne, en km, les distances entre les différentes stations du
réseau.
Question : Déterminer un chemin de longueur minimale entre le départ d’eau en A et le
bassin d’infiltration en K et donner sa longueur.
Dr. Ali Dabba 3/4
Université de M’sila Département d’informatique
Module: Optimisation des Réseaux 2ème Année Master (M2RTIC)
TD03 (2023-2024)
Exercice 1.6
Appliquez l’algorithme de Bellman-Ford sur le
digraphe suivant pour déterminer le plus
court chemin de s à p.
Exercice 1.7 (Arbre couvrant minimal)
Appliquer les algorithmes de Prim et de Kruskal au graphe ci-dessous.
Exercice 1.8 (Algorithmes Kruskal & Prim)
1) Trouver un arbre couvrant de poids
minimal sur les graphes suivants en
appliquant (On représentera la file de
priorité à chaque itération.)
a) l’algorithme de Kruskal.
b) l’algorithme de Prim
2) Donnez le résultat final : arbre couvrant
minimum.
Exercice 1.9
1) Faire tourner l’algorithme de
Kruskal et celui de Prim sur
les graphes suivants:
2) Quel est le poids d’un arbre
couvrant de poids minimal?
Dr. Ali Dabba 4/4
