Chapitre 6 - Entraînement : Les graphes

Représentations d'un graphe

Exercice 1 - Modélisation

Modéliser les situations suivantes sous forme de graphes (orienté ou non, sommets, arêtes/arcs, liste d'adjacence Python).

a. Un groupe de 5 amis : Alice, Bob, Clara, David, Emma. Alice est amie avec Bob et Clara. Bob est ami avec David. Clara est amie avec Emma et David.

b. Un réseau de pages web : la page A contient un lien vers B et C. La page B contient un lien vers A. La page C contient un lien vers B.

Solution

a. Graphe non orienté :

amis = {
    "Alice": ["Bob", "Clara"],
    "Bob": ["Alice", "David"],
    "Clara": ["Alice", "Emma", "David"],
    "David": ["Bob", "Clara"],
    "Emma": ["Clara"]
}

b. Graphe orienté :

web = {
    "A": ["B", "C"],
    "B": ["A"],
    "C": ["B"]
}

Exercice 2 - Matrice d'adjacence

On considère le graphe : A-B, A-C, B-C, B-D, C-D.

a. Écrire la matrice d'adjacence.

b. Écrire une fonction nb_aretes(matrice) qui calcule le nombre d'arêtes.

c. Écrire une fonction degre(matrice, sommet) qui renvoie le degré d'un sommet.

Solution

    A  B  C  D
A [ 0, 1, 1, 0 ]
B [ 1, 0, 1, 1 ]
C [ 1, 1, 0, 1 ]
D [ 0, 1, 1, 0 ]

b. et c.

matrice = [[0,1,1,0],[1,0,1,1],[1,1,0,1],[0,1,1,0]]

def nb_aretes(matrice):
    total = 0
    for i in range(len(matrice)):
        for j in range(len(matrice)):
            total += matrice[i][j]
    return total // 2

def degre(matrice, sommet):
    return sum(matrice[sommet])

print(nb_aretes(matrice))  # 5
print(degre(matrice, 1))   # 3 (B)

Exercice 3 - Choix de structure

Pour chaque situation, indiquer la structure la plus adaptée et justifier.

a. Historique des pages visitées (bouton « retour »).

b. File d'impression.

c. Arbre généalogique.

d. Plan de métro.

e. Annuaire téléphonique.

Solution

a. Pile (LIFO) : le retour va à la dernière page, au sommet de la pile.

b. File (FIFO) : les documents sont traités dans l'ordre d'envoi.

c. Arbre : structure hiérarchique (parents → enfants).

d. Graphe non orienté : les stations sont les sommets, les liaisons les arêtes. Il y a des cycles.

e. Dictionnaire : clé = nom, valeur = numéro. Accès rapide.

Parcours et chemins

Exercice 4 - Parcours DFS et BFS

Soit le graphe suivant :

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

a. Donner l'ordre de visite des sommets par un parcours en profondeur à partir de A.

b. Donner l'ordre de visite par un parcours en largeur à partir de A.

c. Donner un plus court chemin de A à F.

Solution

a. DFS depuis A : A, B, C, F, E, D (on explore B d'abord, puis C, puis F, puis E via F, puis D via E ou retour).

b. BFS depuis A : A, B, D, C, E, F (niveau 0 : A, niveau 1 : B et D, niveau 2 : C et E, niveau 3 : F).

c. Plus court chemin de A à F (en nombre d'arêtes) : A → B → C → F (3 arêtes). Ou A → D → E → F (3 arêtes également).

Exercice 5 - Détection de cycle

a. Le graphe de l'exercice 4 contient-il un cycle ? Lequel ?

b. Supprimer des arêtes pour obtenir un graphe sans cycle mais restant connexe. Combien d'arêtes reste-t-il ?

Solution

a. Oui, plusieurs cycles. Par exemple : A → B → E → D → A.

b. Un graphe connexe sans cycle (arbre couvrant) sur 6 sommets a exactement 5 arêtes. Par exemple : A-B, B-C, C-F, A-D, D-E.

Activités

Activité 1 - Convertir un graphe

Écrire un programme qui :

Construit un graphe non orienté (au choix : réseau d'amis, plan simplifié) en liste d'adjacence ;
Le convertit en matrice d'adjacence ;
Affiche la matrice formatée ;
Reconvertit la matrice en liste d'adjacence ;
Vérifie que le résultat est identique au graphe original.

Solution

def liste_vers_matrice(graphe, sommets):
    n = len(sommets)
    index = {s: i for i, s in enumerate(sommets)}
    matrice = [[0] * n for _ in range(n)]
    for s in graphe:
        for v in graphe[s]:
            matrice[index[s]][index[v]] = 1
    return matrice

def matrice_vers_liste(matrice, sommets):
    graphe = {}
    for i in range(len(sommets)):
        graphe[sommets[i]] = [sommets[j]
            for j in range(len(sommets)) if matrice[i][j] == 1]
    return graphe

def afficher_matrice(matrice, sommets):
    print("    " + "  ".join(sommets))
    for i, s in enumerate(sommets):
        print(f"{s}  {matrice[i]}")

graphe = {
    "Paris": ["Lyon", "Lille"],
    "Lyon": ["Paris", "Marseille"],
    "Lille": ["Paris", "Bruxelles"],
    "Marseille": ["Lyon"],
    "Bruxelles": ["Lille"]
}
sommets = list(graphe.keys())

mat = liste_vers_matrice(graphe, sommets)
afficher_matrice(mat, sommets)

graphe2 = matrice_vers_liste(mat, sommets)
print("\nVérification :", graphe == graphe2)

Activité 2 - Résoudre un labyrinthe

Modéliser un labyrinthe sous forme de graphe et écrire un programme Python qui trouve un chemin de l'entrée à la sortie avec un parcours en profondeur, puis le plus court chemin avec un parcours en largeur.

Solution

from collections import deque

labyrinthe = {
    (0,0): [(0,1), (1,0)],
    (0,1): [(0,0), (0,2)],
    (0,2): [(0,1), (1,2)],
    (1,0): [(0,0), (2,0)],
    (1,2): [(0,2), (1,3)],
    (1,3): [(1,2), (2,3)],
    (2,0): [(1,0), (2,1)],
    (2,1): [(2,0), (2,2)],
    (2,2): [(2,1), (2,3)],
    (2,3): [(2,2), (1,3)]
}

entree = (0, 0)
sortie = (2, 3)

def chemin_dfs(graphe, depart, arrivee, visites=None):
    if visites is None:
        visites = set()
    visites.add(depart)
    if depart == arrivee:
        return [depart]
    for voisin in graphe[depart]:
        if voisin not in visites:
            chemin = chemin_dfs(graphe, voisin, arrivee, visites)
            if chemin is not None:
                return [depart] + chemin
    return None

def chemin_bfs(graphe, depart, arrivee):
    visites = {depart}
    file = deque([(depart, [depart])])
    while file:
        sommet, chemin = file.popleft()
        for voisin in graphe[sommet]:
            if voisin not in visites:
                nouveau = chemin + [voisin]
                if voisin == arrivee:
                    return nouveau
                visites.add(voisin)
                file.append((voisin, nouveau))
    return None

print("DFS :", chemin_dfs(labyrinthe, entree, sortie))
print("BFS :", chemin_bfs(labyrinthe, entree, sortie))