Atualizando um MST

Dado um não dirigida, ligado, gráfico ponderada , onde é a função de ponderação e uma árvore de cobertura mínima (MST) de . Agora vamos diminuir o peso por de uma borda que não não pertencem a . $G = (V,E,w)$$w$$w: E \to \mathbb{R}$$T$$G$
$k$$e$$T$

Como atualizar eficientemente para torná-lo um MST (denotado ) de , onde é o mesmo que exceto que ?$T$$T'$$G'=(V,E,w')$$w'$$w$$w'(e) = w(e) - k$

O algoritmo para atualizar para é fácil: Adicionando para cria um ciclo em . Deixe ser uma vantagem máxima ponderados no ciclo . Se , então é o MST conforme desejado. Caso contrário, .$T$$T'$$e$$T$$C$$T$$e'$$C$$w(e') > w’(e)$$T' = T \cup \{e\} - \{e'\}$$T' = T$

Tenho dificuldade em provar sua correção por contradição. Suponha que é uma árvore de abrangência de G ' e w' (T '') <w '(T') .$T''$$G'$$w'(T'') < w'(T')$

• $e \notin T''$ : temos $w(T'') = w'(T'') < w'(T') \le w(T)$ . Contradiz com o fato de que $T$ é uma MST de $G$ .
• $e \in T''$ : Estou preso aqui.

Duas notas:

• A resposta aceita aqui para a mesma pergunta é muito geral para eu seguir.

• Prefiro provas que não se baseiam em algoritmos concretos de MST, como os algoritmos de Kruskal e Prim. No entanto, você não precisa provar isso por contradição ou separar os dois casos e como eu fiz.$e \notin T''$$e \in T''$

Deixe- ser uma árvore de cobertura mínima de . Vamos ser a borda que modificar para obter'e deixá- ser a árvore calculado de acordo com o algoritmo. Sabemos que o peso de é menor ou igual ao peso de .$T$$G$$e$$G'$$T'$$T'$$T$

Primeiro, é uma árvore - criamos exatamente um ciclo no algoritmo e o quebramos, para não termos ciclos em .$T'$$T'$

Em segundo lugar, é uma árvore de abrangência de . Seja a borda removida e seja a borda adicionada no algoritmo (temos ou ). Para ser uma árvore de abrangência, precisamos ter um caminho entre cada par de vértices , usando apenas arestas de . Suponha que em (que é definitivamente uma árvore de abrangência), o caminho de até não envolva , o mesmo caminho existe em . Como alternativa, suponha que ele usou$T'$$G'$$e'$$e''$$e'' = e'$$e'' = e$$u$$v$$T'$$T$$u$$v$$e'$$T'$$e'$, existe um caminho (sem perda de generalidade) de para um ponto final de e do outro ponto final de para . Também existe um caminho de um ponto final de para o outro ponto final via (ao redor do ciclo), tudo dentro de . Em seguida, podemos construir um caminho de para via em mesclando esses três caminhos e removendo a sobreposição (embora uma caminhada seja suficiente para a conectividade).$u$$e'$$e'$$v$$e'$$e''$$T'$$u$$v$$e''$$T'$

Agora, a parte importante, queremos provar que é uma árvore de abrangência mínima para .$T'$$G'$

Caso 1 : O algoritmo não adiciona à árvore. Neste caso, . Suponha que exista uma árvore de abrangência mínima para que seja diferente de . Se tem o mesmo peso que , terminamos. Agora, suponha, por contradição, que o peso de seja menor que o peso de . Deve haver alguma aresta de menor peso que esteja em mas não em (deve haver alguma aresta que se sai melhor, caso contrário não teria peso menor que$e$$T' = T$$H$$G'$$T'$$H$$T'$$H$$T'$$e'$$H$$T'$$G$$T'$além disso, podemos assumir que a margem que se sai melhor é a menor margem de peso que não está em - podemos pegar qualquer que seja uma árvore de peso menor que e olhar para o candidato a , se não estiver. menor do que qualquer aresta em seu ciclo, então não é um MST, ou podemos criar um novo onde trocamos o por alguma aresta de , esse processo deve terminar com uma aresta que possui o propriedade que é a borda que faz melhor).$T'$$H'$$T'$$e'$$H'$$H'$$e'$$T'$$e'$

1. Se , considere a árvore obtida adicionando a (observe, não ) e removendo a borda de maior peso no ciclo formado. Essa nova árvore tem peso menor que o de e é uma árvore de abrangência para , contradizendo o fato de que é um MST para - então sabemos que isso não pode acontecer.$e' \neq e$$e'$$T$$T'$$T$$G$$T$$G$
2. Se , considere o ciclo formado adicionando a (isto é, o que o algoritmo considerou). Todas as outras arestas do ciclo têm peso menor que (caso contrário, o algoritmo incluiria como aresta) e, portanto, devem estar em (como é a aresta de menor peso que ainda não está em ), mas então deve conter um ciclo, então não é uma árvore e temos uma contradição.$e' = e$$e' = e$$T'$$e'$$e$$H$$e'$$T'$$H$

Caso 2 : O algoritmo adiciona a . Seja a aresta em que é removida pelo algoritmo (e, portanto, não em ). Novamente, assuma que temos outro MST como antes. Se o peso for o mesmo, estamos felizes. Portanto, assuma por contradição que tenha peso menor e, como antes, é o limite de peso mais baixo em que não está em . Podemos fazer argumentos semelhantes aos de antes com .$e$$T'$$x$$T$$T'$$H$$H$$e'$$H$$T'$$x$

1. Se (observe também que ), podemos melhorar como antes, mas sabemos que é um MST e, lembrando-se da propriedade que podemos assumir, tem peso menor que em menos uma aresta no ciclo induzida pela adição, isso dá uma contradição e não pode existir.$e' \neq x$$e' \neq e$$T$$T$$e'$$H$
2. Se , novamente deve ter um peso maior que todas as outras arestas do ciclo, portanto, deve conter todas essas arestas e não é uma árvore, e derivamos uma contradição.$e' = x$$e'$$H$$H$

Portanto, em todos os casos, derivamos uma contradição; portanto, não pode haver uma árvore de abrangência de menor peso que ; portanto, é uma árvore de abrangência mínima para .$T'$$T'$$G'$

Deixe- ser uma árvore de amplitude de um gráfico de aresta ponderados . Chamamos a um local-mínimos árvore geradora de se por toda a borda não em , é uma vantagem a mais pesada no ciclo criado quando adicionamos para .$S$$G$$S$$G$$e$$S$$e$$e$$S$

Deixe-me apresentar um teorema sobre a árvore de abrangência mínima (MST).

Uma árvore de abrangência é um MST se, e somente se, é uma árvore de abrangência local mínima.

Uma prova do teorema acima pelo próprio OP não depende de nenhum algoritmo MST concreto.

Em outra prova do teorema acima, mas declarado de maneira diferente , você também pode ler o motivo pelo qual uma árvore de abrangência é chamada "local-mínimo".

O teorema acima nos permite verificar um MST borda a borda, embora o MST seja definido com relação a todas as arestas juntas.

Uma vez armados com o teorema acima, fica fácil provar a correção do algoritmo na pergunta. Na verdade, deve ser mais fácil construir uma prova do que ler a prova rigorosa abaixo.

Uma prova simples do algoritmo na pergunta

Vamos reutilizar todas as notações na definição de OP do algoritmo.

Note-se que é uma árvore spanning-mínimo local de . Para provar que é um MST de , mostraremos que é uma árvore de abrangência local mínima de . Existem dois casos.$T$$G$$T'$$G'$$T'$$G'$

• quando e . $w(e')\leq w'(e)$$T'=T$

  Como a única diferença entre em e em é o peso da aresta , precisamos verificar apenas . Como é uma aresta mais pesada em com , a condição significa que é uma aresta mais pesada em com . Nós terminamos neste caso.$T$$G$$T'$$G'$$e$$e$$e'$$C$$w$$w'(e) \geq w(e')$$e$$C$$w'$

• quando e .$w(e')\gt w'(e)$$T' = T \cup \{e\} - \{e'\}$

  1. Vamos considerar . O ciclo criado quando adicionamos de é também . Como é uma aresta mais pesada em com , o novo peso de , significa que permanece uma aresta mais pesada em com .$e'$$e'$$T'$$C$$e'$$C$$w$$e$$w'(e) \lt w(e')$$e'$$C$$w'$
  2. Agora seja uma aresta que não esteja em . Deixe- ser o ciclo criado quando adicionamos a . Como é um MST de , é uma aresta mais pesada em com . $f\neq e'$$T'$$D$$f$$T$$T$$G$$\,f$$D$$w$
     • Se , também é o ciclo criado quando adicionamos a . Como e são os mesmos em , permanece uma aresta mais pesada em com .$e'\notin D$$D$$f$$T'$$w$$w'$$D$$\,f$$D$$w'$
     • Agora, suponha que . Se substituirmos com todas as arestas em exceto , obteremos de um novo ciclo , que é o ciclo criado quando adicionamos a . Como é uma aresta mais pesada em com , permanece uma aresta mais pesada em com . Como a única diferença entre e é seus valores em , para os quais temos , vemos que$e'\in D$$e'$$C$$e'$$D$$D'$$f$$T'$$e'$$C$$w$$f$$D'$$w$$w$$w'$$e$$w'(e) \lt w(e') \leq w(f) = w'(f)$$f$permanece uma aresta mais pesada em com .$D'$$w'$
  3. Combinando as etapas 1 e 2, terminamos neste caso.

Observe que o algoritmo e a prova acima funcionam bem, independentemente de o peso de estar diminuído, intacto ou aumentado.$e$

Sobre pesos iguais de arestas

É uma prática comum assumir pesos distintos de todas as arestas para uma exposição mais clara. No entanto, este post funciona bem com pesos de borda possivelmente iguais. Em particular, nos referimos a "uma aresta mais pesada", mas nunca "a aresta mais pesada".