Exercices : graphes

Exercice 1 — QCM : vocabulaire des graphes

Pour chaque question, une seule réponse est correcte.

1. Dans un graphe non orienté simple à 5 sommets, le degré maximal d’un sommet est :

  • A. 4
  • B. 5
  • C. 8
  • D. 10

Correction publiée après la séance.

2. Un graphe non orienté a 6 sommets et 9 arêtes. La somme des degrés de tous les sommets est :

  • A. 9
  • B. 12
  • C. 15
  • D. 18

Correction publiée après la séance.

3. Quelle structure de données utilise-t-on pour implémenter un parcours en largeur (BFS) ?

  • A. une pile
  • B. une file
  • C. un arbre binaire
  • D. un dictionnaire

Correction publiée après la séance.

4. On représente un graphe à 4 sommets par la matrice suivante :

$$\begin{pmatrix} 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \end{pmatrix}$$

Ce graphe est :

  • A. non orienté et connexe
  • B. orienté car la matrice n’est pas symétrique
  • C. non orienté car la diagonale est nulle
  • D. orienté et complet

Correction publiée après la séance.

5. L’algorithme de Dijkstra ne fonctionne pas correctement si :

  • A. le graphe est non orienté
  • B. le graphe contient des arêtes de poids négatif
  • C. le graphe est connexe
  • D. le graphe a plus de 100 sommets

Correction publiée après la séance.

Exercice 2 — Exercice guidé : passer d’un graphe à ses représentations

On considère le graphe non orienté suivant :

Arêtes : A–B, A–C, B–C, B–D, C–D, D–E.

  1. Écrire la matrice d’adjacence de ce graphe (sommets dans l’ordre A, B, C, D, E).

    Indice

    La matrice a une ligne et une colonne par sommet ; la case de la ligne X et de la colonne Y vaut 1 si X et Y sont reliés par une arête, 0 sinon. Le graphe n’est pas orienté : la matrice est symétrique.

  2. Écrire le dictionnaire d’adjacence Python correspondant.

    Indice

    Chaque clé est un sommet et sa valeur la liste de ses voisins, par exemple "A": ["B", "C"]. Nommer ce dictionnaire graphe : les exercices suivants s’en servent.

  3. Vérifier que la somme des degrés est bien le double du nombre d’arêtes.

    Indice

    Le degré d’un sommet est son nombre de voisins. Chaque arête relie deux sommets : elle compte dans le degré de chacun des deux.

Correction publiée après la séance.

Exercice 3 — Exercice guidé : parcours en profondeur (DFS) pas à pas

On reprend le graphe de l’exercice 2 et on effectue un parcours en profondeur à partir du sommet A.

Rappel : le parcours en profondeur utilise une pile ou la récursivité. On utilise ici la version récursive : on visite le sommet, on le marque comme visité, puis on explore récursivement chacun de ses voisins non encore visités, dans l’ordre de la liste.

  1. Compléter le tableau en choisissant les voisins dans l’ordre alphabétique :
ÉtapeSommet visitéAppels récursifs en attenteSommets visités
1A{A}
2
3
4
5
Indice

Depuis un sommet, appeler la visite sur son premier voisin non visité, dans l’ordre alphabétique ; quand un sommet n’a plus de voisin non visité, revenir au sommet qui l’a appelé et continuer avec ses voisins suivants.

  1. Donner l’ordre complet de visite des sommets.

  2. Écrire l’algorithme DFS récursif en Python utilisant le dictionnaire d’adjacence.

    Indice

    Une fonction dfs(graphe, sommet, visites) ajoute sommet à la liste visites, puis s’appelle sur chaque voisin, pris dans l’ordre alphabétique, qui n’est pas encore dans visites.

    Code à copier puis compléter
    def dfs(graphe, sommet, visites):
    visites.append(sommet)
    for voisin in sorted(graphe[sommet]):
        if voisin not in ...:
            dfs(graphe, ..., visites)
    return visites

print(dfs(graphe, "A", []))

Correction publiée après la séance.

Exercice 4 — Exercice guidé : parcours en largeur (BFS) pas à pas

On reprend le même graphe et on effectue un parcours en largeur à partir du sommet A.

Rappel : le parcours en largeur utilise une file. On enfile le sommet de départ, puis à chaque étape on défile un sommet, on le traite et on enfile ses voisins non visités. On marque un sommet comme visité dès qu’on l’enfile.

  1. Compléter le tableau (voisins dans l’ordre alphabétique) :
