Algoritmo para encontrar el diámetro de un árbol usando BFS / DFS. Por que funciona

28

Este enlace proporciona un algoritmo para encontrar el diámetro de un árbol no dirigido usando BFS / DFS . Resumiendo:

Ejecute BFS en cualquier nodo del gráfico, recordando el nodo que descubrió por última vez. Ejecute BFS desde que recuerda el nodo v descubierto por última vez. d (u, v) es el diámetro del árbol.

Por que funciona

La página 2 de esto proporciona un razonamiento, pero es confuso. Cito la parte inicial de la prueba:

Ejecute BFS en cualquier nodo del gráfico, recordando el nodo que descubrió por última vez. Ejecute BFS desde que recuerda el nodo v descubierto por última vez. d (u, v) es el diámetro del árbol.

Corrección: Sea ayb cualquiera de los dos nodos, de modo que d (a, b) sea el diámetro del árbol. Hay un camino único de a a b. Sea t el primer nodo en esa ruta descubierto por BFS. Si las rutas de s a u y de a a b no comparten bordes, entonces la ruta de t a u incluye s. Asi quep1p2

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

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

.... (más desigualdades siguen ..)

Las desigualdades no tienen sentido para mí.

curryage
fuente
No encuentro la cita en la pregunta vinculada.
Raphael
1
Intente reemplazar "no compartir bordes" con "no compartir vértices" en la solución.
Yuval Filmus
Está utilizando solo BFS, no DFS.
Miniatura

Respuestas:

11

Todas las partes de probar el reclamo dependen de 2 propiedades cruciales de los árboles con bordes no dirigidos:

  • 1-conectividad (es decir, entre 2 nodos en un árbol hay exactamente una ruta)
  • cualquier nodo puede servir como la raíz del árbol.

Elija un nodo de árbol arbitrario . Suponga que son nodos con . Supongamos además que el algoritmo encuentra un nodo comienza en primero, algún nodo comienza en continuación. wlog . tenga en cuenta que debe mantenerse, a menos que la primera etapa del algoritmo no termine en . Veremos que .u , v V ( G ) d ( u , v ) = d i a m ( G ) x s y x d ( s , u ) d ( s , v ) d ( s , x ) d ( s , y ) x d ( x , y ) =su,vV(G)d(u,v)=diam(G)xsyxd(s,u)d(s,v)d(s,x)d(s,y)xd(x,y)=d(u,v)

La configuración más general de todos los nodos involucrados se puede ver en los siguientes pseudo-gráficos (posiblemente o o ambos): s = z x ys=zuvs=zxy

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

lo sabemos:

  1. d ( u , v ) < d i a m ( G )d(zuv,y)d(zuv,v) . de lo contrario contradiciendo la suposición.d(u,v)<diam(G)
  2. d ( u , v ) < d i a m ( G )d(zuv,x)d(zuv,u) . de lo contrario contradiciendo la suposición.d(u,v)<diam(G)
  3. xd(s,zxy)+d(zxy,x)d(s,zuv)+d(zuv,u) , de lo contrario la etapa 1 del algoritmo no se detuvo en .x
  4. yd(zxy,y)d(v,zuv)+d(zuv,zxy) , de lo contrario, la etapa 2 del algoritmo no se habría detenido en .y

1) y 2) implican .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) y 4) implican equivalente to .d(zxy,y)+d(s,zxy)+d(zxy,x)d(s,zuv)+d(zuv,u)+d(v,zuv)+d(zuv,zxy)d(x,y)=d(zxy,y)+d(zxy,x)2d(s,zuv)+d(v,zuv)+d(u,zuv)d(u,v)

por lo tanto .d(u,v)=d(x,y)

las pruebas analógicas son válidas para las configuraciones alternativas

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

y

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

Estas son todas las configuraciones posibles. en particular, debido al resultado de la etapa 1 del algoritmo y debido a la etapa 2.y p a t h ( x , u ) , y p a t h ( x , v )xpath(s,u),xpath(s,v)ypath(x,u),ypath(x,v)

