Support des 4 séances du chapitre « Les graphes ». Il sert à la fois de support de projection en classe et de
support de révision à la maison : cliquez sur « Voir la réponse » sous chaque exercice pour afficher le corrigé.
Graphe de référence utilisé dans les séances 3 et 4 : sommets A à H, arêtes A-B, A-C, B-D, B-E,
C-F, C-G, D-H, E-H, F-G (graphe non orienté, connexe, avec deux cycles : B-D-H-E-B et C-F-G-C).
Séance 1 — Découvrir les graphes
Vocabulaire, représentations, deux implémentations en classes Python
📖 Vocabulaire
Sommet, arête (non orienté) / arc (orienté), graphe pondéré, chaîne, longueur, distance, cycle, degré.
Une matrice d'adjacence d'un graphe non orienté est toujours symétrique.
🔁 Matrice ⇄ liste d'adjacence
Exemple : liste A→[B,C,E], B→[A], C→[A,D], D→[C,E], E→[A,D] (non orienté).
Voir la matrice correspondante
A B C D E
A 0 1 1 0 1
B 1 0 0 0 0
C 1 0 0 1 0
D 0 0 1 0 1
E 1 0 0 1 0🐍 Deux classes Graphe
Voir la réponse (matrice)
class Graphe:
def __init__(self, n):
self.n = n
self.adj = [[False] * n for _ in range(n)]
def ajouter_arc(self, s1, s2):
self.adj[s1][s2] = True
def arc(self, s1, s2):
return self.adj[s1][s2]
def voisins(self, s):
return [i for i in range(self.n) if self.adj[s][i]]Voir la réponse (dictionnaire)
class Graphe:
def __init__(self):
self.adj = {}
def ajouter_sommet(self, s):
if s not in self.adj:
self.adj[s] = set()
def ajouter_arc(self, s1, s2):
self.ajouter_sommet(s1)
self.ajouter_sommet(s2)
self.adj[s1].add(s2)
def arc(self, s1, s2):
return s2 in self.adj[s1]
def sommets(self):
return list(self.adj)
def voisins(self, s):
return self.adj[s]🎯 Défi bonus — Le réseau des développeurs
3 serveurs A, B, C connectés en boucle (A→B→C→A), avec la classe Sommet.
Séance 2 — Manipuler la classe Graphe + coloration
Méthodes de la classe, coloration gloutonne, Welsh-Powell
🔧 degre() / nb_arcs() / supprimer_arc()
Voir la réponse (version matrice)
def degre(self, s):
return sum(1 for i in range(self.n) if self.adj[s][i])
def nb_arcs(self):
return sum(self.degre(s) for s in range(self.n))
def supprimer_arc(self, s1, s2):
self.adj[s1][s2] = FalseVoir la réponse (version dictionnaire)
def degre(self, s):
return len(self.adj[s])
def nb_arcs(self):
return sum(self.degre(s) for s in self.adj)
def supprimer_arc(self, s1, s2):
if self.arc(s1, s2):
self.adj[s1].remove(s2)🎨 welsh_powell(g)
On traite les sommets par degré décroissant, une couleur à la fois.
Voir la réponse
def welsh_powell(g):
sommets_tries = sorted(g.sommets(), key=lambda s: g.degre(s), reverse=True)
couleur = {}
c = 0
for s in sommets_tries:
if s in couleur:
continue
couleur[s] = c
for t in sommets_tries:
if t not in couleur and all(couleur.get(v) != c for v in g.voisins(t)):
couleur[t] = c
c += 1
return couleur, c📅 Application — planification d'examens
6 matières, incompatibilités données. Combien de créneaux minimum ?
Voir la réponse
Degrés : P(4), C(3), M(3), N(3), S(2), Ph(1). Welsh-Powell : {P, Ph} → couleur 1, {C, M} → couleur 2, {N, S} → couleur 3.
Nombre chromatique = 3 : il faut 3 créneaux minimum.
🎯 Défi bonus — Coloration d'une carte
5 pays fictifs, frontières P1-P2, P1-P3, P2-P3, P2-P4, P3-P4, P4-P5. Nombre chromatique ?
Séance 3 — Parcours en largeur et en profondeur
BFS (file) et DFS (pile ou récursivité), à la main puis en code
1 parcours_largeur (BFS)
Voir la réponse
def parcours_largeur(g, depart):
file = File()
visites = {depart}
ordre = []
file.enfiler(depart)
while not file.est_vide():
s = file.defiler()
ordre.append(s)
for v in sorted(g.voisins(s)):
if v not in visites:
visites.add(v)
file.enfiler(v)
return ordreSur le graphe de référence depuis A : A, B, C, D, E, F, G, H. Distances : A(0), B,C(1), D,E,F,G(2), H(3).
2 parcours_profondeur (récursif et itératif)
Voir la réponse (récursif)
def parcours_profondeur_recursif(g, s, visites=None, ordre=None):
if visites is None:
visites = set(); ordre = []
visites.add(s)
ordre.append(s)
for v in sorted(g.voisins(s)):
if v not in visites:
parcours_profondeur_recursif(g, v, visites, ordre)
return ordreVoir la réponse (itératif, avec Pile)
def parcours_profondeur_iteratif(g, depart):
pile = Pile()
visites = set(); ordre = []
pile.empiler(depart)
while not pile.est_vide():
s = pile.depiler()
if s not in visites:
visites.add(s); ordre.append(s)
for v in sorted(g.voisins(s), reverse=True):
if v not in visites:
pile.empiler(v)
return ordreSur le graphe de référence depuis A : A, B, D, H, E, C, F, G (les deux versions donnent le même ordre).
Bilan — BFS (File) : garantit le plus court chemin en nombre d'arêtes. DFS (Pile ou récursivité) : va aussi loin que possible avant de revenir en arrière, ne garantit pas le plus court chemin.
🎯 Défi bonus — Histogramme des distances
Regrouper les sommets par distance depuis un départ (niveaux du BFS).
Séance 4 — Chemin, cycle et connexité
Les deux dernières capacités officielles + ouverture sur les DAG
1 existe_chemin / trouver_chemin
Voir la réponse
def existe_chemin(g, depart, arrivee):
return arrivee in parcours_largeur(g, depart)
def trouver_chemin(g, depart, arrivee):
file = File()
parent = {depart: None}
file.enfiler(depart)
while not file.est_vide():
s = file.defiler()
if s == arrivee:
break
for v in sorted(g.voisins(s)):
if v not in parent:
parent[v] = s
file.enfiler(v)
if arrivee not in parent:
return None
chemin = []
s = arrivee
while s is not None:
chemin.append(s); s = parent[s]
chemin.reverse()
return chemintrouver_chemin(g, "A", "H") == ["A", "B", "D", "H"]
2 est_connexe / composantes_connexes
Voir la réponse
def est_connexe(g):
sommets = g.sommets()
if not sommets: return True
return len(parcours_largeur(g, sommets[0])) == len(sommets)
def composantes_connexes(g):
non_visites = set(g.sommets())
composantes = []
while non_visites:
depart = next(iter(non_visites))
composante = parcours_largeur(g, depart)
composantes.append(composante)
non_visites -= set(composante)
return composantes3 contient_cycle (graphe non orienté)
Voir la réponse
def contient_cycle(g):
visites = set()
def dfs(s, parent):
visites.add(s)
for v in g.voisins(s):
if v not in visites:
if dfs(v, s):
return True
elif v != parent:
return True
return False
for s in g.sommets():
if s not in visites:
if dfs(s, None):
return True
return FalseOn détecte un cycle en retombant sur un sommet déjà visité qui n'est PAS le parent direct.
🔗 Ouverture — DAG et programmation dynamique
Un graphe orienté acyclique (DAG) permet de modéliser des dépendances entre tâches (chemin critique).
Voir la réponse
taches = {"A": 3, "B": 2, "C": 4, "D": 1}
dependances = {"A": [], "B": ["A"], "C": ["A"], "D": ["B", "C"]}
def duree_jusqu_a(t, memo={}):
if t in memo:
return memo[t]
if not dependances[t]:
resultat = taches[t]
else:
resultat = taches[t] + max(duree_jusqu_a(dep, memo) for dep in dependances[t])
memo[t] = resultat
return resultat
duree_totale = max(duree_jusqu_a(t) for t in taches)
# Chemin critique : A(3) -> C(4) -> D(1) = 8 jours
Bilan du chapitre — Graphe : matrice ou liste d'adjacence. BFS (file) / DFS (pile ou récursivité) pour parcourir, trouver un chemin, tester la connexité ou détecter un cycle. Les graphes recyclent toutes les structures de l'année : piles, files, récursivité, programmation dynamique.