La respuesta de Miguel Oliveira parece suficiente, la idea general es correcta. Pero cuando me pidió que respondiera, intentaré completar algunos detalles más.
Para una prueba más formal, necesitará la siguiente declaración sobre el algoritmo de Kruskal:
- Deje que [math] E_i [/ math] sea el primer borde [math] i [/ math] procesado por el algoritmo de Kruskal.
- Deje [math] M_i [/ math] ser el conjunto de aristas del algoritmo de Kruskal ya seleccionado como aristas MST.
- Sea [math] G [X] [/ math] el gráfico con todos los vértices originales y [math] X [/ math] como el conjunto de aristas.
Para cada [matemática] i [/ matemática], los componentes conectados de [matemática] G [E_i] [/ matemática] son los mismos que los componentes conectados de [matemática] G [M_i] [/ matemática]. Esto es obvio / fácilmente probado por inducción.
- Cómo dominar algoritmos, estructuras de datos y desarrollar un enfoque de resolución de problemas
- ¿Alguien podría dar una explicación detallada del algoritmo de Lee para encontrar contornos cercanos en una región?
- ¿Cuál es el algoritmo más eficiente para calcular el modo de una matriz de enteros?
- ¿Cuál es el peor caso, el caso promedio y la mejor complejidad de tiempo de un algoritmo?
- ¿Qué algoritmo de ML debo usar para una aplicación de selección de automóviles basada en Tinder?
Ahora considere dos vértices [math] u [/ math] y [math] v [/ math]. Sea [math] d [/ math] la distancia del cuello de botella para [math] u [/ math] y [math] v [/ math]: es decir, la longitud de borde más pequeña de manera que podamos caminar entre [math] u [ / math] y [math] v [/ math] utilizando solo bordes de longitud [math] d [/ math] o menos.
Sea [math] i [/ math] el índice de manera que [math] E_i [/ math] sea el conjunto de todos los bordes de longitud [math] d [/ math] o menos. Según la definición de [matemáticas] d [/ matemáticas] y [matemáticas] i [/ matemáticas], los vértices [matemáticas] u [/ matemáticas] y [matemáticas] v [/ matemáticas] están en el mismo componente de [matemáticas] G [E_i] [/ matemáticas]. Por la propiedad anterior del algoritmo de Kruskal [math] u [/ math] y [math] v [/ math] también están en el mismo componente de [math] G [M_i] [/ math].
La declaración de la pregunta original sigue trivialmente: la ruta entre [math] u [/ math] y [math] v [/ math] en [math] G [M_i] [/ math] estará allí en el MST final, y esta ruta solo contiene bordes de longitud [math] d [/ math] o menos.
Aquí hay algunos comentarios adicionales sobre esta tarea:
Para resolver el problema original, en realidad no tiene que construir el MST. Solo necesita encontrar la última ventaja agregada por el algoritmo de Kruskal: o, de manera equivalente, la [matemática] i [/ matemática] más pequeña de manera que [matemática] G [E_i] [/ matemática] esté conectada.
Ambos algoritmos dados en el análisis de USACO son rápidos y están cerca de ser óptimos. En la práctica, debe elegir cualquiera de ellos. Aún así, es interesante darse cuenta de que hay una mejor solución. De hecho, la tarea se puede resolver en el tiempo óptimo [matemático] O (mn) [/ matemático], es decir, en [matemático] O (v + e) [/ matemático] para un gráfico general con [matemático] v [ / math] vértices y [math] e [/ math] bordes.
El algoritmo es significativamente más complicado. Aquí hay una idea general: Queremos encontrar la [matemática] i [/ matemática] más grande de modo que el gráfico todavía esté desconectado. En cualquier momento, tendremos algunos bordes aceptados (y sabremos los componentes conectados que producen), algunos bordes rechazados (ya sabemos que son demasiado largos) y algunos bordes activos. En cada paso, encuentre la mediana de los bordes activos e intente agregar la mitad más pequeña al gráfico. Si aún nos deja con más de un componente, acepte esos bordes, de lo contrario rechace el borde activo medio y todos los bordes más largos. (Las complicaciones radican en implementar el paso en O (# de bordes activos), sin que la complejidad dependa de la cantidad de vértices. Se puede hacer pero es complicado).
