Quando a árvore de abrangência mínima para um gráfico não é exclusiva

22

Dado um gráfico ponderado e não direcionado G: Quais condições devem ser verdadeiras para que haja várias árvores abrangentes mínimas para G?

Eu sei que o MST é único quando todos os pesos são distintos, mas você não pode reverter esta afirmação. Se houver várias arestas com o mesmo peso no gráfico, pode haver vários MSTs, mas também pode haver apenas um:

insira a descrição da imagem aqui

Neste exemplo, o gráfico à esquerda tem um MST exclusivo, mas o direito não.

O mais próximo que pude encontrar condições para a não exclusividade do MST foi o seguinte:

Considere todos os ciclos sem corda (ciclos que não contêm outros ciclos) no gráfico G. Se em qualquer um desses ciclos a borda ponderada máxima existir várias vezes, o gráfico não terá uma árvore de abrangência mínima exclusiva.

Minha ideia era que, para um ciclo como este

insira a descrição da imagem aqui

com n vértices, você pode deixar de fora exatamente uma das arestas e ainda ter todos os vértices conectados. Portanto, você tem várias opções para remover a borda com o peso mais alto para obter um MST, para que o MST não seja exclusivo.

No entanto, eu vim com este exemplo:

insira a descrição da imagem aqui

Você pode ver que este gráfico tem um ciclo que se ajusta à minha condição: (E, F, G, H), mas, tanto quanto eu posso ver, a árvore de abrangência mínima é única:

insira a descrição da imagem aqui

Parece que minha condição não está correta (ou talvez não esteja completamente correta). Eu adoraria qualquer ajuda para encontrar as condições necessárias e suficientes para a não exclusividade da árvore de abrangência mínima.

Keiwan
fonte
1
Seus menores ciclos são conhecidos como ciclos sem corda (mais ou menos).
Yuval Filmus

Respostas:

10

na primeira figura: o gráfico da direita possui um MST único, usando as arestas e com peso total de 2.( F , G )(F,H)(F,G)

Dado um gráfico e deixe que ser uma árvore de cobertura mínima (MST) em .M = ( V , F ) GG=(V,E)M=(V,F)G

Se existir uma aresta com peso tal que adicionar ao nosso MST produza um ciclo , e seja também o menor peso da aresta de , então podemos criar um segundo MST trocando uma aresta de com peso de borda com . Assim, não temos singularidade.w ( e ) = m e C m F C F C m ee={v,w}EFw(e)=meCmFCFCme

dtt
fonte
Você está certo, eu corrigi esse gráfico na pergunta agora. Você sabe se esta é a condição mais geral para que o MST não seja único? Ou também pode, de alguma forma, ser determinado sem a necessidade de primeiro encontrar um MST?
Keiwan
1
@Keiwan Eu acredito que, se você levar em conta essa pergunta , a condição descrita nesta resposta também será necessária para ter vários MSTs. Em outras palavras: um gráfico tem vários MSTs se e somente se a construção descrita por HueHang puder ser realizada. G
Bakuriu 10/07/16
1
m não precisa ser o menor peso da borda de F∩C. Na verdade, ele pode ter apenas o maior peso da borda, caso contrário M não teria sido mínimo em primeiro lugar. Suponha que houvesse uma aresta e 'com w (e') = m '> m = w (e) em F∩C. Então, trocar e por e 'deixaria uma árvore de abrangência com peso total menor que M, contradizendo a minimalidade de M.
Chad
2

Uma resposta anterior indica um algoritmo para determinar se há vários MSTs que, para cada borda não em , encontram o ciclo criado adicionando a um MST pré-computado e verificam se não é a borda mais pesada exclusiva nesse ciclo. É provável que esse algoritmo seja executado no tempo .G e e O ( | E | | V | )eGeeO(|E||V|)

Um algoritmo mais simples para determinar se existem múltiplas MSTs de G em tempo de complexidadeO(|E|log(|V|)) .

  1. Execute o algoritmo de Kruskal no para encontrar um MST .mGm

  2. Tente executar o algoritmo de Kruskal em novamente. Nesta execução, sempre que tivermos uma escolha entre arestas de pesos iguais, primeiro tentaremos as arestas que não estão em e depois tentaremos as arestas em . Sempre que encontramos uma aresta que não conecta duas árvores diferentes, afirmamos que existem vários MSTs, encerrando o algoritmo.m m mGmmm

  3. Se chegamos aqui, afirmamos que tem um MST único.G

Uma execução comum do algoritmo de Kruskal leva tempo . A seleção extra de arestas que não estão em pode ser feita no tempo . Portanto, o algoritmo atinge complexidade de tempo .m O ( | E | ) O ( | E | log ( | V | ) )O(|E|log(|V|))mO(|E|)O(|E|log(|V|))

Por que esse algoritmo pode determinar se existem vários MSTs?

