Prueba de corrección:Algoritmo para el diámetro de un árbol en teoría de grafos.

https://stackoverflow.com//questions/20010472

20-12-2019
|

Pregunta

Para encontrar el diámetro de un árbol, puedo tomar cualquier nodo del árbol, realizar BFS para encontrar el nodo que esté más alejado de él y luego realizar BFS en ese nodo.La mayor distancia desde el segundo BFS dará como resultado el diámetro.

¿Pero no estoy seguro de cómo probar esto?Intenté utilizar la inducción en la cantidad de nodos, pero hay demasiados casos.

Cualquier idea será altamente apreciada...

Solución

Llamemos al punto final encontrado por el primer BFS X. El paso crucial está demostrando que la X encontrada en este primer paso siempre "funciona", es decir, que siempre está en un extremo de un camino más largo. (Tenga en cuenta que en general puede haber más de un camino igualmente más largo). Si podemos establecer esto, es sencillo ver que un BFS enraizado en X encontrará un nodo en la medida de lo posible de X, que, por lo tanto, debe ser un general camino más largo.

Sugerencia: supongamos (al contrario) que hay un camino más largo entre dos vértices u y v, ninguno de los cuales es x.

Observa que, en el camino único entre U y V, debe haber algunas más altas (más cercanas a la raíz) h. Hay dos posibilidades: la H está en el camino de la raíz de la BFS a X, o no lo es. Muestre una contradicción mostrando que en ambos casos, la ruta U-V se puede hacer al menos tan larga al reemplazar algún segmento de ruta con un camino hacia X.

[editar] En realidad, es posible que no sea necesario tratar los 2 casos por separado después de todo. Pero a menudo me parece más fácil romper una configuración en varios casos (o incluso muchos), y tratar cada uno por separado. Aquí, el caso en el que H está en la ruta de la raíz BFS a X es más fácil de manejar, y da una pista para el otro caso.

[Editar 2] Volviendo a esto más tarde, ahora me parece que los dos casos que deben considerarse son (i), la ruta UV se cruza la ruta de la raíz a x ( a algunos vértice y, no necesariamente en el punto más alto de la ruta del UV); y (ii) no lo hace. Todavía necesitamos H para demostrar cada caso.

Otros consejos

voy a hacer ejercicio La pista de j_random_hacker.Dejar s, t ser un par máximamente distante.Dejar u ser el vértice arbitrario.Tenemos un esquema como

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

dónde x es la unión de s, t, u (es decir.el único vértice que se encuentra en cada uno de los tres caminos entre estos vértices).

Suponer que v es un vértice máximamente distante de u.Si el esquema ahora se ve así

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

entonces

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

donde se cumple la desigualdad porque d(u, t) = d(u, x) + d(x, t) y d(u, v) = d(u, x) + d(x, v).Hay un caso simétrico donde v se une entre s y x en lugar de entre x y t.

El otro caso parece

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

Ahora,

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),

entonces max(d(v, s), d(v, t)) >= d(s, t) mediante un argumento promediador, y v pertenece a un par máximamente distante.

Aquí hay una forma alternativa de verlo:

Suponer GRAMO = ( V, mi ) es un árbol finito no vacío con un conjunto de vértices V y conjunto de bordes mi.

Considere el siguiente algoritmo:

Dejar contar = 0.Deje entrar todos los bordes mi Inicialmente no estará coloreado.Dejar C inicialmente ser igual a V.
Considere el subconjunto V' de V que contiene todos los vértices con exactamente un borde sin color:
- si V' está vacío entonces deja d = contar * 2, y detente.
- si V' contiene exactamente dos elementos y luego colorea su borde mutuo (sin color) de verde, dejemos que d = contar * 2+1, y parar.
- de lo contrario, V' contiene al menos tres vértices;proceder de la siguiente:
Incremento contar por uno.
Eliminar todos los vértices de C que no tengan bordes sin color.
Para cada vértice en V con dos o más bordes sin colorear, vuelva a colorear cada uno de sus bordes verdes de rojo (algunos vértices pueden tener cero dichos bordes).
Para cada vértice en V', colorea su borde sin color de verde.
Regrese al paso (2).

Básicamente, eso colorea el gráfico desde las hojas hacia adentro, marcando los caminos con la distancia máxima a una hoja en verde y marcando aquellos con distancias más cortas en rojo.Mientras tanto, los nodos de C, el centro, con una distancia máxima más corta a una hoja, se cortan hasta C contiene sólo uno o dos nodos con la mayor distancia máxima a una hoja.

Por construcción, todos los caminos simples desde los vértices de las hojas hasta su vértice central más cercano que atraviesan solo los bordes verdes tienen la misma longitud (contar), y todos los demás caminos simples desde el vértice de una hoja hasta su vértice central más cercano (atravesando al menos un borde rojo) son más cortos.Se puede demostrar además que

este algoritmo siempre termina bajo las condiciones dadas, dejando cada borde de GRAMO de color rojo o verde, y dejando C con uno o dos elementos.
al finalizar el algoritmo, d es el diámetro de GRAMO, medido en aristas.
Dado un vértice v en V, los caminos simples de longitud máxima en GRAMO a partir de v son exactamente aquellos que contienen todos los vértices del centro, terminan en una hoja y atraviesan solo los bordes verdes entre el centro y el punto final más alejado.Estos van desde v, cruzando el centro, hasta una de las hojas más alejadas del centro.

Ahora considere su algoritmo, que podría ser más práctico, a la luz de lo anterior.Partiendo de cualquier vértice v, hay exactamente un camino simple pag desde ese vértice, terminando en un vértice central y conteniendo todos los vértices del centro (porque GRAMO es un árbol, y si hay dos vértices en C luego comparten una ventaja).Se puede demostrar que los caminos simples máximos en GRAMO teniendo v como un punto final todos tienen la forma de la unión de pag con un camino sencillo desde el centro hasta la hoja atravesando sólo los bordes verdes.

El punto clave para nuestros propósitos es que el borde entrante del otro punto final es necesariamente verde.Por lo tanto, cuando realizamos una búsqueda de los caminos más largos que comienzan allí, tenemos acceso a aquellos que atraviesan solo los bordes verdes desde la hoja a través de (todos los vértices) del centro hasta otra hoja.Esos son exactamente los caminos simples de longitud máxima en GRAMO, por lo que podemos estar seguros de que la segunda búsqueda revelará el diámetro del gráfico.

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|)

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow