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

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

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

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

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

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

On considère le graphe non orienté suivant :

    A --- B
    |   / |
    |  /  |
    C --- D --- E

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).

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

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

graphe = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"]
}

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é). À chaque étape, on visite le sommet au sommet de la pile, on le marque comme visité, et on empile ses voisins non visités.

1. Compléter le tableau en choisissant les voisins dans l’ordre alphabétique :

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

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

def dfs(graphe, sommet, visites=None):
    if visites is None:
        visites = set()
    visites.add(sommet)
    print(sommet, end=" ")
    for voisin in sorted(graphe[sommet]):
        if voisin not in visites:
            dfs(graphe, voisin, visites)
    return visites

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.

1. Compléter le tableau (voisins dans l’ordre alphabétique) :

2. Donner l’ordre complet de visite.

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

def bfs(graphe, depart):
    visites = {depart}
    file = [depart]
    ordre = []
    while file:
        sommet = file.pop(0)
        ordre.append(sommet)
        for voisin in sorted(graphe[sommet]):
            if voisin not in visites:
                visites.add(voisin)
                file.append(voisin)
    return ordre

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.

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.

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"].

def chemin_existe(graphe, depart, arrivee):
    visites = set()
    pile = [depart]
    while pile:
        sommet = pile.pop()
        if sommet == arrivee:
            return True
        if sommet not in visites:
            visites.add(sommet)
            for voisin in graphe[sommet]:
                pile.append(voisin)
    return False

def chemin_bfs(graphe, depart, arrivee):
    if depart == arrivee:
        return [depart]
    visites = {depart}
    file = [depart]
    predecesseur = {depart: None}
    while file:
        sommet = file.pop(0)
        for voisin in sorted(graphe[sommet]):
            if voisin not in visites:
                visites.add(voisin)
                predecesseur[voisin] = sommet
                if voisin == arrivee:
                    # Reconstituer le chemin
                    chemin = []
                    courant = arrivee
                    while courant is not None:
                        chemin.append(courant)
                        courant = predecesseur[courant]
                    return chemin[::-1]
                file.append(voisin)
    return None  # pas de chemin

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

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

    A --5-- B --2-- C
    |       |       |
    3       7       4
    |       |       |
    D --1-- E --6-- F

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.

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

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

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.

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)

def contient_cycle(graphe):
    visites = set()

    def dfs(sommet, parent):
        visites.add(sommet)
        for voisin in graphe[sommet]:
            if voisin not in visites:
                if dfs(voisin, sommet):
                    return True
            elif voisin != parent:
                return True  # voisin déjà visité et ce n'est pas le parent → cycle
        return False

    for sommet in graphe:
        if sommet not in visites:
            if dfs(sommet, None):
                return True
    return False

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

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

  Gare --4-- Marché --3-- Hôpital
    |          |              |
    6          2              5
    |          |              |
  Mairie --7-- Stade ---------+

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}, ...}
   

2. Écrire une fonction dijkstra(graphe, depart) qui implémente l’algorithme de Dijkstra et renvoie un dictionnaire {sommet: distance_minimale}.

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

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é ?

graphe = {
    "Gare":     {"Marché": 4, "Mairie": 6},
    "Marché":   {"Gare": 4, "Hôpital": 3, "Stade": 2},
    "Hôpital":  {"Marché": 3, "Stade": 5},
    "Mairie":   {"Gare": 6, "Stade": 7},
    "Stade":    {"Marché": 2, "Hôpital": 5, "Mairie": 7}
}

def dijkstra(graphe, depart):
    distances = {s: float("inf") for s in graphe}
    distances[depart] = 0
    predecesseurs = {s: None for s in graphe}
    non_traites = set(graphe.keys())

    while non_traites:
        # Sélectionner le sommet non traité de distance minimale
        sommet = min(non_traites, key=lambda s: distances[s])
        non_traites.remove(sommet)

        for voisin, poids in graphe[sommet].items():
            nouvelle_dist = distances[sommet] + poids
            if nouvelle_dist < distances[voisin]:
                distances[voisin] = nouvelle_dist
                predecesseurs[voisin] = sommet

    return distances, predecesseurs