Algoritmo para encontrar o diâmetro de uma árvore usando BFS / DFS. Por que isso funciona?

28

Esse link fornece um algoritmo para encontrar o diâmetro de uma árvore não direcionada usando BFS / DFS . Resumindo:

Execute o BFS em qualquer nó s no gráfico, lembrando o nó que você descobriu por último. Execute o BFS u lembrando o nó v descoberto pela última vez. d (u, v) é o diâmetro da árvore.

Por que isso funciona?

A página 2 disso fornece um raciocínio, mas é confuso. Estou citando a parte inicial da prova:

Execute o BFS em qualquer nó s no gráfico, lembrando o nó que você descobriu por último. Execute o BFS u lembrando o nó v descoberto pela última vez. d (u, v) é o diâmetro da árvore.

Correção: Seja a e b quaisquer dois nós, de modo que d (a, b) seja o diâmetro da árvore. Há um caminho único de a para b. Seja o primeiro nó nesse caminho descoberto pelo BFS. Se os caminhos de s a u e de a a b não compartilham arestas, o caminho de t a u inclui s. tãop1p2

d(t,u)d(s,u)

d(t,u)d(s,a)

.... (mais desigualdades seguem ..)

As desigualdades não fazem sentido para mim.

curryage
fonte
Não encontro a citação na pergunta vinculada.
Raphael
11
Tente substituir "não compartilhar arestas" por "não compartilhar vértices" na solução.
Yuval Filmus
Você está usando apenas BFS, não DFS.
Miniatura

Respostas:

11

Todas as partes da prova da reivindicação dependem de 2 propriedades cruciais de árvores com bordas não direcionadas:

  • Conexão 1 (ou seja, entre quaisquer 2 nós em uma árvore, existe exatamente um caminho)
  • qualquer nó pode servir como a raiz da árvore.

Escolha um nó de árvore arbitrário . Suponha que u , v V ( G ) são nós com d ( u , v ) = d i a m ( G ) . Suponha ainda que o algoritmo encontre um nó x iniciando em s primeiro, algum nó y iniciando em x próximo. wlog d ( s , u ) d ( s , v ) . Observe quesu,vV(G)d(u,v)=diam(G)xsyxd(s,u)d(s,v) deve permanecer, a menos que o primeiro estágio do algoritmo não termine em x . Veremos que d ( x , y ) = d ( u , v ) .d(s,x)d(s,y)xd(x,y)=d(u,v)

A configuração mais geral de todos os nós envolvidos pode ser vista nos pseudo gráficos a seguir (possivelmente ou s = z x y ou ambos):s=zuvs=zxy

(u)                                            (x)
  \                                            /
   \                                          /
    \                                        /
     ( z_uv )---------( s )----------( z_xy )
    /                                        \
   /                                          \
  /                                            \
(v)                                            (y)

nós sabemos isso:

  1. . outra forma de d ( u , v ) < d i um m ( L ) contrariando a suposição.d(zuv,y)d(zuv,v)d(u,v)<diam(G)
  2. . outra forma de d ( u , v ) < d i um m ( L ) contrariando a suposição.d(zuv,x)d(zuv,u)d(u,v)<diam(G)
  3. ; caso contrário, o estágio 1 do algoritmo não teria parado em x .d(s,zxy)+d(zxy,x)d(s,zuv)+d(zuv,u)x
  4. ; caso contrário, o estágio 2 do algoritmo não teria parado em y .d(zxy,y)d(v,zuv)+d(zuv,zxy)y

1) e 2) implicam .d(u,v)=d(zuv,v)+d(zuv,u)d(zuv,x)+d(zuv,y)=d(x,y)+2d(zuv,zxy)d(x,y)

3) e 4) implicam d(zxy,y)+d(s,zxy)+d(zxy,x)d(s,zuv)+d(zuv,u)+d(v,zuv)+d(zuv,zxy) equivalente a .d(x,y)=d(zxy,y)+d(zxy,x)2d(s,zuv)+d(v,zuv)+d(u,zuv)d(u,v)

