Calculateur de Flot Maximal dans un Réseau

Calculateur de Flot Maximal dans un Réseau

Le Calculateur de Flot Maximal dans un Réseau calcule le flot maximal d'une source s vers un puits t choisis dans n'importe quel réseau orienté avec capacités. Sous le capot, il exécute la méthode de Ford-Fulkerson avec des chemins augmentants via recherche en largeur (l'algorithme d'Edmonds-Karp), puis enregistre chaque chemin trouvé pour que vous puissiez revoir tout le processus de décision itération par itération. La page de résultats fait également apparaître la coupe minimale — la partition goulot d'étranglement qui prouve que votre valeur de flot est réellement optimale.

Qu'est-ce que le problème du flot maximal ?

Un réseau de flot est un graphe orienté G = (V, E) accompagné d'une fonction de capacité c: E → ℝ_≥0. Deux sommets sont distingués : la source s (où le flot prend naissance) et le puits t (où il est consommé). Un flot f est toute affectation f(u, v) ≥ 0 sur les arêtes qui respecte :

Le problème du flot maximal cherche le flot f qui maximise |f|. Intuitivement : si les arêtes étaient des tuyaux d'eau avec les capacités données, combien de litres par seconde pouvez-vous envoyer de s vers t ?

Comment l'algorithme fonctionne — Ford-Fulkerson avec BFS

L'algorithme maintient un graphe résiduel parallèlement au flot actuel. Pour chaque arête (u, v) de capacité c et flot actuel f, le graphe résiduel contient :

• une arête résiduelle avant (u, v) avec capacité c − f (combien peut encore être poussé), et
• une arête résiduelle inverse (v, u) avec capacité f (combien du flot engagé peut encore être annulé).

À chaque itération, il effectue une recherche en largeur (BFS) de s vers t sur le graphe résiduel. Si un chemin est trouvé, la plus petite capacité d'arête sur le chemin — le goulot — est ajoutée au flot sur chaque arête avant et soustraite sur chaque arête inverse le long du chemin. C'est ce qu'on appelle un chemin augmentant. Lorsque le BFS ne peut plus atteindre t, le flot actuel est optimal.

L'utilisation du BFS (plutôt qu'une recherche de chemin arbitraire) transforme Ford-Fulkerson en Edmonds-Karp, avec un temps d'exécution garanti de O(V · E²). Cela garantit également la terminaison sur des capacités irrationnelles, ce que Ford-Fulkerson simple ne fait pas.

Le théorème Flot-Max / Coupe-Min

Une coupe est une partition des sommets en deux ensembles (S, T) avec s ∈ S et t ∈ T. Sa capacité est la somme des capacités des arêtes allant de S vers T :

Le théorème flot-max / coupe-min (Ford & Fulkerson, 1956) stipule :

Cet outil trouve la coupe minimale automatiquement. Une fois qu'Edmonds-Karp s'arrête, il exécute un dernier BFS depuis s sur le graphe résiduel ; les sommets atteints forment S, le reste forme T, et chaque arête traversant S → T dans le graphe original est saturée. Leurs capacités s'additionnent exactement à la valeur du flot maximal — visible dans le résultat principal comme "Capacité de coupe min ✓ confirme l'optimalité".

Fonctionnalités conçues pour l'apprentissage

• Animation étape par étape. Revoyez chaque chemin augmentant avec des contrôles de lecture, pause et étape. Voyez quel chemin le BFS a choisi, quelle arête était le goulot et comment le total cumulé a augmenté.
• Trois matrices synchronisées. Basculez entre la matrice de capacité C, la matrice de flot final f et la matrice résiduelle C − f — les trois images qui caractérisent ensemble tout flot.
• Vue de la partition de coupe minimale. Les sommets des côtés S et T sont listés sous forme de badges avec les arêtes saturées traversantes mises en évidence en rouge.
• Tableau arête par arête. Pour chaque arête : capacité, flot, résiduel, barre d'utilisation et badge de saturation.
• Disposition par couches gauche-droite. Le dessin du graphe est calculé à partir des distances BFS depuis la source, de sorte que l'eau "coule" visiblement de gauche à droite — exactement comme dans les manuels.

Formats d'entrée

1. Liste d'arêtes avec capacités

Une arête par ligne. La forme avec flèche est la plus lisible, mais plusieurs alternatives fonctionnent :

Également acceptés : A, B, 10 · A B 10 · A -> B , 10. Les arêtes multiples entre une même paire sont sommées.

2. Matrice de capacité

Une ligne par sommet, valeurs séparées par des espaces ou des virgules. L'entrée C[i][j] est la capacité de l'arête du sommet i vers le sommet j. Utilisez 0 pour "pas d'arête". La matrice doit être carrée et la diagonale doit être 0 (pas de boucles sur soi-même).

Saisissez les étiquettes de sommets correspondantes dans le champ Étiquettes de matrice (séparées par des virgules ou des espaces). Si omis, les étiquettes sont par défaut S, A, B, …, T.

Applications du Flot Maximal

Exemple commenté

L'exemple rapide "Manuel" encode un réseau de 6 nœuds avec une source S et un puits T. L'exécution d'Edmonds-Karp donne quatre chemins augmentants :