Suponha que temos um MST que não é o mesmo que . É o suficiente para mostrar que o algoritmo em execução no não vai chegar a etapa 3, uma vez que a borda encontrado no final da etapa 2, que não está na e conectando duas árvores diferentes teriam sido incluídos no MST resultante tinha corremos Kruskal de algoritmo até a conclusão. Seja o maior peso, de modo que, para qualquer aresta com peso menor que , seja em se e somente se for em . Como e têm o mesmo número de arestas de peso , existem arestas de peso que estão em m L m w w m m ' m m ' w w m " m e " S S m w m e ' w m S w S m ' . e " m " { e ' } S m ' m ' e ' SmmGmwwmmmmwwm mas não em . Se o algoritmo saiu antes de processar as bordas dessas bordas, estamos prontos. Caso contrário, suponha que o algoritmo processe a primeira aresta entre essas arestas agora. Seja o conjunto de todas as arestas que foram preservadas até o momento para serem incluídas no MST resultante. . Como o algoritmo não concluiu o processamento da aresta de peso em , como em , ele não deve ter começado a processar as arestas de peso em . Portanto, as arestas em pesam menos que . Isso significaLembre-se quemeSSmwmewmSwSm.e está em . Como , onde é uma árvore, deve conectar duas árvores diferentes em e o algoritmo sai nesse momento.m{e}SmmeS

Nota sobre o desenvolvimento adicional Os
passos 1 e 2 podem ser intercalados para que possamos terminar o algoritmo o mais rápido possível sem processar bordas de pesos maiores.
Caso você queira calcular o número de MSTs, verifique uma resposta sobre como calcular o número de MSTs .

Apass.Jack
fonte
1

G

  • Uma aresta é a mais pesada do ciclo exclusivo se for a aresta mais pesada única em algum ciclo.
  • Uma aresta não é a mais pesada do ciclo, se nunca for a mais pesada de qualquer ciclo.
  • Uma aresta é o corte mais leve exclusivo se for a borda mais leve exclusiva para atravessar algum corte.
  • Uma aresta não é mais clara se nunca for uma aresta mais clara para atravessar qualquer corte.
  • Dois STs são adjacentes se todo ST tiver exatamente uma aresta que não está no outro ST.
  • Um MST é um MST isolado se não estiver adjacente a outro MST (quando os dois MSTs são considerados STs).

Quando há mais de uma árvore de abrangência mínima?

G

  • Existem dois MSTs adjacentes.
  • Não há MST isolado.
  • Existe um ST que é tão leve quanto ou mais leve que todos os ST adjacentes e que é tão leve quanto um ST adjacente.
  • Existe uma aresta que não é a mais pesada do ciclo nem a mais pesada do ciclo.
  • Existe uma aresta que não é nem a mais leve nem a mais leve

A novidade desta resposta é principalmente as duas últimas caracterizações. O segundo da última caracterização pode ser considerado o próximo passo da abordagem do OP . As três primeiras caracterizações juntas podem ser consideradas como uma versão ligeiramente aprimorada da resposta do dtt .

G

Quando as árvores de abrangência mínima são únicas?

G

  • Exclusividade do MST : existe um MST exclusivo.
  • Nenhum MST adjacente : não há MSTs adjacentes.
  • Um MST isolado : existe um MST isolado.
  • Um ST local mínimo : existe um ST mais leve que todos os ST adjacentes.
  • Extremidade extrema do ciclo : cada extremidade é única com o ciclo mais pesado ou sem o ciclo mais pesado.
  • Extremidade de corte extrema : todas as arestas são únicas ou mais leves

Aqui vem a minha prova.

"Exclusividade do MST" => "Nenhum MST adjacente": óbvio.

"Nenhum MST adjacente" => "Um MST isolado": óbvio.

"Um MST isolado" => "Um ST mínimo local": Um MST isolado é mais leve que todos os STs adjacentes.

m

  • mlmllclmmm1m2m1m2lcm 2m1m2. Nomeie essa borda . Seja a união dem lmm1m2lGmmmmlll
  • mhmhmchchmmhhmmmmhhhch

"ST local mínimo" => "Extremidade extrema": a prova é deixada como exercício.

meememm

"Extremidade extrema" => "Exclusividade do MST": a prova é deixada como um exercício.

As cadeias de implicações acima comprovam o teorema.

Mais uma vez, a novidade dessas respostas é principalmente a propriedade "borda extrema do ciclo" e a propriedade "borda extrema do corte", que usa os conceitos mais pesado e não mais leve. Eu não vi esses conceitos em outro lugar, embora sejam bastante naturais.


Aqui estão duas observações interessantes relacionadas.

  • ee e e
  • ee e e

Duas condições suficientes, mas não necessárias, para MST exclusivo

ab1,bc1,cd1,da2,ac2

1,1,2

Apass.Jack
fonte