Para responder a esta pregunta, supondré que cada borde tiene un peso de 1.
Para cada L comprobaremos si existe un árbol de expansión T, de modo que todas las rutas entre 2 vértices tengan una longitud de L como máximo, es decir, el costo (T) <= L (*). Por lo tanto, la respuesta es mínima L donde existe T. Para encontrar L, simplemente verifique cada número en el rango [1, N-1] donde N es el número de vértices en G, o haga una búsqueda binaria para un tiempo de ejecución más rápido.
Considere un árbol de expansión con costo (T) = L. Entonces, T tiene una ruta con la longitud más larga L. Para una ruta, conecte 2 vértices u y v con longitud L en T, su punto medio M divide la ruta en 2 rutas con la misma la longitud si L es par o la longitud de una ruta es 1 unidad mayor que la otra ruta si L es impar.
- ¿Cuáles son las aplicaciones más prácticas (vida cotidiana) del algoritmo de agrupación de k-means? ¿Cómo se ha utilizado exactamente k-means en estas aplicaciones?
- ¿Cuál sería un algoritmo eficiente para ordenar millones de líneas de cadenas / enteros en un archivo?
- ¿Cómo realizan las computadoras la multiplicación y la complejidad del tiempo?
- ¿Por qué no ha habido un codificador indio en la región 2400+ después de Rudradev Basak, especialmente cuando la cultura de codificación en el país está en aumento?
- No puedo entender algoritmos y estructuras de datos. ¿Cómo puedo aprender algoritmos y estructuras de datos de una manera simple?
Cuando L es par. En este caso, cada camino (en T) desde M hasta cualquier otro vértice debe tener una longitud menor o igual a L / 2. Si no es así, entonces T contiene otra ruta con una longitud mayor que L. Por otro lado, si existe un vértice M tal que la longitud de la ruta más corta (en G) desde ella a otras sea menor o igual a L / 2, entonces existe un árbol de expansión T en G tal que cuesta (T) <= L. Así podemos responder (*) fácilmente cuando L es par.
Cuando L es impar. En este caso, el punto medio M divide la ruta más larga en 2 rutas, una es de longitud L / 2 y otra es de longitud L / 2 + 1 (división entera). Fije M como la raíz del árbol de expansión T. La ruta (en el árbol de expansión T) desde M hasta cualquier otro vértice debe tener una longitud menor o igual a L / 2 + 1 y aquellos a una distancia L / 2 + 1 a M deben misma rama, eso significa que todos los caminos desde M hasta ellos deben pasar por el mismo vértice inmediatamente después de M. Lo contrario también es cierto. Considere M tal que la longitud del camino más corto (en G) desde M hasta cualquier otro vértice sea menor o igual a L / 2 + 1. Sea v_1, v_2, …, v_k los vértices cuya distancia más corta desde M hasta M es exacta L / 2 + 1. Si existe un vértice U adyacente a M tal que cualquier distancia más corta desde U a cualquier v_i (1 <= i <= k) es L / 2 (es decir, existe una ruta desde M a cualquier v_i que atraviesa U) , entonces G contiene un árbol de expansión T con costo (T) <= L. Ahora (*) se puede responder cuando L es impar.
