From 9cdb6fbadb258a4a04bbe836b0ab3bd39f3f02e7 Mon Sep 17 00:00:00 2001 From: marcellus Date: Mon, 19 May 2025 17:40:58 +0200 Subject: update: Monday 1 May, 17:40:58 from IUseArchBTW --- ...l\303\250mes de flots dans un r\303\251seau.md" | 68 ++++++++++++++++++++++ 1 file changed, 68 insertions(+) create mode 100644 "ERO1/Probl\303\250mes de flots dans un r\303\251seau.md" (limited to 'ERO1/Problèmes de flots dans un réseau.md') diff --git "a/ERO1/Probl\303\250mes de flots dans un r\303\251seau.md" "b/ERO1/Probl\303\250mes de flots dans un r\303\251seau.md" new file mode 100644 index 0000000..6b455f8 --- /dev/null +++ "b/ERO1/Probl\303\250mes de flots dans un r\303\251seau.md" @@ -0,0 +1,68 @@ +# Réseaux et flots +## Définitions +### Réseau +Graphe orienté, défini par ses noeuds et arcs +### Flot +- Quantité quelconque circulant sur les arcs d'un réseau +- Analogie avec un débit d'eau circulant dans des tuyaux + +## Caractérisation des noeuds +### Noeud source + +### Noeud puits +### Noeud de transbordement +- Noeud intermédiaire +- Tout le flot entrant doit être égal au flot sortant + +## Capacité sur les arcs +- Quantité max de flots pouvant circuler sur l'arc +- Si le flot est le débit d'eau, la capacité est proportionnelle au diamètre du tuyau + +## Flot maximum +-> réseau saturé + +# Coupe de capacité maximale +## Définitions +### Coupe +Partition en 2 sous-ensembles $S$ et $\overline{S}$ des noeuds du réseau +### Coupe s-t +-> Soit $s$ un noeud source et $t$ un noeud puits +-> C'est une coupe telle que $s \in S$ et $t \in \overline{S}$ +### Capacité d'une coupe s-t +Somme des capacités $(i,j)$ tels que $i \in S$ et $j \in \overline{S}$ +Attention au sens de l'arc + +## Invariance du flot le long d'une coupe +- La valeur nette du flot le long de toute coupe est indépendant de la coupe +- Ceci signifie que la valeur du flot peut être récupérée le long d'une coupe quelconque, en comptant positivement les flots de $S$ vers $\overline{S}$ et négativement les autres + +La valeur du flot dans un réseau est inférieure à la capacité de n'importe quelle coupe + +## Théorème Max Flow Min Cut +- La valeur du flot maximum dans un réseau est égale à la valeur de la coupe de capacité minimale dans ce même réseau +- Ceci signifie que le flot maximum correspond à la capacité du "goulot d'étranglement" du réseau +# Algorithme de Ford-Fulkerson +## Graphe résiduel +La **capacité résiduelle** d'un arc $(i,j)$ de capacité $u_{i,j}$ sur lequel circule $x_{i,j}$ unités de flot se définit comme suit : +$$ +\begin{align} +r_{i,j} = u_{i,j} - x_{i,j} \\ +r_{j,i} = x_{i,j} +\end{align} +$$ +Elle est égale à la capacité résiduelle minimale le long du chemin. +Un chemin **augmentant** dans un graphe résiduel est un chemin entre un noeud source et noeud puits ayant une capacité résiduelle strictement positive. + +## L'algorithme +1. Trouver un chemin augmentant. S'il n'y en a pas le flot est déjà maximal +2. Sinon on calcule la capacité résiduelle $R$ du chemin et mettre ) jour les capacité résiduelles des arcs du chemin : + 1. augmenter la capacité résiduelle des arcs $(i,j)$ de $R$ unités + 2. diminuer la capacité résiduelle des arcs $(i,j)$ de $R$ unités +3. Recommencer +## Retour sur la coupe minimale +Pour trouver la coupe de capacité minimale associée, on définit $S$ en prenant les sommets atteignables depuis la source dans le graphe résiduel (+ la source) + +## Validité de l'algorithme +1. Le flot est maximum entre $s$ et $t$ +2. Le réseau résiduel ne contient aucun chemin augmentant +3. Il existe une coupe dont la capacité est égale à la valeur du flot \ No newline at end of file -- cgit v1.2.3