Ejercicio 1
Hay 5 ciudades. El costo de construir una carretera directamente entre i y j es la entrada a(i,j) en la siguiente matriz. Una entrada indefinida indica que la carretera no se puede construir. Determine el costo mínimo para hacer que todas las ciudades sean accesibles entre sí.
Ordenamos las aristas según los pesos: 12, 23, 13, 45, 25, 15, 24, 35, 14 (fila-columna). El algoritmo de Kruskal acepta los bordes 12, 23, luego rechaza el 13, luego acepta el 45, 25 y luego se detiene. Por lo tanto, el costo mínimo para construir la red de carreteras es 3 + 3 + 7 + 8 = 21.
Ejercicio 2
El profesor Herr Guerard propone un nuevo algoritmo de divide y vencerás para calcular árboles de expansión mínimos, que es el siguiente.
Dado un grafo G = (V, E), dividir el conjunto V de vértices en dos conjuntos V1 y V2 tales que |V1| y |V2| difieren como máximo en 1. Sea E1 el conjunto de aristas que inciden sólo en los vértices de V1, y sea E2 el conjunto de aristas que inciden sólo en los vértices de V2. Resuelva recursivamente 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 falla el algoritmo. Encuentre un ejemplo donde funciona y donde no.
Afirmamos que el algoritmo fallará. A continuación se muestra un contraejemplo simple. El grafo 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}. El MST de G1 tiene un peso de 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 un peso de 1, en suma, el árbol de expansión formado por el algoritmo propuesto sigue a {v2, v1 , v4, v3} que tiene un peso de 10. Por el contrario, es obvio que el MST de G sigue a {v4, v1, v2, v3} con un peso de 7. Por lo tanto, el algoritmo propuesto no logra obtener un MST.
Ejercicio 3
Demuestre que si G es un grafo ponderado y e es una arista cuyo peso es menor que cualquier otra arista, entonces e debe pertenecer a todo árbol generador de peso mínimo para G.
Supongamos que T es un árbol generador de peso mínimo para G que no contiene la arista e. Considere entonces el gráfico T+e. Este gráfico debe contener un ciclo C que contiene la arista e. Sea f una arista de C diferente de e, y sea T*=T+e−f. Entonces T* también es un árbol de expansión para G, pero w(T*)=w(T+e−f)=w(T)+w(e)−w(f) < w(T), a diferencia de T siendo un árbol de expansión de peso mínimo. Por lo tanto, tal árbol T (es decir, sin e) no puede existir.
Ejercicio 4
Muestre que si todos los pesos del grafo ponderado G son distintos, entonces hay un único árbol generador de peso mínimo para G.
La prueba imita algo la de la prueba del algoritmo de Kruskal. Supongamos que T es un árbol generado por el algoritmo de Kruskal (de hecho, un momento de reflexión muestra que con las condiciones del problema, solo se podría generar un árbol de este tipo).
Afirmamos que no hay otros árboles de expansión de peso mínimo para G. Supongamos (y mostraremos que esto conduce a una contradicción) que existen otros árboles de expansión de peso mínimo y elija uno cualquiera, T'. Supongamos entonces que e es la primera arista de T que no pertenece a T'. Es decir, supongamos que las aristas de T, en el orden en que fueron sumadas para formar T, son e1, e2 , …, ek , …en−1 y que e = ek y para todo i <k, ei ∈T’ .
Sea C el ciclo en T'+ e que contiene a 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. De hecho, 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), nous aurions utilisé f à ce stade. Alors maintenant l’ensemble T*=T’+e−f est un arbre couvrant de poids inférieur à T’, une 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 borde son distintos, ¿este nuevo algoritmo calcula correctamente un MST?
Sí. En el paso k (comenzando con ak = 1), el algoritmo considera la k-ésima ventaja de costo más grande. Si esta arista pertenece a un ciclo en el grafo restante T, entonces todas las aristas de este ciclo (y de hecho de T) deben tener un coste inferior al de la arista considerada. Por lo tanto, el borde no puede pertenecer al MST (según la pregunta anterior).
El algoritmo no puede terminar con T teniendo un ciclo, porque el algoritmo habría considerado cada arista en dicho ciclo y habría eliminado la arista de mayor costo cuando consideró esa arista. El algoritmo tampoco puede terminar con T desconectada, porque las aristas solo se eliminan cuando pertenecen a un ciclo, y desconectar una arista que pertenece a un ciclo no desconecta el gráfico. Por lo tanto, el algoritmo termina siendo T un árbol de expansión.
Es el MST porque todas las aristas que se han borrado tienen la propiedad de no pertenecer al MST. Dado que los únicos bordes que podrían pertenecer al MST son los restantes y, de hecho, definen un árbol de expansión, debe ser el MST.
ES 
FR 
EN