colapsar
fuente
(1) Con respecto al primer gráfico, ¿no debería la ruta de s a x siempre contener los vértices uy v en algún orden ya que están presentes en el árbol generado por BFS? (2) ¿Podría aclarar cómo se obtienen las desigualdades? (3) Dado que el BFS que comienza desde sy el que comienza desde x contiene u, v en algún lugar de la ruta, creo que el gráfico debe ser como se muestra en el enlace imgur.com/jQ94erY . ¿Cómo se aplica el razonamiento que proporcionó aquí?
curryage
¡@curryage tenga en cuenta que el árbol está dado y no está siendo construido por bfs! respuestas específicas: anuncio 1) no. imagine un refinamiento del árbol en los gráficos (1) agregando arbitrariamente muchos nodos en el borde y exactamente 1 nodo en el borde . la primera etapa bfs terminará en x. ad 2) ¿qué desigualdades no están claras? Siempre estamos suponiendo que sea ​​una ruta de la longitud del diámetro del gráfico . esto está bien definido ya que G está conectado a 1. ad 3) no: 3.1 hay más de 1 ruta entre 2 nodos aparte de , por lo que el gráfico no es un árbol. ...( z x y , x ) ( u , v ) d i a g ( G ) ( s , y )(s,zxy)(zxy,x)(u,v)diag(G)(s,y)
collapsar
@curryage ... 3.2 ; esto es imposible ya que por suposición y el diámetro de un gráfico es la distancia mínima máxima entre dos nodos. en el caso de un árbol, hay exactamente 1 ruta entre 2 nodos, por lo que la definición se reduce a "distancia máxima entre dos nodos". d ( u , v ) = d i a m ( G )d(x,y)>d(u,v)d(u,v)=diam(G)
collapsar
9

La intuición detrás es muy fácil de entender. Supongamos que tengo que encontrar la ruta más larga que existe entre dos nodos en el árbol dado.

Después de dibujar algunos diagramas, podemos observar que la ruta más larga siempre ocurrirá entre dos nodos de hoja (nodos que solo tienen un borde vinculado). Esto también se puede demostrar por contradicción de que si la ruta más larga es entre dos nodos y uno o ambos no es un nodo hoja, entonces podemos extender la ruta para obtener una ruta más larga.

Entonces, una forma es verificar primero qué nodos son nodos hoja, luego iniciar BFS desde uno de los nodos hoja para obtener el nodo más alejado de él.

En lugar de encontrar primero qué nodos son nodos hoja, comenzamos BFS desde un nodo aleatorio y luego vemos qué nodo está más alejado de él. Deje que el nodo más alejado sea x. Está claro que x es un nodo hoja. Ahora, si iniciamos BFS desde x y verificamos el nodo más alejado de él, obtendremos nuestra respuesta.

Pero, ¿cuál es la garantía de que x será un punto final de una ruta máxima?

Veamos por un ejemplo: -

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

Supongamos que comencé mi BFS desde 6. El nodo a una distancia máxima de 6 es el nodo 7. Usando BFS podemos obtener este nodo. Ahora iniciamos BFS desde el nodo 7 para obtener el nodo 9 a la distancia máxima. La ruta del nodo 7 al nodo 9 es claramente la ruta más larga.

¿Qué pasa si BFS que comenzó desde el nodo 6 dio 2 como el nodo a la distancia máxima? Luego, cuando vamos a BFS desde 2, obtendremos 7 como nodo a la distancia máxima y la ruta más larga será entonces 2-> 1-> 4-> 5-> 7 con longitud 4. Pero la longitud de ruta más larga real es 5. Esto no puede sucede porque BFS del nodo 6 nunca dará el nodo 2 como nodo a la distancia máxima.

Espero que ayude.

MayankPratap
fuente
1
¡Esa es una explicación simple y clara! gracias :)
anekix
4

Aquí hay una prueba que sigue más de cerca el conjunto de soluciones MIT vinculado en la pregunta original. Para mayor claridad, usaré la misma notación que usan para que la comparación se pueda hacer más fácilmente.

Supongamos que tenemos dos vértices y modo que la distancia entre y en el camino es un diámetro, por ejemplo, la distancia es la distancia máxima posible entre dos puntos en el árbol. Supongamos que también tenemos un nodo (si , entonces sería obvio que el esquema funciona, ya que el primer BFS obtendría , y el segundo volvería a a). Supongamos también que tenemos un nodo tal que .ababp(a,b)d(a,b)sa,bs=abud(s,u)=maxxd(s,x)

Lema 0: Tanto como son nodos foliares.ab

Prueba: si no fueran nodos de hoja, podríamos aumentar extendiendo los puntos finales a los nodos de hoja, contradiciendo que es un diámetro.d(a,b)d(a,b)

Lema 1: .max[d(s,a),d(s,b)]=d(s,u)

Prueba: supongamos, en aras de la contradicción, que tanto como eran estrictamente menores que . Nos fijamos en dos casos:d(s,a)d(s,b)d(s,u)

Caso 1: camino que hace no contienen vértice . En este caso, no puede ser el diámetro. Para ver por qué, deje que sea ​​el vértice único en con la menor distancia a . Luego, vemos que , ya que . Del mismo modo, también tendríamos . Esto contradice que es un diámetro.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)