ÉtapeFile (avant)Sommet défiléVoisins enfilésSommets visités
1[A]A
2
3
4
5
Indice

Défiler le premier sommet de la file, puis enfiler, dans l’ordre alphabétique, ceux de ses voisins qui ne sont pas encore marqués, en les marquant aussitôt.

  1. Donner l’ordre complet de visite.

  2. Écrire l’algorithme BFS en Python utilisant une liste comme file.

    Indice

    La liste file démarre avec le sommet de départ : file.pop(0) défile et file.append(v) enfile. Un sommet est marqué dès qu’il est enfilé, pour ne pas l’enfiler deux fois.

    Code à copier puis compléter
    def bfs(graphe, depart):
    visites = [depart]
    file = [depart]
    ordre = []
    while len(file) > 0:
        sommet = file.pop(0)
        ordre.append(sommet)
        for voisin in sorted(graphe[sommet]):
            if voisin not in visites:
                visites.append(...)
                file.append(...)
    return ordre

print(bfs(graphe, "A"))

Correction publiée après la séance.

Exercice 5 — Implémenter DFS et BFS

  1. Écrire une fonction chemin_existe(graphe, depart, arrivee) qui utilise un parcours (au choix DFS ou BFS) pour déterminer s’il existe un chemin entre depart et arrivee.

    Indice

    Lancer un parcours depuis depart : il existe un chemin si et seulement si arrivee fait partie des sommets visités. La fonction bfs de l’exercice 4 donne justement la liste des sommets atteints.

  2. Écrire une fonction chemin_bfs(graphe, depart, arrivee) qui renvoie un plus court chemin (en nombre d’arêtes) entre depart et arrivee, sous forme de liste de sommets.

    Indication : utiliser un dictionnaire predecesseur qui associe à chaque sommet visité le sommet depuis lequel on l’a découvert. Une fois arrivee atteint, remonter les prédécesseurs.

    Indice

    Faire un parcours en largeur depuis depart en notant, pour chaque sommet découvert, le sommet qui l’a découvert : predecesseur[voisin] = sommet. Partir ensuite de arrivee, remonter les prédécesseurs jusqu’à depart, puis retourner la liste obtenue.

    Code à copier puis compléter
    def chemin_bfs(graphe, depart, arrivee):
    predecesseur = {depart: None}
    file = [depart]
    while len(file) > 0:
        sommet = file.pop(0)
        for voisin in sorted(graphe[sommet]):
            if voisin not in predecesseur:
                predecesseur[voisin] = ...
                file.append(voisin)
    if arrivee not in predecesseur:
        return None
    chemin = []
    courant = arrivee
    while courant != None:
        chemin.append(courant)
        courant = ...
    return chemin[::-1]

  3. Tester avec le graphe de l’exercice 2 : chemin_bfs(graphe, "A", "E") doit renvoyer ["A", "B", "D", "E"] ou ["A", "C", "D", "E"].

Correction publiée après la séance.

Exercice 6 — Exercice guidé : algorithme de Dijkstra pas à pas

On considère le graphe pondéré suivant :

On cherche le plus court chemin de A à F avec l’algorithme de Dijkstra.

  1. Compléter le tableau de Dijkstra. À chaque étape, on sélectionne le sommet non traité de distance minimale.
ÉtapeSommet sélectionnédist(A)dist(B)dist(C)dist(D)dist(E)dist(F)
Init—0\(\infty\)\(\infty\)\(\infty\)\(\infty\)\(\infty\)
1A
2
3
4
5
6
Indice

Après avoir sélectionné un sommet, examiner chacun de ses voisins : si passer par le sommet sélectionné donne une distance plus petite que celle notée, la remplacer. À l’étape suivante, on sélectionne, parmi les sommets non traités, celui dont la distance est la plus petite.

  1. Quel est le plus court chemin de A à F ? Quel est son poids ?

    Indice

    Le poids se lit dans la colonne dist(F) à la fin. Pour le chemin, repartir de F et chercher chaque fois le sommet par lequel sa distance a été obtenue.

  2. Le plus court chemin passe-t-il par le moins d’arêtes possible ? Justifier.

    Indice

    Compter les arêtes du chemin trouvé, puis chercher un chemin de A à F qui en utilise moins : quel est son poids ?

