Tool guide

Flot maximal, coupe minimale et couplage biparti

Le panneau Flow & matching couvre trois tâches liées sur le canevas partagé de l'atelier de théorie des graphes : un flot maximal d'une source à un puits avec Dinic ou Edmonds–Karp, un test de bipartition qui colore le graphe ou produit un cycle impair comme contre-exemple, et un couplage maximal hongrois avec la couverture de sommets minimale de Kőnig. Les résultats de flot viennent avec la capacité de coupe minimale, les arêtes de coupe et le côté source de la coupe, donc la réponse porte sa propre preuve.

Updated 5 sources5 min read