Comment lancer une requête de flot ou de couplage 01 Construisez le réseau. Le préréglage Flow network S→T est un réseau orienté à 6 nœuds ; les tests de bipartition acceptent aussi le préréglage Bipartite K₃,₃ et toute grille. 02 Choisissez Dinic max-flow ou Edmonds–Karp , réglez Source S et Sink T, puis lisez le flot maximal, la capacité de coupe minimale, la ligne de recoupement et le tableau flot/capacité par arête. 03 Pour Bipartite check , lisez le verdict, les ensembles gauche et droit et — quand la réponse est Non — le témoin de cycle impair. 04 Pour Hungarian matching , chargez un graphe biparti et lisez la taille du couplage, les paires, la couverture de sommets minimale et les sommets non couplés. 05 Avancez l'exécution pas à pas sur les algorithmes de flot pour voir les chemins augmentants augmenter la valeur du flot.
Relevés calculés
Configuration
Relevé
Préréglage de flot, Dinic S → T
flot maximal 19 ; capacité de coupe minimale 19 ; recoupement (Edmonds–Karp) 19 ; arêtes de coupe S→A, B→D ; côté source S, B
Préréglage de flot, flots par arête
S→A 10/10 , S→B 9/10 , A→C 4/4 , A→D 6/8 , B→D 9/9 , C→T 9/10 , D→C 5/6 , D→T 10/10
Bipartite K₃,₃, Hungarian matching
couplage maximal 3 ; paires L1–R3, L2–R2, L3–R1 ; couverture de sommets minimale L1, L2, L3 ; non couplés —
Cycle C₅, Bipartite check
biparti Non ; témoin de cycle impair C → B → A → E → D → C
Grille 4 × 5, Bipartite check
biparti Oui ; gauche 10 nœuds à partir de 1-1, 1-3, 1-5, 2-2 ; droite 10 à partir de 1-2, 1-4, 2-1
Les deux algorithmes de flot concordent à 19 , et les arêtes de coupe confirment la borne : S→A porte 10 et B→D porte 9 , soit la somme du flot maximal. Le puits reçoit 9 par C→T et 10 par D→T, encore 19 .
Pourquoi la coupe démontre le flot Max-flow min-cut dit que le meilleur flot égale le goulot d'étranglement le moins cher. Dinic s'arrête quand il ne reste aucun chemin augmentant ; le panneau montre alors les nœuds encore atteignables depuis S — le côté source S, B — et les arêtes qui le quittent, S→A et B→D , dont les capacités 10 et 9 s'additionnent pour donner le flot. Chaque unité doit franchir cette coupe, donc aucun flot plus grand n'existe. Du côté du couplage, le théorème de Kőnig donne le même style de preuve : un couplage de taille 3 et une couverture de sommets de taille 3 se verrouillent mutuellement.
Limites
Le couplage exige un graphe biparti. Lancez Hungarian matching sur le préréglage Petersen et le panneau refuse avec "Graph is not bipartite (odd cycle O3 → O2 → O1 → O5 → O4 → O3) — the Hungarian/Kuhn algorithm does not apply" au lieu de renvoyer une réponse partielle. Le couplage pour graphes généraux n'est pas proposé.
Une paire source-puits à la fois, sans coûts. Pas de flot à coût minimal, pas de flot multicommodité, pas de bornes inférieures sur les arêtes ; lancez les paires à tour de rôle et comparez les côtés source. Ce qu'il ne fait pas. Il n'énumère pas les coupes au-delà du minimum affiché et n'importe pas de fichiers de réseau. Construisez le réseau sur le canevas, puis emportez la matrice d'adjacence vers math tools pour l'algèbre, ou listez l'atteignabilité avec Components .
Le piège de la direction Les arêtes de coupe sont imprimées comme des paires orientées. Sur le préréglage Flow orienté, ce sont S→A et B→D ; sur le graphe par défaut non orienté, Dinic A→F imprime A→B, A→C avec côté source A . Le côté source est le relevé stable d'une exécution à l'autre — tout ce qui reste atteignable depuis S quand l'algorithme s'arrête —, donc comparez cette ligne, pas le sens des flèches, lorsque vous revérifiez une coupe à la main.
Où cela sert Planification de capacité Le préréglage de flot montre quelle part d'une demande de 19 unités peut passer et où se situe le goulot : S→B garde 1 unité de marge tandis que A→D en laisse 2 , mais la coupe S→A / B→D est saturée. Augmentez la capacité d'une arête de coupe et la valeur du flot bouge ; augmentez une arête à l'intérieur du réseau et elle ne bouge généralement pas.
Problèmes d'affectation Sur Bipartite K₃,₃, le panneau Hungarian apparie les trois nœuds gauches et imprime une couverture de même taille, donc l'affectation est démontrablement maximale. Les grilles répondent Oui au test de bipartition avec un partage égal 10/10, tandis que C₅ répond Non et renvoie le cycle impair — le certificat qu'aucune 2-coloration n'existe. Le panneau Traversal peut alors montrer les groupes de couleur nœud par nœud.
Confidentialité Tous les calculs de flot, de coloration et de couplage se font dans votre navigateur ; rien n'est téléversé.
Références
Wikipedia, Maximum flow problem , en.wikipedia.org (访问日期:2026-10-07)— chemins augmentants et valeur du flot.
Wikipedia, Max-flow min-cut theorem , en.wikipedia.org (访问日期:2026-10-07)— le flot égale la capacité de coupe.
Wikipedia, Bipartite graph , en.wikipedia.org (访问日期:2026-10-07)— 2-coloration et cycles impairs.
Wikipedia, Maximum cardinality matching , en.wikipedia.org (访问日期:2026-10-07)— couplage par chemins augmentants.
Wikipedia, Kőnig's theorem (graph theory) , en.wikipedia.org (访问日期:2026-10-07)— couplage égal à la couverture de sommets dans les graphes bipartis.
Calculators in this hub
Hand-picked tools, one click away. The mini versions compute live and carry your values into the full calculator.
Sources & review
Updated 2026-10-07