Correction publiée après la séance.

Exercice 7 — Détecter un cycle dans un graphe

  1. Rappeler la définition d’un cycle dans un graphe.

  2. Écrire une fonction contient_cycle(graphe) qui renvoie True si le graphe (non orienté, donné par un dictionnaire d’adjacence) contient un cycle, False sinon.

    Indication : adapter le DFS. Un cycle est détecté si, en explorant les voisins d’un sommet, on tombe sur un sommet déjà visité qui n’est pas le prédécesseur direct.

    Indice

    Écrire un parcours en profondeur récursif qui reçoit aussi le sommet d’où l’on vient, parent. Pour chaque voisin : s’il n’est pas visité, l’explorer et transmettre un cycle éventuellement trouvé ; s’il est déjà visité et différent de parent, il y a un cycle. Lancer ce parcours depuis chaque sommet non encore visité.

    Code à copier puis compléter
    def dfs_cycle(graphe, sommet, parent, visites):
    visites.append(sommet)
    for voisin in graphe[sommet]:
        if voisin not in visites:
            if dfs_cycle(graphe, voisin, sommet, visites):
                return True
        elif voisin != ...:
            return True
    return False

def contient_cycle(graphe):
    visites = []
    for sommet in graphe:
        if sommet not in visites:
            if dfs_cycle(graphe, sommet, None, visites):
                return ...
    return ...

  3. Tester sur les graphes suivants :

    • {"A": ["B"], "B": ["A", "C"], "C": ["B"]} (pas de cycle)
    • {"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B"]} (cycle A–B–C)

Correction publiée après la séance.

Exercice 8 — Synthèse : réseau de transport

La ville de Graphville possède cinq stations de métro reliées comme suit :

Les poids représentent les temps de trajet en minutes.

  1. Modéliser ce réseau par un dictionnaire d’adjacence pondéré en Python.

    Indication : pour un graphe pondéré, on utilise un dictionnaire de dictionnaires :

    graphe = {"Gare": {"Marché": 4, "Mairie": 6}, ...}
    Indice

    Chaque station est une clé, et sa valeur un dictionnaire qui associe à chaque station voisine le temps de trajet. Chaque liaison s’écrit dans les deux sens, par exemple "Gare": {"Marché": 4, ...} et "Marché": {"Gare": 4, ...}.

  2. Écrire une fonction dijkstra(graphe, depart) qui implémente l’algorithme de Dijkstra et renvoie le couple (distances, predecesseurs) : le dictionnaire distances associe à chaque sommet sa distance minimale depuis depart, le dictionnaire predecesseurs associe à chaque sommet le sommet qui le précède sur un plus court chemin.

    Indice

    Toutes les distances valent d’abord float("inf"), sauf celle de depart, qui vaut 0. Tant qu’il reste des sommets non traités : choisir celui de plus petite distance, le retirer des sommets à traiter, puis, pour chaque voisin, mettre à jour sa distance et son prédécesseur si passer par ce sommet raccourcit le trajet.

    Code à copier puis compléter
    def dijkstra(graphe, depart):
    distances = {}
    predecesseurs = {}
    for s in graphe:
        distances[s] = float("inf")
        predecesseurs[s] = None
    distances[depart] = 0
    non_traites = list(graphe)
    while len(non_traites) > 0:
        sommet = non_traites[0]
        for s in non_traites:
            if distances[s] < ...:
                sommet = s
        non_traites.remove(sommet)
        for voisin, poids in graphe[sommet].items():
            if distances[sommet] + poids < distances[voisin]:
                distances[voisin] = ...
                predecesseurs[voisin] = ...
    return distances, predecesseurs

  3. Trouver le plus court chemin et le temps minimal pour aller de Gare à Hôpital.

    Indice

    Appeler dijkstra(graphe, "Gare") : la distance de Hôpital donne le temps minimal. Pour le chemin, remonter les prédécesseurs depuis Hôpital jusqu’à Gare.

  4. Un incident bloque la ligne Marché–Stade. Quel est maintenant le plus court chemin de Gare à Hôpital ? Le temps a-t-il augmenté ?

    Indice

    Retirer la liaison des deux dictionnaires concernés, dans les deux sens, puis relancer dijkstra depuis Gare.

Correction publiée après la séance.

Chapitres liés