GRO Flashcards
Définition d’un graphe
C’est un couple G = (E, Γ)
où E est un ensemble de sommets et Γ ensemble fini d’ arêtes (ie : couples ordonnés (i, j) avec i, j ∈ E)
Définition d’un graphe valué
C’est un graphe auquel on associe une fonction positive c : Γ → R+ appelée capacité.
Coefficient de la matrice d’incidence
aᵢᵣ =
−1 si le sommet i est l’extrémité initiale de l’arête r
+1 si le sommet i est l’extrémité terminale de l’arête r
0 sinon
Remarque : le graphe doit être sans boucle (pas d’arête (i,i))
Définition d’un puits
Sommet sans successeur
Définition d’une source
Sommet sans prédécesseur
Définition d’un flot
Soit un graphe valué comportant un seul sommet source s et un seul sommet puits t.
Un flot de s à t est une fonction f : Γ → R tq
∑f(i,j) = ∑f(j,k) où i∈P(j) et k∈S(j)
pour tout sommet j ≠ s,t. On dit qu’il y a conservation du flux au sommet j (“ce qui rentre égale ce qui sort”).
f (i, j) est le flot dans l’arête (i, j).
Flot réalisable
Le flot est dit réalisable si pour toute arête (i, j) ∈ Γ, on a : 0 ≤ fij ≤ cij
Valeur de flot
C’est la quantité ∑f(i,t) avec i∈P(t)
Coupe d’un graphe
Une coupe d’un graphe valué G = (E, Γ, c) possédant un seul sommet source s et un seul sommet puits t, est une partition des sommets notée (X, X̅) telle que :
s∈X et t∈X̅
La capacité de la coupe est définie par c(X, X̅) = ∑cᵢᵣ
avec i∈X et r∈X̅
Théorème de Ford-Fulkerson
Soit G = (E, Γ, c) un graphe valué. Pour tout flot réalisable f et toute coupe (X, X̅), on a :
v(f) ≤ c(X, X̅)
où v(f) est la valeur du flot f
Arête saturée et insaturée
On dit qu’une arête (i, j) ∈ Γ est saturée si fij = cij et qu’elle est insaturée si fij = 0
Coupe minimale
Une coupe (X, X̅) est dite minimale pour f si toute arête de X vers X̅ est saturée et toute arête de X̅ vers X est insaturée.
Corollaire du théorème de Ford-Fulkerson qui donne une condition suffisante pour avoir un flot maximal.
S’il existe une coupe minimale pour un flot f , alors ce flot est maximal.
Chaîne
Une chaîne d’un graphe est une suite de sommets reliés entre eux par des arêtes
Ces arêtes sont des arêtes directes ou inverses, car une chaîne (contrairement à un chemin) ne tient pas compte de l’orientation des arêtes reliant les sommets
Théorème reliant flot maximal et chaîne améliorante
Un flot réalisable est maximal si et seulement s’il n’existe pas de chaîne améliorante.
Chaîne améliorante
Soit G = (E, Γ, c) un graphe valué possédant une seule source s et un seul puits t. Une chaîne C = (s, i₁, · · · , iᵣ, iᵣ₊₁, · · · , t) est dite améliorante pour un flot réalisable f donné si :
f(iᵣ, iᵣ₊₁) < c(iᵣ, iᵣ₊₁) si (iᵣ, iᵣ₊₁) ∈ Γ (arête directe)
f(iᵣ₊₁, iᵣ) > 0 si (iᵣ₊₁, iᵣ) ∈ Γ (arête inverse)
Algorithme de Ford-Fulkerson
1) Initialisation par un flot initial réalisable (f = 0)
2) Tant que le flot n’est pas maximal
- Marquage de la source s
- Tant qu’on marque des sommets
Pour tout sommet marqué i
Marquer les sommets j non marqués tq
f (i, j) < c(i, j) ou f (j, i) > 0
Fin pour
Fin Tant que
- Si le puits t n’est pas marqué alors le flot est maximal
- Sinon amélioration du flot
Fin Tant que
Amélioration du flot
- Trouver une chaîne qui a permis de marquer t et calculer ε = min(ε₁, ε₂) > 0 avec
ε₁ = min {c(iᵣ , iᵣ₊₁) − f (iᵣ , iᵣ₊₁) avec (iᵣ , iᵣ₊₁) ∈ Γ (arête directe)}
ε₂ = min {f(iᵣ , iᵣ₊₁) avec (iᵣ , iᵣ₊₁) ∈ Γ (arête inverse)} - Trouver le nouveau flot f’ :
Si (iᵣ , iᵣ₊₁) ∈ Γ (arête directe) alors f’(iᵣ , iᵣ₊₁) = f(iᵣ , iᵣ₊₁) + ε
Si (iᵣ , iᵣ₊₁) ∈ Γ (arête inverse) alors f’(iᵣ , iᵣ₊₁) = f(iᵣ , iᵣ₊₁) − ε
Parcours en profondeur (DFS)
Pour chaque sommet, on prend et on marque le premier sommet successeur jusqu’à ce qu’un sommet n’ait plus de successeur ou bien que tous ses successeurs soient déjà marqués.
=> utilisation d’une pile
Parcours en largeur (BFS)
A partir d’un sommet, on liste et on marque tous les sommets successeurs non encore marqués, jusqu’à ce qu’un sommet n’ait plus de successeur ou bien que tous ses successeurs soient déjà marqués.
=> utilisation d’une file
Complexité de l’algorithme de Ford-Fulkerson
Pour un graphe avec n sommets et m arêtes : O(nmCmax) opérations
où Cmax est le maximum des capacités des arêtes.
Parfois la complexité est donnée en utilisant le flot maximum F* (qu’on ne connait pas a priori) qui est * nécessairement entier, ce qui nous donne une complexité en O(mF*).
