Tool guide

Fluxo máximo, corte mínimo e emparelhamento bipartido

O painel Flow & matching cobre três tarefas relacionadas na tela compartilhada da bancada de teoria dos grafos: um fluxo máximo de uma fonte a um sumidouro com Dinic ou Edmonds–Karp, uma verificação bipartida que colore o grafo ou produz um ciclo ímpar como contraexemplo, e um emparelhamento máximo húngaro com a cobertura mínima de vértices de Kőnig. Os resultados de fluxo vêm com a capacidade do corte mínimo, as arestas de corte e o lado da fonte, então a resposta carrega sua própria prova.

Updated 5 sources4 min read