TD — Séance 5 — Graphes

Représentations, parcours, tri topologique, Dijkstra et Kruskal

TD de la séance 5 de Structures de données et algorithmes avancés : parcourir, ordonner, trouver le plus court chemin et l’arbre couvrant minimal.
Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

ImportantObjectif

Appliquer à la main, sur des graphes nouveaux, les mécanismes du cours : représentations, parcours en largeur et en profondeur, composantes connexes, tri topologique et détection de cycle, plus courts chemins de Dijkstra, arbre couvrant minimal de Kruskal. Chaque réponse se donne sous la forme demandée (tableau, liste, ordre, distance) et se justifie en une ou deux phrases.

Conventions. Les listes d’adjacence sont remplies dans l’ordre des arêtes de l’énoncé, par ajout en queue (une arête non orientée \(v\)–\(w\) entre dans la liste de \(v\) et dans celle de \(w\)) ; les voisins d’un sommet sont examinés dans l’ordre de sa liste. Le parcours en largeur marque un sommet quand il entre dans la file. Le parcours en profondeur est récursif ; quand il doit partir de plusieurs sommets, une boucle essaie \(v=0, 1, 2,\dots\) Le tri topologique est l’ordre postfixe inversé. Dans l’algorithme de Dijkstra, le tas contient des entrées distance:sommet, comparées par distance puis par sommet ; une distance n’est remplacée que si elle diminue strictement, et une entrée qui sort alors que son sommet est déjà définitif est périmée et ignorée. Kruskal examine les arêtes par poids croissant, à poids égal par plus petite première extrémité, puis plus petite seconde (dans l’ordre où l’énoncé écrit l’arête), et s’arrête à \(V-1\) arêtes.

Exercice 1 : le réseau du Nord

Sept villes, numérotées de 0 à 6 : Saint-Louis, Richard-Toll, Dagana, Podor, Louga, Linguère, Matam. Arêtes, dans cet ordre : 0–1, 1–2, 2–3, 3–6, 0–4, 4–5, 5–6, 1–4.

0 1 2 3 4 5 6
0
1
2
3
4
5
6
  1. Remplir la matrice d’adjacence. Combien de cases valent 1 ?
  2. Écrire les listes d’adjacence.
  3. Donner le degré de chaque ville et vérifier \(\sum\deg(v)=2|E|\).
  4. Donner un cycle de 3 arêtes et un cycle de 6 arêtes. Le graphe est-il connexe ? Combien d’arêtes faut-il au moins retirer pour obtenir un arbre ?
  5. Pour un graphe de \(V=14\,000\) sommets et \(E=40\,000\) arêtes, donner le nombre de cases de la matrice et le nombre d’entrées des listes. Quelle représentation choisir, et pourquoi ?

Exercice 2 : un parcours en largeur depuis Saint-Louis

On parcourt en largeur le graphe de l’exercice 1 depuis Saint-Louis (sommet 0).

  1. Compléter le tableau des tours.
  2. Donner distTo et dessiner l’arbre de parcours.
  3. Donner le chemin rendu par chemin(6) et sa longueur en arêtes. Quelles villes sont exactement à 2 tronçons de Saint-Louis ?
  4. Combien d’entrées des listes le parcours lit-il ? Le relier à \(E\).
tour sort marqués (distance) file après le tour
1
2
3
4
5
6
7

Exercice 3 : profondeur et composantes connexes

Un graphe non orienté a 9 sommets. Arêtes, dans cet ordre : 0–1, 0–2, 1–3, 2–3, 3–4, 5–6, 6–7, 5–7, 7–8.

  1. Écrire les listes d’adjacence.
  2. Une boucle sur \(v=0..8\) lance dfs(v) sur chaque sommet non marqué. Donner les appels lancés par la boucle, puis les ordres préfixe et postfixe.
  3. Combien le graphe a-t-il de composantes connexes ? Quels sommets contient chacune ?
  4. Dessiner la forêt de parcours (l’arête père–fils de chaque appel).
  5. Expliquer comment le parcours en profondeur révèle un cycle dans un graphe non orienté, puis donner un cycle de chaque composante.
