Tool guide

Flujo máximo, corte mínimo y emparejamiento bipartito

El panel Flow & matching cubre tres tareas relacionadas sobre el lienzo compartido del banco de teoría de grafos: un flujo máximo de una fuente a un sumidero con Dinic o Edmonds–Karp, una comprobación bipartita que colorea el grafo o produce un ciclo impar como contraejemplo, y un emparejamiento máximo húngaro con la cobertura de vértices mínima de Kőnig. Los resultados de flujo vienen con la capacidad del corte mínimo, las aristas de corte y el lado de la fuente, así que la respuesta lleva su propia prueba.

Updated 5 sources5 min read