1. S → A → B → T avec goulot 4 (l'arête A-B est le limiteur). Total cumulé : 4.
2. S → A → D → T avec goulot 6. Total cumulé : 10.
3. S → C → D → T avec goulot 4 (l'arête D-T est maintenant le limiteur, il ne reste que 4). Total cumulé : 14.
4. S → C → D → B → T avec goulot 5. Total cumulé : 19.

L'algorithme s'arrête — il n'existe plus de chemin augmentant. La coupe minimale est (S = {S, C}, T = {A, B, D, T}) avec les arêtes traversantes S → A (capacité 10) et C → D (capacité 9), totalisant 19 — exactement la valeur du flot maximal.

Comment utiliser ce calculateur

1. Choisissez le format d'entrée via les onglets — liste d'arêtes (recommandé) ou matrice de capacité.
2. Saisissez votre réseau. Vous pouvez partir d'un exemple rapide et le modifier. Pour l'entrée matricielle, fournissez également des étiquettes si vous voulez des noms autres que S, A, B, …, T.
3. Spécifiez la source et le puits (ou laissez vide pour une détection automatique de S et T).
4. Cliquez sur Calculer le Flot Maximal. La page de résultats affiche la valeur du flot maximal, la partition de coupe minimale, une visualisation graphique par couches, chaque chemin augmentant, un tableau d'utilisation des arêtes et trois matrices (capacité, flot, résiduelle).
5. Lancez l'animation sous le graphe pour revoir les décisions de l'algorithme. Cliquez sur n'importe quelle étape de chemin augmentant pour y accéder directement.

Limites

• Sommets : jusqu'à 30 — pour garder la visualisation et les matrices lisibles.
• Arêtes : jusqu'à 200.
• Capacités : non négatives, jusqu'à 10⁹. Les capacités fractionnaires sont autorisées.
• Pas de boucles sur soi-même. Les boucles sur un même sommet ne transportent aucun flot dans une formulation standard et sont rejetées.

Foire Aux Questions

Qu'est-ce que le problème du flot maximal ?

Étant donné un réseau orienté où chaque arête a une capacité non négative, le problème du flot maximal demande : quelle quantité de flot peut être envoyée d'un sommet source désigné s vers un sommet puits désigné t, sachant que le flot sur chaque arête ne peut excéder sa capacité et que le flot entrant dans chaque sommet (autre que la source et le puits) doit être égal au flot en sortant ? La réponse est appelée la valeur du flot maximal.

Qu'est-ce que la méthode de Ford-Fulkerson ?

Ford-Fulkerson est une technique générale pour calculer le flot maximal. Elle trouve de manière répétée un chemin augmentant de la source au puits dans le graphe résiduel et pousse autant de flot que possible le long de ce chemin (la capacité du goulot), puis met à jour le graphe résiduel. La procédure s'arrête lorsqu'il n'existe plus de chemin augmentant. Lorsqu'elle est implémentée avec une recherche en largeur pour la sélection du chemin, elle est appelée Edmonds-Karp et s'exécute en temps O(V · E²).

Qu'est-ce que la coupe minimale d'un réseau de flot ?

Une coupe est une partition des sommets en deux ensembles S et T tels que la source est dans S et le puits est dans T. La capacité de la coupe est la somme des capacités des arêtes allant de S vers T. Une coupe minimale est une coupe de capacité minimale. Le célèbre théorème flot-max / coupe-min prouve que la valeur du flot maximal est toujours égale à la capacité de la coupe minimale.

Qu'est-ce que le graphe résiduel ?

Le graphe résiduel suit la quantité de flot supplémentaire qui peut encore être poussée sur chaque arête. Pour chaque arête originale (u, v) avec capacité c et flot actuel f, le graphe résiduel contient une arête avant (u, v) avec une capacité c moins f (capacité restante) et une arête inverse (v, u) avec une capacité f (flot annulable). Un chemin augmentant utilise les arêtes du graphe résiduel, permettant à l'algorithme d'annuler des décisions antérieures.

Pourquoi l'outil utilise-t-il le BFS pour les chemins augmentants ?

Le choix des chemins augmentants par recherche en largeur (Edmonds-Karp) garantit une fin en temps polynomial quelles que soient les capacités des arêtes. Ford-Fulkerson simple avec une stratégie de recherche de chemin arbitraire peut boucler pendant un nombre exponentiel d'itérations sur des entrées pathologiques, et sur des capacités irrationnelles, il peut ne jamais s'arrêter. Le BFS produit également les chemins augmentants les plus courts, plus faciles à lire.

Que signifie une arête saturée ?

Une arête est saturée lorsque son flot est égal à sa capacité, de sorte qu'aucun flot supplémentaire ne peut y être poussé. Les arêtes saturées sont les goulots d'étranglement du réseau, et chaque coupe minimale est entièrement constituée d'arêtes saturées allant du côté S vers le côté T de la coupe. L'outil met en évidence les arêtes saturées en orange pour que vous puissiez voir la structure du goulot d'un coup d'œil.

Lectures complémentaires

• Problème de flot maximum — Wikipédia
• Algorithme de Ford-Fulkerson — Wikipédia
• Algorithme d'Edmonds-Karp — Wikipédia
• Théorème flot-max/coupe-min — Wikipédia