GRO

Question 1

Définition d’un graphe

Answer 1

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)

Question 2

Définition d’un graphe valué

Answer 2

C’est un graphe auquel on associe une fonction positive c : Γ → R+ appelée capacité.

Question 3

Coefficient de la matrice d’incidence

Answer 3

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))

Question 4

Définition d’un puits

Answer 4

Sommet sans successeur

Question 5

Définition d’une source

Answer 5

Sommet sans prédécesseur

Question 6

Définition d’un flot

Answer 6

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).

Question 7

Flot réalisable

Answer 7

Le flot est dit réalisable si pour toute arête (i, j) ∈ Γ, on a : 0 ≤ fij ≤ cij

Question 8

Valeur de flot

Answer 8

C’est la quantité ∑f(i,t) avec i∈P(t)

Question 9

Coupe d’un graphe

Answer 9

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̅

Question 10

Théorème de Ford-Fulkerson

Answer 10

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

Question 11

Arête saturée et insaturée

Answer 11

On dit qu’une arête (i, j) ∈ Γ est saturée si fij = cij et qu’elle est insaturée si fij = 0

Question 12

Coupe minimale

Answer 12

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.

Question 13

Corollaire du théorème de Ford-Fulkerson qui donne une condition suffisante pour avoir un flot maximal.

Answer 13

S’il existe une coupe minimale pour un flot f , alors ce flot est maximal.

Question 14

Chaîne

Answer 14

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

Question 15

Théorème reliant flot maximal et chaîne améliorante

Answer 15

Un flot réalisable est maximal si et seulement s’il n’existe pas de chaîne améliorante.

Question 16

Chaîne améliorante

Answer 16

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)

Question 17

Algorithme de Ford-Fulkerson

Answer 17

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

Question 18

Amélioration du flot

Answer 18

• 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ᵣ₊₁) − ε

Question 19

Parcours en profondeur (DFS)

Answer 19

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

Question 20

Parcours en largeur (BFS)

Answer 20

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

Question 21

Complexité de l’algorithme de Ford-Fulkerson

Answer 21

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*).