^{PDFprof.com Search Engine}

TIPE : Optimisation de flot sur un réseau de transport

Comment calculer un flot ?
Un flot dans un réseau de flot G = (V, A,c) est une fonction f :V ×V → R satisfaisant les deux propriétés suivantes : 1. contrainte de capacité : ∀ u,v ∈V : 0 ≤ f (u,v) ≤ c(u,v); 2. conservation des flots : ∀ u ∈V \\{s,t} : ∑v∈V f (v,u) = ∑v∈V f (u,v).
Comment déterminer le flot maximal ?
La valeur d'un flot maximal est égal à la valeur d'une coupe minimale.
De plus, si (A,B) est une coupe minimale, et que a est un arc ayant son départ dans A et son extrémité dans B, est saturé par tout flot maximal.
Quelle est la valeur du flot total en sortie de réseau ?
La valeur du flot sur un réseau est égale à la valeur du flux φ0 sur l'arc de retour uo.
La valeur du flot est égale à ce qui "part" de la source et à ce qui "arrive" au puits.
L'arc de retour sert de compteur, il permet de mesurer ce qui circule sur le réseau.
Un flot ϕ est dit complet si et seulement si tout chemin de s à t comporte au moins un arc saturé.

Comment calculer un flot ?