Caso 2: la ruta contiene el vértice . En este caso, nuevamente no puede ser el diámetro, ya que para algunos vértices tal que , tanto como sería mayor que .p(a,b)sd(a,b) ud(s,u)=maxxd(s,x)d(a,u)d(b,u)d(a,b)

Lema 1 da la razón por la que empezamos el segundo primero en amplitud de búsqueda en la última descubierto vértice de los primeros BFS. Si es el vértice único con la mayor distancia posible desde , entonces según el Lema 1, debe ser uno de los puntos finales de algún camino con una distancia igual al diámetro y, por lo tanto, un segundo BFS con como la raíz encuentra inequívocamente diámetro. Por otro lado, si hay al menos otro vértice tal que , entonces sabemos que el diámetro es , y no importa si comenzamos el segundo BFS en o .u s u vuusuvd(s,v)=d(s,u)d(a,b)=2d(s,u)uv

xdavidliu
fuente
Increíble. Gracias por publicar esta respuesta. Me sorprende que esta respuesta no haya recibido ningún voto positivo.
Zephyr
0

Primero ejecute un DFS desde un nodo aleatorio, luego el diámetro de un árbol es la ruta entre las hojas más profundas de un nodo en su subárbol DFS: ingrese la descripción de la imagen aquí

seddik11
fuente
44
¿Por qué funciona esto?
Yuval Filmus
0

Según la definición de BFS, la distancia (desde el nodo inicial) de cada nodo explorado es igual a la distancia del nodo anterior explorado o mayor en 1. Por lo tanto, el último nodo explorado por BFS estará entre los más alejados desde el inicio nodo.

Por lo tanto, el algoritmo de utilizar BFS cantidades dos veces para "escoger un nodo arbitrario . Encuentre el nodo de más alejado de (último nodo encontrado por BFS a partir de ). Encuentre el nodo más alejado de (último nodo encontrado por BFS a partir de ). ", que encuentra dos nodos de distancia máxima entre sí.xaxxbaa

Extrarius
fuente
1
Gracias por la respuesta con la intuición. Sin embargo, el "así" en la última oración no es obvio. ¿Por qué sigue eso? ¿Por qué el nodo más alejado de tiene que ser uno de los dos nodos a una distancia máxima entre sí? Parece que eso necesita alguna prueba. x
DW
No estoy seguro de cómo construir tal prueba. Siento que lo contrario es intuitivamente cierto: si dos nodos están a una distancia máxima entre sí, entonces, para cualquier nodo dado, uno de los dos está a la mayor distancia posible de él.
Extrarius
La afirmación "intuitivamente verdadera" no es cierta en general para los gráficos generales. Vea el gráfico en cs.stackexchange.com/a/213/755 e imagine comenzar el BFS desde el nodo (es decir, sea ); entonces elegirá y encontrará el nodo a la mayor distancia de , pero eso no encuentra los dos nodos de distancia máxima entre sí. Entonces, la afirmación reclamada, si es cierta, debe basarse en alguna propiedad especial de los árboles que no se cumple para los gráficos generales. vx=va=uba
DW
Sí, pero esta pregunta especifica árboles no dirigidos, que es el contexto en el que estoy intuyendo. Restringir los ciclos y los bordes dirigidos hace que muchos problemas de gráficos sean mucho más fáciles de razonar.
Extrarius
0

Una cosa clave que debe saber es que un árbol siempre es plano, lo que significa que se puede colocar en un plano, por lo que a menudo funciona el pensamiento bidimensional ordinario. En este caso, el algoritmo dice que comenzar en cualquier lugar, ir lo más lejos posible. La distancia desde ese punto hasta donde puede alejarse de ese punto es la distancia más larga en el árbol y, por lo tanto, el diámetro.

Este método también funcionaría para encontrar el diámetro de una isla física real si lo definiéramos como el diámetro del círculo más pequeño que encerraría completamente la isla.

Viejo pro
fuente
0

@op, la forma en que se definen los casos en el PDF puede estar un poco fuera de lugar.

Creo que los dos casos deberían ser:

  1. p1 no se cruza con , es decir, no hay vértices comunes entre las rutas y . En este caso, defina como el primer nodo en descubierto por el primer BFS que comienza en .p2p1p2tp2s

  2. p1 y tienen al menos un vértice común. En este caso, defina como el primer nodo en descubierto por el primer BFS que también está en .p2tp2p1

El resto de la prueba en el PDF debe seguir.

Con esta definición, la figura mostrada por OP cae en el caso 2.

usuario650654
fuente