portanto .d(u,v)=d(x,y)

provas analógicas valem para configurações alternativas

                 (u)                          (x)
                   \                          /
                    \                        /
                     \                      /
     ( s )---------( z_uv )----------( z_xy )
                     /                      \
                    /                        \
                   /                          \
                 (v)                          (y)

e

                          (x)        (u)  
                          /            \  
                         /              \ 
                        /                \
     ( s )---------( z_xy )----------( z_uv )
                        \                /          
                         \              /           
                          \            /            
                          (y)        (v)            

essas são todas as configurações possíveis. em particular, devido ao resultado do estágio 1 do algoritmo e y p a t h ( x , u ) , y A p a t h ( x , v ) devido ao estágio 2.xpath(s,u),xpath(s,v)ypath(x,u),ypath(x,v)

colapsar
fonte
(1) Em relação ao primeiro gráfico, o caminho de s até x não deve sempre conter os vértices u e v em alguma ordem, pois estão presentes na árvore gerada pelo BFS? (2) Você poderia esclarecer como as desigualdades são obtidas? (3) Como o BFS a partir de s e o x a partir de x contêm u, v em algum lugar do caminho, acredito que o gráfico deve ser como mostrado no link imgur.com/jQ94erY . Como o raciocínio que você forneceu se aplica aqui?
curryage 21/03
@ pressa note que a árvore é dada e não está sendo construída pelos bfs! respostas específicas: anúncio 1) não. imagine um refinamento da árvore nos gráficos (1) adicionando arbitrariamente muitos nós na borda e exatamente 1 nó na borda ( z x y , x ) . o primeiro estágio bfs terminará em x. 2) quais desigualdades não são claras? estamos sempre assumindo que ( u , v ) seja um caminho com o comprimento do diâmetro do gráfico d i a g ( G )(s,zxy)(zxy,x)(u,v)diag(G). isso está bem definido, pois G está 1 conectado. ad 3) no: 3.1 existe mais de um caminho entre dois nós separados de ; portanto, o gráfico não é uma árvore. ... #(s,y)
22414
@curryage ... 3,2 ; isso é impossível como d ( u , v ) = d i a m ( G ) por suposição e o diâmetro de um gráfico é a distância mínima mínima entre dois nós. no caso de uma árvore, existe exatamente 1 caminho entre dois nós, portanto, a definição se reduz a 'distância máxima entre dois nós'. d(x,y)>d(u,v)d(u,v)=diam(G)
precisa
9

A intuição por trás é muito fácil de entender. Suponha que eu tenha que encontrar o caminho mais longo que exista entre dois nós na árvore especificada.

Após desenhar alguns diagramas, podemos observar que o caminho mais longo sempre ocorrerá entre dois nós de folha (nós com apenas uma aresta vinculada). Isso também pode ser comprovado pela contradição de que, se o caminho mais longo estiver entre dois nós e um ou ambos os nós não for um nó folha, podemos estender o caminho para obter um caminho mais longo.

Portanto, uma maneira é primeiro verificar quais nós são nós folha e iniciar o BFS a partir de um dos nós folha para obter o nó mais distante dele.

Em vez de primeiro descobrir quais nós são nós de folha, iniciamos o BFS a partir de um nó aleatório e, em seguida, vemos qual nó está mais distante dele. Deixe o nó mais distante seja x. É claro que x é um nó folha. Agora, se iniciarmos o BFS a partir de x e verificar o nó mais distante, obteremos nossa resposta.

Mas qual é a garantia de que x será o ponto final de um caminho máximo?

Vamos ver por um exemplo: -

       1   
    / /\ \
   6 2  4 8
         \ \
          5 9
           \
            7

