Una propiedad definitoria de un árbol de expansión es que hay una ruta única desde cualquier vértice a cualquier otro vértice. La eliminación de un borde divide el gráfico en dos subárboles; obviamente no puede crear una ruta donde no existía ninguno anteriormente.
Ahora, su nuevo borde conecta dos nodos X e Y que anteriormente estaban en diferentes subárboles. Cada otro nodo tiene una ruta única a X o Y, pero no a ambas. Cualquier camino entre los dos componentes debe pasar por su nuevo borde. Además, solo se puede llegar a dos vértices que no estén en el mismo subárbol usando la ruta única a X, a través del nuevo borde, y luego usando la ruta única desde Y (o al revés si comienza desde el subárbol Y). El gráfico también tiene caminos únicos y es un árbol de expansión.
(La prueba de Krishna Hariram es más simple; nota que cualquier gráfico conectado con N nodos y bordes N-1 es un árbol de expansión, que ciertamente es su construcción).
- ¿Cuáles son las principales diferencias en términos de definición / idea clave, dominio de aplicación y eficiencia entre árboles de segmento, árboles de intervalo, árboles indexados binarios y árboles de rango?
- ¿Cuáles son algunos de los principales factores que pueden afectar la velocidad de ejecución de un algoritmo?
- ¿Puede un algoritmo descubrir macronutrientes a partir de una imagen?
- ¿Es posible tener un número de elementos en una matriz más que el tamaño de la matriz que se define en un momento de compilación?
- ¿Cómo es posible que el hashing sea imposible de revertir? ¿Hay alguna prueba?
