Accueil du site > MOCA > Flot maximal sur un réseau de transport
Aller à ...
OMFG
Informations
Dans la rubrique MOCA , cet article a été écrit par b3nj et publié le 6 avril 2006.
6827 personnes ont affiché cette page et sa popularité est de 100.
Pebkac
Mots clefs
I see dead pixels.
Outils
SYN
Flot maximal sur un réseau de transport

Propriétés sur les flots

1. Flot complet

Un flot est dit complet si tous les chemins de S à T comportent au moins un arc saturé (\varphi_u = C_u )

2. Coupe

On appelle coupe séparant S et T un ensemble d’arcs de la forme \omega^{+}(A) où A est un sous-ensemble de sommets [1] tel que S \in A et T \not\in A

Exemple de coupe du graphe Exemple de réseau de transport avec arc retour :
A = \left\lbrace S, B \right\rbrace
\omega^{+}(A) = \left\lbrace u_1 , u_4 , u_6 \right\rbrace

3. Capacité d’une coupe

C(A) = \sum\limits_{u \in \omega^{+}_{A}} C_u
Où C(A) est la capacité de la coupe, et C_u est la capacité de l’arc u

En reprenant l’exemple donné en Flot maximal sur un réseau de transport :
C(A) = C_{u_1} + C_{u_4} + C_{u_6} = 6 + 3 + 3 = 12

4. Flot maximal

La valeur de flot maximal de S à T est égale à la valeur minimale de toutes les coupes séparant S de T.

Faire l’exercice Exercice 17b

pages : << 1 2 3 4 >>

[1] Un sous-ensemble contient au moins un sommet

Poster un message