Localizando o corte mínimo de um gráfico não direcionado

25

Aqui está uma pergunta de um exame passado que estou tentando resolver:

Para um gráfico não direcionado com pesos positivos , estou tentando encontrar o corte mínimo. Não conheço outras maneiras de fazer isso além de usar o teorema de min-cut de fluxo máximo. Mas o gráfico não é direcionado, então como devo direcioná-lo? Pensei em direcionar arestas nas duas extremidades, mas qual vértice seria a fonte e qual vértice seria o coletor? Ou existe outra maneira de encontrar o corte mínimo?w ( e ) ≥ 0Gw(e)≥0

algorithms graph-theory Jozef
fonte
11
Se você não tem origem e destino no gráfico original, acho que precisará tentar várias opções. (Para qualquer dado e , o corte mínima não pode separar os dois.)tst
Raphael
Você está tentando encontrar o min-cut para determinados nós de origem e coletor ou o min-cut do gráfico?
Peter
@ Peter: O corte mínimo do gráfico.
Jozef

Respostas:

13

Existem muitos algoritmos para encontrar o min-cut de um gráfico não direcionado. O algoritmo de Karger é um algoritmo aleatório simples, porém eficaz.

Em suma, o algoritmo funciona selecionando arestas uniformemente aleatoriamente e contratando-as com auto-loops removidos. O processo é interrompido quando há dois nós restantes e os dois representam um corte. Para aumentar a probabilidade de sucesso, o algoritmo aleatório é executado várias vezes. Enquanto faz as corridas, mantém o controle do menor corte encontrado até agora.

Veja a entrada da Wikipedia para mais detalhes. Para talvez uma introdução melhor, confira o primeiro capítulo de Probabilidade e computação: algoritmos aleatórios e análise probabilística de Michael Mitzenmacher e Eli Upfal.

Juho
fonte
Este é um algoritmo de aproximação?
Strin
@Strin É um algoritmo aleatório que encontra o corte mínimo com alta probabilidade.
Juho
11
Não acho que o Karger's seja apropriado para encontrar um corte de peso mínimo. A derivação da probabilidade de encontrar um corte mínimo depende de encontrar um corte de cardinalidade mínima; É improvável que a Karger's encontre um corte mínimo com muitas arestas leves.
Sumudu Fernando
8

(u,v,weight)(u,v,weight)(v,u,weight)

... mas então qual vértice seria a fonte e qual vértice seria o coletor?

Não importa.

Pratik Deoghare
fonte
11
Por que isso não importa?
The Coding Wombat
1

O algoritmo Ford-Fulkerson deve funcionar para você. Você pode criar dois vértices falsos viz. a fonte e afundar.

Veja também o algoritmo Edmonds-Karp . Existem duas variações:

  1. Uma versão escolhe o caminho mais curto
  2. Outro escolhe um caminho com a capacidade máxima

, ao contrário de Ford-Fulkerson, que escolhe um caminho arbitrário.

Este é um bom recurso.

ajmartin
fonte
Bem-vindo ao cs.stackexchange! Pode ajudar o OP se você puder explicar melhor como os vértices falsos estão conectados ao gráfico existente. E quais serão os pesos das arestas?
Paresh