Réseau de distribution d'eau - Analyse de graphes orientés pondérés
Une ville souhaite modéliser son réseau de distribution d'eau. Le réseau est représenté par un graphe orienté pondéré où :
- les sommets représentent des nœuds du réseau (châteaux d'eau, jonctions, quartiers),
- les arêtes orientées représentent des canalisations avec une capacité maximale (en litres/seconde).
Représentation : On utilise un dictionnaire de listes d'adjacence :
# reseau[u] = liste de couples (v, cap) signifiant :
# canalisation de u vers v, capacité cap
reseau1 = {
0: [(1, 10), (2, 8)],
1: [(3, 5), (4, 7)],
2: [(1, 3), (4, 6)],
3: [(5, 4)],
4: [(5, 9)],
5: []
}
# Sommet 0 = château d'eau (source), sommet 5 = quartier (puits)
Écrire une fonction voisins(reseau, u) qui retourne la liste des sommets directement accessibles depuis u.
Exemple
voisins(reseau1, 2)
[1, 4]
def voisins(reseau, u):
if u not in reseau:
return []
return [v for v, cap in reseau[u]]
Écrire une fonction nb_sommets(reseau) et une fonction nb_aretes(reseau) qui retournent respectivement le nombre de sommets et le nombre d'arêtes du graphe.
Exemple
nb_sommets(reseau1)
nb_aretes(reseau1)
6
7
def nb_sommets(reseau):
return len(reseau)
def nb_aretes(reseau):
total = 0
for voisins in reseau.values():
total += len(voisins)
return total
Écrire une fonction parcours_largeur(reseau, s) qui retourne la liste des sommets visités en BFS depuis le sommet source s, dans l'ordre de découverte.
Exemple
parcours_largeur(reseau1, 0)
[0, 1, 2, 3, 4, 5]
def parcours_largeur(reseau, s):
visites = []
file = [s]
vu = {s}
while file:
u = file.pop(0)
visites.append(u)
for v in voisins(reseau, u):
if v not in vu:
vu.add(v)
file.append(v)
return visites
Écrire une fonction est_accessible(reseau, s, t) qui retourne True si le sommet t est accessible depuis s en suivant les arêtes orientées, False sinon. On utilisera un parcours en largeur ou en profondeur.
Exemple
est_accessible(reseau1, 0, 5)
est_accessible(reseau1, 3, 2)
True
False
def est_accessible(reseau, s, t):
if s == t:
return True
visites = set()
file = [s]
visites.add(s)
while file:
u = file.pop(0)
for v in voisins(reseau, u):
if v == t:
return True
if v not in visites:
visites.add(v)
file.append(v)
return False
Écrire une fonction distance(reseau, s, t) qui retourne la longueur minimale (en nombre d'arêtes) d'un chemin de s à t, ou -1 si t n'est pas accessible depuis s. On utilisera un BFS.
Exemple
distance(reseau1, 0, 5)
distance(reseau1, 0, 3)
distance(reseau1, 3, 0)
2
2
-1
def distance(reseau, s, t):
if s == t:
return 0
dist = {s: 0}
file = [s]
while file:
u = file.pop(0)
for v in voisins(reseau, u):
if v not in dist:
dist[v] = dist[u] + 1
if v == t:
return dist[v]
file.append(v)
return -1
Écrire une fonction chemin_court(reseau, s, t) qui retourne un chemin de longueur minimale de s à t sous forme de liste de sommets, ou [] si aucun chemin n'existe. On stockera pour chaque sommet son prédécesseur dans le BFS.
Exemple
chemin_court(reseau1, 0, 5)
[0, 2, 4, 5] # ou [0, 1, 4, 5]
def chemin_court(reseau, s, t):
if s == t:
return [s]
precedent = {s: None}
file = [s]
while file:
u = file.pop(0)
for v in voisins(reseau, u):
if v not in precedent:
precedent[v] = u
if v == t:
# Reconstruire le chemin
chemin = []
courant = t
while courant is not None:
chemin.append(courant)
courant = precedent[courant]
return chemin[::-1]
file.append(v)
return []
Écrire une fonction tous_chemins(reseau, s, t) qui retourne la liste de tous les chemins simples (sans sommet répété) de s à t, en utilisant un parcours en profondeur avec backtracking.
Exemple
tous_chemins(reseau1, 0, 5)
[[0,1,3,5], [0,1,4,5], [0,2,1,3,5], [0,2,1,4,5], [0,2,4,5]]
def tous_chemins(reseau, s, t):
resultats = []
def dfs(u, chemin):
if u == t:
resultats.append(chemin[:])
return
for v in voisins(reseau, u):
if v not in chemin:
chemin.append(v)
dfs(v, chemin)
chemin.pop()
dfs(s, [s])
return resultats
La capacité d'un chemin est le minimum des capacités de ses arêtes (c'est le débit maximal qu'on peut y faire passer).
Écrire une fonction capacite_chemin(reseau, chemin) qui retourne la capacité du chemin donné (liste de sommets). On supposera le chemin valide et non vide.
Exemple
capacite_chemin(reseau1, [0, 1, 4, 5])
capacite_chemin(reseau1, [0, 2, 4, 5])
7
6
def capacite_chemin(reseau, chemin):
min_cap = float('inf')
for i in range(len(chemin) - 1):
u, v = chemin[i], chemin[i+1]
for w, cap in reseau[u]:
if w == v:
min_cap = min(min_cap, cap)
break
return min_cap
Écrire une fonction meilleur_chemin(reseau, s, t) qui retourne, parmi tous les chemins simples de s à t, celui qui a la capacité maximale. En cas d'égalité, on retourne le premier trouvé.
Exemple
meilleur_chemin(reseau1, 0, 5)
[0, 1, 4, 5]
def meilleur_chemin(reseau, s, t):
tous = tous_chemins(reseau, s, t)
if not tous:
return None
meilleur = tous[0]
meilleur_cap = capacite_chemin(reseau, meilleur)
for chemin in tous[1:]:
cap = capacite_chemin(reseau, chemin)
if cap > meilleur_cap:
meilleur_cap = cap
meilleur = chemin
return meilleur
On appelle goulot d'étranglement d'un chemin l'arête de capacité minimale. Écrire une fonction goulot(reseau, chemin) qui retourne le couple $(u, v)$ correspondant à cette arête (le premier rencontré en cas d'égalité).
Exemple
goulot(reseau1, [0, 1, 4, 5])
(1, 4)
def goulot(reseau, chemin):
min_cap = float('inf')
goulot_arete = None
for i in range(len(chemin) - 1):
u, v = chemin[i], chemin[i+1]
for w, cap in reseau[u]:
if w == v:
if cap < min_cap:
min_cap = cap
goulot_arete = (u, v)
break
return goulot_arete
Écrire une fonction contient_cycle(reseau) qui retourne True si le graphe orienté contient au moins un cycle, False sinon. On utilisera un DFS avec trois états pour chaque sommet : non visité, en cours de visite, complètement visité.
Exemple
reseau2 = {0: [(1,1)], 1: [(2,1)], 2: [(0,1)], 3: [(2,1)]}
contient_cycle(reseau1)
contient_cycle(reseau2)
False
True
def contient_cycle(reseau):
# 0 = non visité, 1 = en cours, 2 = terminé
etat = {sommet: 0 for sommet in reseau}
def dfs(u):
etat[u] = 1 # en cours de visite
for v in voisins(reseau, u):
if etat[v] == 1: # cycle détecté
return True
if etat[v] == 0 and dfs(v):
return True
etat[u] = 2 # terminé
return False
for sommet in reseau:
if etat[sommet] == 0:
if dfs(sommet):
return True
return False
Lorsque le graphe est un DAG (graphe orienté acyclique), il est possible de le trier topologiquement : trouver un ordre linéaire des sommets tel que pour toute arête $(u,v)$, $u$ apparaît avant $v$.
Écrire une fonction tri_topologique(reseau) qui retourne une liste des sommets dans un ordre topologique valide, ou None si le graphe contient un cycle. On utilisera un DFS post-ordre.
Exemple
tri_topologique(reseau1)
[0, 2, 1, 4, 3, 5] # (un ordre valide parmi plusieurs)
def tri_topologique(reseau):
# 0 = non visité, 1 = en cours, 2 = terminé
etat = {sommet: 0 for sommet in reseau}
resultat = []
def dfs(u):
etat[u] = 1
for v in voisins(reseau, u):
if etat[v] == 1: # cycle détecté
return False
if etat[v] == 0 and not dfs(v):
return False
etat[u] = 2
resultat.append(u)
return True
for sommet in reseau:
if etat[sommet] == 0:
if not dfs(sommet):
return None
return resultat[::-1] # inversion pour l'ordre topologique
On souhaite maintenant minimiser non plus le nombre d'arêtes, mais le coût total d'un chemin. On définit le coût d'une arête $(u,v,c)$ comme $100 - c$ (plus la capacité est grande, moins le chemin est « coûteux » à entretenir).
Écrire une fonction cout_arete(cap) qui retourne le coût d'une arête de capacité cap.
Exemple
cout_arete(7)
93
def cout_arete(cap):
return 100 - cap
Écrire une fonction dijkstra(reseau, s) qui implémente l'algorithme de Dijkstra et retourne un dictionnaire dist tel que dist[v] est le coût minimal d'un chemin de s à v (ou float('inf') si v n'est pas accessible). On utilisera une file de priorité (module heapq).
Exemple
dijkstra(reseau1, 0)
{0: 0, 1: 90, 2: 92, 3: 181, 4: 183, 5: 187}
import heapq
def dijkstra(reseau, s):
dist = {sommet: float('inf') for sommet in reseau}
dist[s] = 0
file = [(0, s)]
while file:
d, u = heapq.heappop(file)
if d > dist[u]:
continue
for v, cap in reseau[u]:
cout = cout_arete(cap)
if dist[u] + cout < dist[v]:
dist[v] = dist[u] + cout
heapq.heappush(file, (dist[v], v))
return dist
En modifiant dijkstra, écrire une fonction chemin_optimal(reseau, s, t) qui retourne le chemin de coût minimal de s à t sous forme de liste de sommets.
Exemple
chemin_optimal(reseau1, 0, 5)
[0, 1, 4, 5]
def chemin_optimal(reseau, s, t):
dist = {sommet: float('inf') for sommet in reseau}
dist[s] = 0
precedent = {sommet: None for sommet in reseau}
file = [(0, s)]
while file:
d, u = heapq.heappop(file)
if d > dist[u]:
continue
if u == t:
break
for v, cap in reseau[u]:
cout = cout_arete(cap)
if dist[u] + cout < dist[v]:
dist[v] = dist[u] + cout
precedent[v] = u
heapq.heappush(file, (dist[v], v))
if precedent[t] is None and s != t:
return []
chemin = []
courant = t
while courant is not None:
chemin.append(courant)
courant = precedent[courant]
return chemin[::-1]
On dit qu'un sommet v (différent de la source s et du puits t) est un point de vulnérabilité si sa suppression rend t inaccessible depuis s.
Écrire une fonction points_vulnerabilite(reseau, s, t) qui retourne la liste de tous les points de vulnérabilité du réseau pour la paire $(s, t)$. On pourra s'appuyer sur est_accessible.
Exemple
points_vulnerabilite(reseau1, 0, 5)
[4]
def points_vulnerabilite(reseau, s, t):
if s == t:
return []
vulnérables = []
for sommet in reseau:
if sommet == s or sommet == t:
continue
# Créer une copie du réseau sans le sommet
copie = {u: [(v, cap) for v, cap in voisinage if v != sommet]
for u, voisinage in reseau.items() if u != sommet}
if not est_accessible(copie, s, t):
vulnérables.append(sommet)
return vulnérables
On appelle réseau robuste un réseau dans lequel il n'existe aucun point de vulnérabilité entre la source et le puits. Écrire une fonction est_robuste(reseau, s, t) qui retourne True si le réseau est robuste.
Exemple
est_robuste(reseau1, 0, 5)
False
def est_robuste(reseau, s, t):
return len(points_vulnerabilite(reseau, s, t)) == 0
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.