rang 1 2 3 4 5 6 7 8 9
préfixe
postfixe

Exercice 4 : les tâches d’un projet logiciel

Huit tâches, numérotées de 0 à 7 : Analyse, Maquette, Base, API, Interface, Tests, Déploiement, Documentation. Un arc \(u\to v\) signifie que \(v\) ne peut commencer qu’après \(u\). Arcs, dans cet ordre : 0\(\to\) 1, 0\(\to\) 2, 2\(\to\) 3, 1\(\to\) 4, 3\(\to\) 4, 3\(\to\) 5, 4\(\to\) 5, 5\(\to\) 6, 0\(\to\) 7, 7\(\to\) 6.

  1. Dérouler le tri topologique du cours (boucle sur \(v=0..7\)) : les entrées et sorties d’appels, puis l’ordre postfixe.
  2. En déduire l’ordre topologique, et vérifier les dix arcs.
  3. On ajoute par erreur l’arc Déploiement\(\to\)API (6\(\to\) 3). Dérouler CycleOriente : quel arc mène à un sommet dont l’appel est en cours ? Quel cycle est rendu ?
rang 1 2 3 4 5 6 7 8
postfixe
ordre topologique

Exercice 5 : l’algorithme de Dijkstra

Un graphe non orienté pondéré a sept sommets, A à G (0 à 6). Arêtes, dans cet ordre : A–B 5, A–C 2, B–C 1, B–D 6, C–D 9, C–E 11, D–E 3, D–F 7, E–F 2, E–G 8, F–G 3.

  1. Dérouler l’algorithme de Dijkstra depuis A : à chaque extraction, l’entrée extraite, distTo après le tour et le contenu du tas. Marquer les entrées périmées.
  2. Combien y a-t-il d’extractions, d’entrées périmées et d’insertions ? Vérifier que les insertions ne dépassent pas \(E+1\).
  3. Donner le chemin le plus court de A à G et l’arbre des plus courts chemins.
extrait A B C D E F G tas après le tour

Exercice 6 : l’algorithme de Kruskal

On reprend le graphe pondéré de l’exercice 5.

  1. Compléter le tableau : les arêtes examinées, par poids croissant, la décision et sa raison (les morceaux de la forêt).
  2. Donner l’arbre couvrant minimal et son poids ; quelles arêtes ne sont jamais examinées ?
  3. Comparer cet arbre à l’arbre des plus courts chemins de l’exercice 5. Ce résultat est-il général ?
arête poids décision raison : morceaux de la forêt

Exercice 7 : poids négatif et pièges

  1. Un graphe orienté a cinq sommets et les arcs 0\(\to\) 1 (1), 0\(\to\) 2 (5), 1\(\to\) 3 (3), 2\(\to\) 1 (\(-5\)), 3\(\to\) 4 (4).

    Dérouler le code de Dijkstra du cours depuis 0 et donner distTo. Calculer les vraies distances en examinant les chemins. Quels sommets sont faux, et à quel moment l’erreur se produit-elle ?

  2. Vrai ou faux ? Justifier chaque réponse en une ou deux lignes, par un argument ou un contre-exemple.

    1. Un graphe orienté sans cycle a toujours au moins un sommet sans arc entrant.
    2. Si toutes les arêtes ont le même poids, le parcours en largeur donne les plus courts chemins pondérés.
    3. Dans un graphe connexe non orienté à poids positifs, un plus court chemin de \(s\) à \(t\) commence toujours par l’arête la plus légère issue de \(s\).
    4. Ajouter la même constante à tous les poids ne change pas l’arbre couvrant minimal.
    5. Si tous les poids sont distincts, l’arbre couvrant minimal est unique.
    6. Le parcours en profondeur depuis \(s\) et le parcours en largeur depuis \(s\) atteignent les mêmes sommets.

Pour cette séance

Le cours

Les slides

À lire en ligne

À télécharger

Retour au sommet