Cómo ejecutar una consulta de flujo o emparejamiento 01 Construye la red. El preajuste Flow network S→T es una red dirigida de 6 nodos; las pruebas de bipartición también aceptan el preajuste Bipartite K₃,₃ y cualquier rejilla. 02 Elige Dinic max-flow o Edmonds–Karp , fija Source S y Sink T y lee el flujo máximo, la capacidad del corte mínimo, la fila de contraste y la tabla de flujo/capacidad por arista. 03 Para Bipartite check lee el veredicto, los conjuntos izquierdo y derecho y — cuando la respuesta es No — el testigo del ciclo impar. 04 Para Hungarian matching carga un grafo bipartito y lee el tamaño del emparejamiento, los pares, la cobertura de vértices mínima y los vértices sin emparejar. 05 Avanza la ejecución paso a paso en los algoritmos de flujo para ver cómo los caminos aumentantes elevan el valor del flujo.
Lecturas resueltas
Configuración
Lectura
Preajuste de flujo, Dinic S → T
flujo máximo 19 ; capacidad del corte mínimo 19 ; contraste (Edmonds–Karp) 19 ; aristas de corte S→A, B→D ; lado de la fuente S, B
Preajuste de flujo, flujos por arista
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
emparejamiento máximo 3 ; pares L1–R3, L2–R2, L3–R1 ; cobertura de vértices mínima L1, L2, L3 ; sin emparejar —
Ciclo C₅, Bipartite check
bipartito No ; testigo del ciclo impar C → B → A → E → D → C
Rejilla 4 × 5, Bipartite check
bipartito Sí ; izquierda 10 nodos empezando 1-1, 1-3, 1-5, 2-2; derecha 10 empezando 1-2, 1-4, 2-1
Los dos algoritmos de flujo coinciden en 19 , y las aristas de corte confirman la cota: S→A lleva 10 y B→D lleva 9 , que suman el flujo máximo. El sumidero recibe 9 por C→T y 10 por D→T, de nuevo 19 .
Por qué el corte demuestra el flujo El teorema max-flow min-cut dice que el mejor flujo es igual al cuello de botella más barato. Dinic se detiene cuando no queda ningún camino aumentante; el panel muestra entonces los nodos aún alcanzables desde S — el lado de la fuente S, B — y las aristas que lo abandonan, S→A y B→D , cuyas capacidades 10 y 9 suman el flujo. Cada unidad debe cruzar ese corte, así que no existe un flujo mayor. En el lado del emparejamiento, el teorema de Kőnig da el mismo estilo de prueba: un emparejamiento de tamaño 3 y una cobertura de vértices de tamaño 3 se fijan mutuamente.
Límites
El emparejamiento necesita un grafo bipartito. Ejecuta Hungarian matching en el preajuste Petersen y el panel se niega con "Graph is not bipartite (odd cycle O3 → O2 → O1 → O5 → O4 → O3) — the Hungarian/Kuhn algorithm does not apply" en lugar de devolver una respuesta parcial. No se ofrece emparejamiento para grafos generales.
Un par fuente-sumidero a la vez, sin costes. No hay flujo de coste mínimo, ni flujo multicommodity, ni cotas inferiores en las aristas; ejecuta los pares por turnos y compara los lados de la fuente. Lo que no hace. No enumera cortes más allá del mínimo reportado y no importa archivos de red. Construye la red en el lienzo y lleva la matriz de adyacencia a math tools para más álgebra, o lista la alcanzabilidad con Components .
La trampa de la dirección Las aristas de corte se imprimen como pares dirigidos. En el preajuste Flow dirigido son S→A y B→D ; en el grafo predeterminado no dirigido, Dinic A→F imprime A→B, A→C con lado de la fuente A . El lado de la fuente es la lectura estable entre ejecuciones — todo lo aún alcanzable desde S cuando el algoritmo se detiene —, así que compara esa fila, no la dirección de las flechas, cuando revises un corte a mano.
Dónde resulta útil Planificación de capacidad El preajuste de flujo muestra cuánto de una demanda de 19 unidades puede pasar y dónde se sienta el cuello de botella: S→B conserva 1 unidad de margen mientras que A→D deja 2 , pero el corte S→A / B→D está saturado. Sube la capacidad de una arista de corte y el valor del flujo se mueve; sube una arista dentro de la red y normalmente no lo hace.
Problemas de asignación En Bipartite K₃,₃ el panel Hungarian empareja los tres nodos izquierdos y imprime una cobertura del mismo tamaño, así que la asignación es demostrablemente máxima. Las rejillas responden Sí a la comprobación bipartita con un reparto igual 10/10, mientras que C₅ responde No y devuelve el ciclo impar — el certificado de que no existe 2-coloración. El panel Traversal puede entonces mostrar los grupos de color nodo por nodo.
Privacidad Todos los cálculos de flujo, coloreado y emparejamiento se ejecutan en tu navegador; no se sube nada.
Referencias
Wikipedia, Maximum flow problem , en.wikipedia.org (访问日期:2026-10-07)— caminos aumentantes y valor del flujo.
Wikipedia, Max-flow min-cut theorem , en.wikipedia.org (访问日期:2026-10-07)— el flujo iguala la capacidad del corte.
Wikipedia, Bipartite graph , en.wikipedia.org (访问日期:2026-10-07)— 2-coloración y ciclos impares.
Wikipedia, Maximum cardinality matching , en.wikipedia.org (访问日期:2026-10-07)— emparejamiento por caminos aumentantes.
Wikipedia, Kőnig's theorem (graph theory) , en.wikipedia.org (访问日期:2026-10-07)— emparejamiento igual a cobertura de vértices en grafos bipartitos.
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