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

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:

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

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:

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:

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.

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 ) $G=(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 $e=\{v,w\}\in E \setminus F$$w(e)=m$$e$$C$$m$$F\cap C$$F\cap C$$m$$e$

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 |$e$$G$$e$$e$$O(|E||V|)$

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

$\ $ 1. Execute o algoritmo de Kruskal no para encontrar um MST .$G$$m$

$\ $ 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 $G$$m$$m$$m$

$\ $ 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|))$$m$$O(|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 '$m'$$m$$G$$m$$w$$w$$m$$m'$$m$$m'$$w$$w$$m'$ 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 que$m$$e'$$S$$S\subset m$$w$$m$$e'$$w$$m$$S$$w$$S\subset m'.$$e'$ está em . Como , onde é uma árvore, deve conectar duas árvores diferentes em e o algoritmo sai nesse momento.$m'$$\{e'\}\cup S\subset m'$$m'$$e'$$S$

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 .

$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$

• $m$$l$$m$$l$$l$$c$$l$$m$$m$$m_1$$m_2$$m_1$$m_2$$l$$c$m $m_1$$m_2$. Nomeie essa borda . Seja a união dem $l'$$m'$$m_1$$m_2$$l'$$G$$m$$m'$$m$$m'$$l$$l'$$l$
• $m$$h'$$m$$h'$$m$$c$$h$$c$$h'$$m'$$m$$h$$h'$$m$$m'$$m$$m'$$h$$h'$$h'$$c$$h'$

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

$m$$e$$e$$m$$e$$m$$m$

"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.

• $e$$e$$\Leftrightarrow$ $e$$\Leftrightarrow$ $e$
• $e$$e$$\Leftrightarrow$ $e$$\Leftrightarrow$ $e$

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

$ab\rightarrow 1, bc\rightarrow 1, cd\rightarrow 1, da\rightarrow 2, ac\rightarrow 2$

$1,1,2$