update: Monday 1 May, 17:40:58 from IUseArchBTW

1 files changed, 68 insertions, 0 deletions

diff --git a/ERO1/Problèmes de flots dans un réseau.md b/ERO1/Problèmes de flots dans un réseau.md
new file mode 100644
index 0000000..6b455f8
--- /dev/null
+++ b/ERO1/Problèmes de flots dans un réseau.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