La página presenta varios ejercicios corregidos sobre problemas de teoría de grafos. Estos ejercicios tratan sobre problemas de árbol de expansión.
Ejercicio 1
Hay 5 ciudades. El costo de construir una carretera directamente entre i y j es la entrada ayo, j en la matriz a continuación. Una entrada indefinida indica que la carretera no se puede construir. Determine el menor costo de hacer que todas las ciudades sean accesibles entre sí.
Ordenamos los bordes según los pesos: 12, 23, 13, 45, 25, 15, 24, 35, 14 (columna sin procesar). El algoritmo de Kruskal acepta los bordes 12, 23, luego rechaza 13, luego acepta 45, 25 y luego se detiene. Por lo tanto, el menor costo para construir la red de carreteras es 3 + 3 + 7 + 8 = 21.
Ejercicio 2
El profesor Herr Guerard propone una nueva divide y conquistaras algoritmo para calcular árboles de expansión mínimos, que es el siguiente.
Dado un gráfico G = (V, E), divida el conjunto V de vértices en dos conjuntos V1 y V2 tal que | V1| y | V2| difieren como máximo en 1. Sea E1 el conjunto de aristas que inciden solo en los vértices de V1y deja que E2 ser el conjunto de aristas que inciden solo en vértices en V2. Resuelva de forma recursiva un problema de árbol de expansión mínimo en cada uno de los dos subgrafos G1 = (V1, E1) y G2 = (V2, E2). Finalmente, seleccione el borde de peso mínimo en E que cruza el corte V1, V2 y use este borde para unir los dos árboles de expansión mínimos resultantes en un solo árbol de expansión.
O argumenta que el algoritmo calcula correctamente un árbol de expansión mínimo de G, o proporciona un ejemplo en el que el algoritmo falla. Encontré un ejemplo de dónde funciona y dónde no funciona.
Afirmamos que el algoritmo fallará. A continuación se muestra un ejemplo de contador simple. El gráfico G = (V, E) tiene cuatro vértices: {v1, v2, v3, v4}, y se divide en subconjuntos G1 con V1 = {v1, v2} y G2 con V2 = {v3, v4}. Té ETS de G1 tiene peso 4, y el MST de G2 tiene un peso de 5 y el borde de peso mínimo que cruza el corte (V1, V2) tiene peso 1, en suma, el árbol de expansión que se forma mediante el algoritmo propuesto sigue {v2, v1, v4, v3} que tiene peso 10. Por el contrario, es obvio que el MST de G sigue {v4, v1, v2, v3} con peso 7. Por lo tanto, el algoritmo propuesto no logra obtener un MST.
Ejercicio 3
Demuestre que si G es una gráfica ponderada ye es una arista cuyo peso es menor que el de cualquier otra arista, entonces e debe pertenecer a cada árbol de expansión de peso mínimo para G.
Suponga que T es un árbol de expansión de peso mínimo para G que no contiene el borde e. Luego considere la gráfica T + e. Este gráfico debe contener un ciclo C que contenga el borde e. Sea f una arista de C diferente de e, y establezca T * = T + e - f. Entonces T * es también un árbol de expansión para G, pero w (T *) = w (T + e - f) = w (T) + w (e) −w (f) <w (T), contrario a T siendo un árbol de expansión de peso mínimo. Por tanto, tal árbol T (es decir, sin e) no puede existir.
Ejercicio 4
Demuestre que si todos los pesos del gráfico ponderado G son distintos, entonces existe un árbol de expansión de peso mínimo único para G.
La prueba imita un poco a la prueba del algoritmo de Kruskal. Supongamos que T es un árbol generado por el algoritmo de Kruskal (de hecho, un momento de pensamiento muestra que con las condiciones del problema, solo se podría generar uno de esos árboles).
Afirmamos que no hay otros árboles de expansión de peso mínimo para G. Suponga (y mostraremos que esto conduce a una contradicción) que hay otros árboles de expansión de peso mínimo y elija uno, T '. Entonces suponga que e es el primer borde de T que no está en T '. En otras palabras, suponga que las aristas de T, en el orden en que se agregaron para formar T, son e1, e2 ,…, Ek ,… En - 1 y que e = ek y por todo yo <k, eI ∈T '.
Sea C el ciclo en T '+ e que contiene e. sea f una arista de C que no está en T '. Observamos que por la naturaleza del algoritmo de Kruskal, el peso de f debe ser mayor que el peso de e. Esto se debe a que en el momento en que colocamos e en T, f también estaba disponible y no habría producido un ciclo (ya que todas las aristas de T hasta ese punto también están en T '). Entonces si w (f) <w(e), we would have used f at that juncture. So now set T*=T’+e−f is a spanning tree of weight less than T’, a contradiction.
Ejercicio 5
Considere un algoritmo de Kruskal "invertido" para calcular un MST. Inicialice T para que sea el conjunto de todos los bordes del gráfico. Ahora, considere los bordes de mayor a menor costo. Para cada borde, elimínelo de T si ese borde pertenece a un ciclo en T. Suponiendo que todos los costos de los bordes son distintos, ¿este nuevo algoritmo calcula correctamente un MST?
Si lo hace. En la etapa k (comenzando ak = 1), el algoritmo considera la k-ésima ventaja de costo más grande. Si ese borde pertenece a un ciclo en el gráfico T restante, entonces todos los bordes en ese ciclo (y de hecho en T) deben tener un costo menor que el borde que se está considerando. Por tanto, el borde no puede pertenecer al MST (por la pregunta anterior).
El algoritmo no puede terminar con T teniendo un ciclo, ya que el algoritmo habría considerado cada borde en dicho ciclo y habría eliminado el borde del mayor costo cuando consideró ese borde. El algoritmo tampoco puede terminar con la desconexión de T, ya que los bordes solo se eliminan cuando pertenecen a un ciclo, y la desconexión de un borde que pertenece a un ciclo no desconecta el gráfico. Por tanto, el algoritmo termina siendo T un árbol de expansión.
Es el MST porque todos los bordes que se eliminaron tienen la propiedad de que no pueden pertenecer al MST. Dado que los únicos bordes que podrían pertenecer al MST son los que quedan, y de hecho definen un árbol de expansión, debe ser el MST.
ES 
FR 
EN