As árvores de abrangência mínima de um gráfico ponderado têm o mesmo número de arestas com um determinado peso?

21

Se um gráfico ponderado tiver duas árvores abrangentes mínimas diferentes e , é verdade que, para qualquer aresta em , o número de arestas em com o mesmo peso de (incluindo o próprio ) é igual ao número de arestas em com o mesmo peso que ? Se a afirmação é verdadeira, como podemos provar isso?G T 1 = ( V 1 , E 1 ) TGT1=(V1,E1) 2 = ( V 2 , E 2 ) e E 1 E 1 eT2=(V2,E2)eE1E1e e E 2 eeE2e

Aden Dong
fonte
Uma abordagem complicada, porém viável, é mostrar 1) O algoritmo de Kruskal pode produzir todas as árvores abrangentes mínimas e 2) todas as árvores abrangentes mínimas encontradas pela Kruskal têm o mesmo multiset de peso de borda.
Raphael

Respostas:

16

Reivindicação: Sim, essa afirmação é verdadeira.

Esboço de prova: Seja duas árvores de abrangência mínimas com multisets com peso de borda . Suponha e denote sua diferença simétrica com .T 1 , T 2 T1,T2W 1 , W 2 W1,W2W 1W 2W1W2W = W 1 Δ W 2W=W1ΔW2

Escolha a aresta com , ou seja, e é uma aresta que ocorre em apenas uma das árvores e tem peso mínimo de discordância. Tal uma vantagem, que é, em particular, de e \ em T_1 \ mathop {\ Delta} T_2 , existe sempre: claramente, nem todas as arestas de peso \ min W podem estar em ambas as árvores, caso contrário, \ min W \ W notin . O Wlog deixa e \ in T_1 e assume que T_1 tem mais arestas de peso \ min W do que T_2 .e T 1 Δ T 2eT1ΔT2 w ( e ) = min W w(e)=minWe ee T 1 Δ T 2e T1ΔT2 min W min Wmin W W min WWe T 1 e T1T 1T1 min W min Wt doisT2

Agora considere todas as arestas em que também estão no corte que é induzido por em . Se houver uma aresta que tenha o mesmo peso que , atualize usando vez de ; observe que a nova árvore ainda é uma árvore de abrangência mínima com o mesmo multiset de peso de borda que . Iteramos esse argumento, reduzindo por dois elementos e, assim, removendo uma aresta do conjunto de candidatos a em cada etapa. Portanto, seguimos finamente várias etapas para uma configuração em que todas as arestas emT 2 T2C T 1 ( e ) CT1( E )e eT 1 T1e 'e e eT 1 T1e 'e e eT 1T1 W We eT 2C T 1 ( e ) T2CT1( E )(onde é a versão atualizada) tem pesos diferentes de .T 1T1 w ( e )w ( e )

Agora podemos sempre escolher de tal forma que podemos trocar e ¹, ou seja, podemos criar uma nova árvore de spanninge C T 1 ( e ) T 2eCT1( E ) T2 e ee e

T 3 = { ( T 1{ e } ) { E ' } , w ( e ' ) < w ( e ) ( T 2{ E ' } ) { e } , w ( e ' ) > w ( e )T3={(T1{e}){e},(T2{e}){e},w(e)<w(e)w(e)>w(e)

que tem peso menor que e ; isso contradiz a escolha de como árvores abrangentes mínimas. Portanto, .T 1 T1T 2 T2T 1 , T 2 T1,T2W 1 = W 2W1=W2


  1. Os nós incidentes de estão em conectados por um caminho ; é a aresta única em .e eT 2T2 P Pe e P C T 1 ( e )PCT1(e)
Rafael
fonte
3
Em referência ao comentário de Dave , eu criei essa prova depois de 0) acreditando que tinha um contra-exemplo que vi errado após o TikZing, 1) tentando provar a afirmação, mas falhando; 2) tentando construir um contra-exemplo com base em onde a prova falhou e falhou novamente e, finalmente, 3) usando a maneira como esses novos exemplos falharam em trabalhar para apresentar a prova. Provavelmente também é por isso que não é tão refinado quanto poderia ser.
Raphael
yeas exatamente, eu não entendo o que se entende por cit induzida por em eu só tinha visto corte como cortee t 1 ( S , V - S )eT1(S,VS)
dragoboy
@dragoboy Removendo desconecta ; um componente forma e o outro o complemento. e T 1 SeT1S
Raphael
5

Aqui está um argumento um pouco mais simples que também funciona para outros matróides. (Vi essa pergunta de outra .)

Suponha que tenha arestas. Sem perda de generalidade, assuma que a função de peso assume valores em ; portanto, temos uma partição de nos conjuntos para . Podemos induzir o número de não vazio e o número de vértices em ; para e qualquer , a afirmação é óbvia.G m w [ m ] E E i : = w - 1 ( i ) i [ m ] j E i n G j = 1 nGmw[m]EEi:=w1(i)i[m]jEinGj=1n

Um fato padrão sobre matróides é que para cada MST não é uma extensão linear da migração induzida por para que o algoritmo guloso produz .T w TTwT

Para fechar a indução, tome como o maior número para que não esteja vazio. Defina . Observe que qualquer extensão linear de coloca todas as arestas em antes de qualquer aresta em . De acordo com o fato, qualquer MST consiste em uma floresta de abrangência do subgrafo induzido por e algumas arestas de . Pela hipótese indutiva, cada componente conectado de tem o mesmo número de arestas de cada para . Como todas as opções dettEtEtE=E1Et1E=E1Et1wwEEEtEtFFEEEtEtFFEiEii<ti<tFFtiver o mesmo tamanho, o número de arestas de necessário para completar em uma árvore de abrangência é independente da escolha de e pronto.EtEtFFFF

Louis
fonte
Você pode dar o matroide para o problema do MST? Parece que me lembro que é algo difícil de fazer, e ainda tenho que ver isso feito (rigorosamente). Sim, usamos algoritmos gananciosos, mas não os gananciosos (canônicos) da teoria matróide.
Raphael
Dito isso, acho que seu argumento principal funciona (e nem precisa de materoides): pela correção do algoritmo de Kruskal e pelo fato de que todo MST pode ser obtido de uma execução de Kruskal com uma permutação específica (classificada) do multiset de peso ( prova rigorosa pendente), segue a reivindicação. Escrevo "provas pendentes" porque não é trivial nem imediato: sem usar a afirmação em si, não está absolutamente claro por que a Kruskal deve encontrar todos os MSTs. Claramente, se alguém tivesse um multiset de peso diferente, Kruskal nunca o encontraria!
Raphael
1. O matróide é o gráfico matróide. Feito!
Louis
2. Você está confuso. Abstratamente, estamos fazendo otimização linear sobre o politopo básico. Uma das caracterizações padrão dos matróides é que o algoritmo ganancioso funciona para qualquer escolha de pesos. Todos os w árvores de expansão -minimal são vértices de uma face deste polytope. Agora, idéias padrão do LP levam ao fato padrão que mencionei.
Louis
1. Você pode dar uma referência? Eu não conheço o gráfico matróide. 2. Agora você arrasta o LP para ele também! Tudo o que estou dizendo é que sua resposta carece do matróide, e que sem ele, a linha de raciocínio parece depender da própria afirmação. Se você tem uma maneira de contornar isso, edite / esclareça a resposta.
Raphael