Como executar uma consulta de fluxo ou emparelhamento 01 Construa a rede. A predefinição Flow network S→T é uma rede direcionada de 6 nós; os testes de biparticidade também aceitam a predefinição Bipartite K₃,₃ e qualquer grade. 02 Escolha Dinic max-flow ou Edmonds–Karp , defina Source S e Sink T e leia o fluxo máximo, a capacidade do corte mínimo, a linha de conferência e a tabela de fluxo/capacidade por aresta. 03 Em Bipartite check leia o veredito, os conjuntos esquerdo e direito e — quando a resposta é Não — a testemunha do ciclo ímpar. 04 Em Hungarian matching carregue um grafo bipartido e leia o tamanho do emparelhamento, os pares, a cobertura mínima de vértices e os vértices sem par. 05 Avance a execução passo a passo nos algoritmos de fluxo para ver os caminhos aumentantes elevarem o valor do fluxo.
Leituras calculadas
Configuração
Leitura
Predefinição de fluxo, Dinic S → T
fluxo máximo 19 ; capacidade do corte mínimo 19 ; conferência (Edmonds–Karp) 19 ; arestas de corte S→A, B→D ; lado da fonte S, B
Predefinição de fluxo, fluxos por aresta
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
emparelhamento máximo 3 ; pares L1–R3, L2–R2, L3–R1 ; cobertura mínima de vértices L1, L2, L3 ; sem par —
Ciclo C₅, Bipartite check
bipartido Não ; testemunha do ciclo ímpar C → B → A → E → D → C
Grade 4 × 5, Bipartite check
bipartido Sim ; esquerda 10 nós começando em 1-1, 1-3, 1-5, 2-2; direita 10 começando em 1-2, 1-4, 2-1
Os dois algoritmos de fluxo concordam em 19 , e as arestas de corte confirmam o limite: S→A carrega 10 e B→D carrega 9 , somando o fluxo máximo. O sumidouro recebe 9 por C→T e 10 por D→T, de novo 19 .
Por que o corte prova o fluxo O teorema max-flow min-cut diz que o melhor fluxo é igual ao gargalo mais barato. O Dinic para quando não resta caminho aumentante; o painel então mostra os nós ainda alcançáveis a partir de S — o lado da fonte S, B — e as arestas que o deixam, S→A e B→D , cujas capacidades 10 e 9 somam o fluxo. Cada unidade precisa cruzar esse corte, então não existe fluxo maior. Do lado do emparelhamento, o teorema de Kőnig dá o mesmo estilo de prova: um emparelhamento de tamanho 3 e uma cobertura de vértices de tamanho 3 se fixam mutuamente.
Limites
O emparelhamento precisa de um grafo bipartido. Rode Hungarian matching na predefinição Petersen e o painel recusa com "Graph is not bipartite (odd cycle O3 → O2 → O1 → O5 → O4 → O3) — the Hungarian/Kuhn algorithm does not apply" em vez de devolver uma resposta parcial. Emparelhamento para grafos gerais não é oferecido.
Um par fonte-sumidouro por vez, sem custos. Não há fluxo de custo mínimo, fluxo multicommodity nem limites inferiores nas arestas; rode os pares por vez e compare os lados da fonte. O que ele não faz. Não enumera cortes além do mínimo reportado e não importa arquivos de rede. Construa a rede na tela e leve a matriz de adjacência para math tools para mais álgebra, ou liste a alcançabilidade com Components .
A armadilha da direção As arestas de corte são impressas como pares direcionados. Na predefinição Flow direcionada são S→A e B→D ; no grafo padrão não direcionado, Dinic A→F imprime A→B, A→C com lado da fonte A . O lado da fonte é a leitura estável entre execuções — tudo o que ainda é alcançável a partir de S quando o algoritmo para —, então compare essa linha, não a direção das setas, quando reconferir um corte à mão.
Onde é útil Planejamento de capacidade A predefinição de fluxo mostra quanto de uma demanda de 19 unidades pode passar e onde fica o gargalo: S→B mantém 1 unidade de folga enquanto A→D deixa 2 , mas o corte S→A / B→D está saturado. Aumente a capacidade de uma aresta de corte e o valor do fluxo muda; aumente uma aresta dentro da rede e normalmente não muda.
Problemas de atribuição Em Bipartite K₃,₃ o painel Hungarian emparelha os três nós esquerdos e imprime uma cobertura do mesmo tamanho, então a atribuição é comprovadamente máxima. Grades respondem Sim à verificação bipartida com uma divisão igual 10/10, enquanto C₅ responde Não e devolve o ciclo ímpar — o certificado de que não existe 2-coloração. O painel Traversal pode então mostrar os grupos de cor nó a nó.
Privacidade Todos os cálculos de fluxo, coloração e emparelhamento rodam no seu navegador; nada é enviado.
Referências
Wikipedia, Maximum flow problem , en.wikipedia.org (访问日期:2026-10-07)— caminhos aumentantes e valor do fluxo.
Wikipedia, Max-flow min-cut theorem , en.wikipedia.org (访问日期:2026-10-07)— fluxo igual à capacidade do corte.
Wikipedia, Bipartite graph , en.wikipedia.org (访问日期:2026-10-07)— 2-coloração e ciclos ímpares.
Wikipedia, Maximum cardinality matching , en.wikipedia.org (访问日期:2026-10-07)— emparelhamento por caminhos aumentantes.
Wikipedia, Kőnig's theorem (graph theory) , en.wikipedia.org (访问日期:2026-10-07)— emparelhamento igual à cobertura de vértices em grafos bipartidos.
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