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 :
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 :
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) ?
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 :
Correction publiée après la séance.
5. L’algorithme de Dijkstra ne fonctionne pas correctement si :
Correction publiée après la séance.
On considère le graphe non orienté suivant :
Arêtes : A–B, A–C, B–C, B–D, C–D, D–E.
Écrire la matrice d’adjacence de ce graphe (sommets dans l’ordre A, B, C, D, E).
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.
Écrire le dictionnaire d’adjacence Python correspondant.
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.
Vérifier que la somme des degrés est bien le double du nombre d’arêtes.
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.
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.
| Étape | Sommet visité | Appels récursifs en attente | Sommets visités |
|---|---|---|---|
| 1 | A | {A} | |
| 2 | |||
| 3 | |||
| 4 | |||
| 5 |
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.
Donner l’ordre complet de visite des sommets.
Écrire l’algorithme DFS récursif en Python utilisant le dictionnaire d’adjacence.
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.
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.
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.
| Étape | File (avant) | Sommet défilé | Voisins enfilés | Sommets visités |
|---|---|---|---|---|
| 1 | [A] | A | ||
| 2 | ||||
| 3 | ||||
| 4 | ||||
| 5 |
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.
Donner l’ordre complet de visite.
Écrire l’algorithme BFS en Python utilisant une liste comme file.
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.
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.
É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.
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.
É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.
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.
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]
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.
On considère le graphe pondéré suivant :
On cherche le plus court chemin de A à F avec l’algorithme de Dijkstra.
| Étape | Sommet sélectionné | dist(A) | dist(B) | dist(C) | dist(D) | dist(E) | dist(F) |
|---|---|---|---|---|---|---|---|
| Init | — | 0 | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) |
| 1 | A | ||||||
| 2 | |||||||
| 3 | |||||||
| 4 | |||||||
| 5 | |||||||
| 6 |
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.
Quel est le plus court chemin de A à F ? Quel est son poids ?
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.
Le plus court chemin passe-t-il par le moins d’arêtes possible ? Justifier.
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.
Rappeler la définition d’un cycle dans un graphe.
É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.
É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é.
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 ...
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.
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.
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}, ...}
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, ...}.
É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.
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.
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
Trouver le plus court chemin et le temps minimal pour aller de Gare à Hôpital.
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.
Un incident bloque la ligne Marché–Stade. Quel est maintenant le plus court chemin de Gare à Hôpital ? Le temps a-t-il augmenté ?
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.