Suponha que eu iniciei meu BFS a partir de 6. O nó na distância máxima de 6 é o nó 7. Usando o BFS, podemos obter esse nó. Agora, estrelamos o BFS no nó 7 para obter o nó 9 à distância máxima. O caminho do nó 7 ao nó 9 é claramente o caminho mais longo.

E se o BFS iniciado no nó 6 fornecesse 2 como o nó na distância máxima. Então, quando obtermos BFS de 2, obteremos 7 como nó na distância máxima e o caminho mais longo será 2-> 1-> 4-> 5-> 7 com comprimento 4. Mas o comprimento do caminho mais longo real é 5. Isso não pode acontece porque o BFS do nó 6 nunca dará o nó 2 como nó na distância máxima.

Espero que ajude.

MayankPratap
fonte
11
isso é uma explicação simples e clara! Obrigado :)
anekix
4

Aqui está uma prova que segue o conjunto de soluções MIT vinculado mais detalhadamente à pergunta original. Para maior clareza, usarei a mesma notação usada para que a comparação possa ser feita com mais facilidade.

ababp(a,b)d(a,b)sa,bs=abud(s,u)=maxxd(s,x)

ab

d(a,b)d(a,b)

max[d(s,a),d(s,b)]=d(s,u)

d(s,a)d(s,b)d(s,u)

p(a,b)sd(a,b)tp(a,b)sd(a,u)=d(a,t)+d(t,s)+d(s,u)>d(a,b)=d(a,t)+d(t,b)d(s,u)>d(s,b)=d(s,t)+d(t,b)>d(t,b)d(b,u)>d(a,b)d(a,b)

p(a,b)sd(a,b) ud(s,u)=maxxd(s,x)d(a,u)d(b,u)d(a,b)

uusuvd(s,v)=d(s,u)d(a,b)=2d(s,u)uv

xdavidliu
fonte
Impressionante. Obrigado por postar esta resposta. Estou surpreso que esta resposta não tenha recebido nenhum voto positivo.
Zephyr
0

Primeiro, execute um DFS a partir de um nó aleatório e, em seguida, o diâmetro de uma árvore é o caminho entre as folhas mais profundas de um nó em sua subárvore DFS: insira a descrição da imagem aqui

seddik11
fonte
4
Por que isso funciona?
Yuval Filmus
0

Pela definição de BFS, a distância (a partir do nó inicial) de cada nó explorado é igual à distância do nó anterior explorado ou superior a 1. Portanto, o último nó explorado pelo BFS estará entre os mais distantes desde o início nó.

xaxxbaa

Extrarius
fonte
11
x
Não sei como construir essa prova. Eu sinto que o inverso é intuitivamente verdadeiro: se dois nós estão à distância máxima um do outro, então, para qualquer nó, um dos dois está à maior distância possível dele.
Extrarius
vx=va=uba
Sim, mas esta pergunta especifica árvores não direcionadas, que é o contexto em que estou entrando. Os ciclos de restrição e as bordas direcionadas tornam muitos problemas gráficos significativamente mais simples de se pensar.
Extrarius
0

Uma coisa importante a saber é que uma árvore é sempre plana, o que significa que ela pode ser projetada em um plano, e muitas vezes o pensamento bidimensional comum funciona. Nesse caso, o algoritmo diz que, começando em qualquer lugar, vá o mais longe possível. A distância desse ponto até onde você pode se afastar é a maior distância na árvore e, portanto, o diâmetro.

Esse método também funcionaria para encontrar o diâmetro de uma ilha física real se o definíssemos como o diâmetro do menor círculo que envolveria completamente a ilha.

Old Pro
fonte
0

@op, a maneira como os casos são definidos no PDF pode ser um pouco complicada.

Eu acho que os dois casos devem ser:

  1. p1p2p1p2tp2s

  2. p1p2tp2p1

O restante da prova no PDF deve seguir.

Com essa definição, a figura mostrada pelo OP se enquadra no caso 2.

user650654
fonte