|
Définissons à la fois les réseaux résiduels et les chemins augmentants, en particulier dans le contexte d'algorithmes de flux de réseau comme la méthode Ford-Fulkerson.
1. Réseau résiduel :
Imaginez que vous disposez d'un réseau avec une ou plusieurs sources, un puits (t) et des bords avec des capacités représentant le flux maximum autorisé à travers chaque bord. Un *réseau résiduel* est une représentation de la capacité restante dans le réseau *après* qu'une certaine quantité de flux l'ait déjà traversé.
Voici comment cela fonctionne :
* Bords avant : Pour chaque bord (u, v) du réseau d'origine avec une capacité c(u, v) et un flux de courant f(u, v), le réseau résiduel comprend un *bord avant* correspondant (u, v) avec une capacité cf (u, v) =c(u, v) - f(u, v). Cela représente la capacité restante disponible sur la périphérie.
* Bords arrière : La partie cruciale est que le réseau résiduel comprend *également* des *bords arrière*. Pour chaque bord (u, v) du réseau d'origine avec le flux de courant f(u, v), le réseau résiduel contient un bord arrière (v, u) de capacité cf (v, vous) =f(u, v). Cela représente la possibilité de *repousser le flux* le long du bord, annulant ainsi une partie du flux déjà envoyé. La capacité du bord arrière est égale au flux actuellement sur le bord avant, car vous ne pouvez repousser que la quantité de flux déjà présente.
Essentiellement, le réseau résiduel montre la capacité disponible pour modifier le flux. Il s'adapte dynamiquement à mesure que le flux circule à travers le réseau. Trouver un chemin d'augmentation (expliqué ci-dessous) dans le réseau résiduel signifie qu'il est toujours possible d'augmenter le flux total de la source au puits.
2. Chemin d'augmentation :
Un *chemin d'augmentation* est un chemin simple (sans sommets répétés) dans le réseau résiduel qui mène de la ou des sources au puits (t). Surtout, cela représente un moyen d’augmenter le flux total à travers le réseau.
La quantité par laquelle le débit peut être augmenté le long du chemin d'augmentation est déterminée par la *capacité du goulot d'étranglement*. Il s'agit de la capacité résiduelle minimale parmi tous les bords du chemin d'augmentation.
Par exemple:
Si un chemin augmentant a des arêtes avec des capacités résiduelles de 5, 3 et 7, la capacité du goulot d'étranglement est de 3. On peut alors augmenter le flux le long de ce chemin de 3 unités. Ce processus met à jour le flux dans le réseau d'origine et modifie ensuite le réseau résiduel.
Relation entre les réseaux résiduels et les chemins d'augmentation :
Le cœur de nombreux algorithmes de flux maximum (comme Ford-Fulkerson) est itératif :
1. Trouver un chemin d'augmentation dans le réseau résiduel actuel.
2. Augmentez le flux le long de cette voie par la capacité de goulot d'étranglement.
3. Mettre à jour le réseau résiduel pour refléter le changement de débit.
Ce processus se poursuit jusqu'à ce qu'il n'y ait plus de chemins d'augmentation dans le réseau résiduel, moment auquel le débit maximum a été atteint. Le théorème de coupe minimale du débit maximum le garantit.
|
