Prova de correção:Algoritmo para diâmetro de uma árvore na teoria dos grafos

Question

Para encontrar o diâmetro de uma árvore, posso pegar qualquer nó da árvore, executar o BFS para encontrar o nó mais distante dele e, em seguida, executar o BFS nesse nó.A maior distância do segundo BFS produzirá o diâmetro.

Não tenho certeza de como provar isso?Tentei usar indução no número de nós, mas há muitos casos.

Quaisquer ideias serão muito apreciadas...

Answer 1

Vamos chamar o endpoint encontrado pelo primeiro BFS X. O passo crucial está provando que o X encontrado neste primeiro passo sempre "funciona" - isto é, que é sempre em uma extremidade de algum caminho mais longo. (Observe que, em geral, pode haver mais de um caminho igualmente mais longo.) Se pudermos estabelecer isso, é direto ver que um BFS enraizado em X encontrará algum nó o mais longe possível de X, que deve, portanto, ser um caminho mais longo.

dica: Suponha (em contrário) que há um caminho mais longo entre dois vértices u e v, nenhum dos quais é x.

Observe que, no caminho exclusivo entre U e V, deve haver algum mais alto (mais próximo da raiz) vértice h. Existem duas possibilidades: ou H está no caminho da raiz do BFS para X, ou não é. Mostrar uma contradição mostrando que em ambos os casos, o caminho U-V pode ser feito pelo menos, por enquanto, substituindo algum segmento de caminho nele com um caminho para x.

[editar] Na verdade, pode não ser necessário tratar os dois casos separadamente depois de tudo. Mas muitas vezes acho mais fácil quebrar uma configuração em vários casos (ou até mesmo) e trate cada um separadamente. Aqui, o caso em que H está no caminho da raiz do BFS para X é mais fácil de manusear, e dá uma pista para o outro caso.

[edit 2] voltando para isso mais tarde, agora parece-me que os dois casos que precisam ser considerados são (i) o caminho UV intercepta o caminho da raiz para X ( em alguns vértice y, não necessariamente no ponto mais alto do caminho UV); e (ii) não. Ainda precisamos de h para provar cada caso.

Answer 2

eu vou malhar dica de j_random_hacker.Deixar s, t ser um par maximamente distante.Deixar u seja o vértice arbitrário.Temos um esquema como

    u
    |
    |
    |
    x
   / \
  /   \
 /     \
s       t ,

onde x é a junção de s, t, u (ou seja,o único vértice que se encontra em cada um dos três caminhos entre esses vértices).

Suponha que v é um vértice maximamente distante de u.Se o esquema agora se parecer com

    u
    |
    |
    |
    x   v
   / \ /
  /   *
 /     \
s       t ,

então

d(s, t) = d(s, x) + d(x, t) <= d(s, x) + d(x, v) = d(s, v),

onde a desigualdade se mantém porque d(u, t) = d(u, x) + d(x, t) e d(u, v) = d(u, x) + d(x, v).Existe um caso simétrico onde v anexa entre s e x em vez de entre x e t.

O outro caso parece

    u
    |
    *---v
    |
    x
   / \
  /   \
 /     \
s       t .

Agora,

d(u, s) <= d(u, v) <= d(u, x) + d(x, v)
d(u, t) <= d(u, v) <= d(u, x) + d(x, v)

d(s, t)  = d(s, x) + d(x, t)
         = d(u, s) + d(u, t) - 2 d(u, x)
        <= 2 d(x, v)

2 d(s, t) <= d(s, t) + 2 d(x, v)
           = d(s, x) + d(x, v) + d(v, x) + d(x, t)
           = d(v, s) + d(v, t),

então max(d(v, s), d(v, t)) >= d(s, t) por um argumento de média, e v pertence a um par maximamente distante.

Answer 3

Aqui está uma maneira alternativa de olhar para ele:

Suponha g = ( v , e ) é uma árvore não-feminina e finita com conjunto de vértices v e borda set e .

Considere o seguinte algoritmo:

.
1. deixe count = 0. Deixe todas as bordas e inicialmente ser insolente. Deixe c inicialmente ser igual a v .
2. Considere o subconjunto v 'de v contendo todos os vértices com exatamente uma borda Uncrolored:
   • se v 'está vazio, então deixe d = contar * 2, e parar.
   • se v 'contém exatamente dois elementos, em seguida, cor sua borda mútua (uncolored) verde, deixe d = contar * 2 + 1 e pare.
   • de outra forma, v 'contém pelo menos três vértices; Proceda da seguinte forma:
3. incremento contar por um.
4. Remova todos os vértices de c que não têm bordas não coloridas.
5. Para cada vértice em v com duas bordas ou mais insignificantes, colore cada uma das suas bordas verdes vermelhas (alguns vértices podem ter zero essas bordas). .
6. para cada vértice em v ', cor sua borda uncolored verde.
7. Retornar ao passo (2).

que basicamente colore o gráfico das folhas para dentro, marcando caminhos com distância máxima para uma folha em verde e marcando aqueles com apenas distâncias mais curtas em vermelho. Enquanto isso, os nós de c , o centro, com distância máxima mais curta a uma folha são pared até c contém apenas o único ou dois nós com a maior distância máxima para uma folha.

Por construção, todos os caminhos simples de vértices foliares para o vértice central mais próximo que viaja apenas bordas verdes são o mesmo comprimento ( count ), e todos os outros caminhos simples de um vértice foliar para o seu centro mais próximo vértice (atravessando pelo menos uma borda vermelha) são mais curtas. Pode além disso, ser provado que

• este algoritmo sempre termina sob as condições dadas, deixando cada borda de g colorido vermelho ou verde, e deixando c com um ou dois elementos.
• na terminação de algoritmo, d é o diâmetro de g , medido em bordas.
• Dado um vértice v em v , os caminhos simples de comprimento máximo em g < / forte> Começando em v são exatamente aqueles que contêm contêm todos os vértices do centro, terminam em uma folha, e percorrem apenas bordas verdes entre o centro e o extremo extremo. Estes vão de v , do outro lado do centro, para uma das folhas mais distantes do centro.

---

.

Agora considere seu algoritmo, que pode ser mais prático, à luz do acima. A partir de qualquer vértice v , há exatamente um caminho simples p a partir desse vértice, terminando em um vértice central e contendo todos os vértices do centro (porque g é uma árvore, e se houver dois vértices em c então eles compartilham uma borda) . Pode ser mostrado que os caminhos simples maximais em g tendo v como um endpoint todos têm a forma da união de p com um caminho simples do centro para folha atravessando apenas bordas verdes.

O ponto chave para os nossos propósitos é que a borda recebida do outro ponto de extremidade é necessariamente verde. Portanto, quando realizamos uma busca pelos caminhos mais longos que começam lá, temos acesso àqueles que percorrem apenas bordas verdes da folha através (todos os vértices de) o centro para outra folha. Esses são exatamente os caminhos simples de comprimento máximo em g , para que possamos estar confiantes de que a segunda pesquisa realmente revelará o diâmetro do gráfico.

Answer 4

1:procedureTreeDiameter(T)

2:pick an arbitrary vertex v where v∈V

3:u = BFS ( T, v )

4:t = BFS ( T, u )

5:return distance ( u, t )

Result: Complexity = O(|V|)