Greedy: Árbol Recubridor Mínimo Flashcards
Explique qué se busca encontrar en el problema del Árbol Recubridor Mínimo
Dado un grafo, se busca encontrar un árbol que conecte todos los nodos del grafo original, con la menor suma posible de costos de los ejes.
Explique la definición formal del problema del Árbol Recubridor Mínimo
Sea G=(V,E) un grafo conexo y ponderado (con costos w positivos), queremos seleccionar un subconjunto de ejes T (incluídos en E) de tal forma que:
- El nuevo grafo
G = (V,T)seaconexo(todos sus vértices están conectados). - El costo total
W = ∑(Wt)sea mínimo entre todos los posibles grafos conexos.
¿Qué es un árbol en términos de grafos?
Un árbol es un grafo simple no dirigido, conexo y sin ciclos.
El nuevo grafo G' es conexo. ¿Podría tener ciclos?
El nuevo grafo G' no tendrá ciclos.
Si tuviese ciclos, podríamos extraer un eje del ciclo y el grafo resultante sería conexo con un costo menor.
Pero G' es el grafo con el costo total mínimo entre todos los posibles, por lo que nunca tiene ciclos.
¿Cuántos árboles recubridores existen para un grafo G? ¿Son todos mínimos?
Para un grafo G, existen varios posibles árboles recubridores, pero sólo un conjunto de ellos (o 1) es mínimo.
Explique el concepto de Propiedad de Corte.
Supongamos que todos los costos de los ejes son diferentes. Se tiene un subset de nodos S no vacío y un subconjunto de ejes F.
- Todos los ejes de F van a tener un extremo en S y otro en V-S.
- De todos los ejes de F, hay al menos uno que tiene el menor costo en comparación con los demás. Esto significa que hay al menos un eje en F que tiene el costo más bajo y que conecta a S con V-S.
Explique el algoritmo de Kruskal
- Inicialmente todos los nodos de
G=(V,E)son árboles de un bosque. - Iterativamente, se recorren los ejes E, del de menor costo al de mayor costo.
2.a. En cada iteración, se analiza el eje: si agregarlo une a dos árboles diferentes, se agrega.
2.b. Si agregar el eje une a dos nodos del mismo árbol, se desecha. - El resultado es un árbol recubridor mínimo.
Kruskal: Optimalidad. ¿Kruskal es óptimo?
Kruskal es óptimo.
Por como se seleccionan los ejes, se elije el menos costoso que une a dos subespacios y que no crea un ciclo.
Entonces el eje elegido pertenece a cualquier árbol recubridor mínimo de G, por propiedad de corte.
=> Siempre devuelve un árbol recubridor mínimo.
Explique el Algoritmo de Prim.
- Inicialmente, se selecciona un nodo
udel grafo, y se dice queS = {u}. - Se repite mientras que el subconjunto V-S no esté vacío.
2.a. Se selecciona el eje con menor costo que une ambos subconjuntos.
2.b. Se agrega el nodo de V-S al subconjunto S.
¿Prim es óptimo?
Prim es óptimo.
Por como se selecciona cada eje, se elije el menos costoso que una a S con V-S.
Entonces el eje elegido pertenece a cualquier árbol recubridor mínimo de G, por propiedad de corte.
=> Siempre devuelve un árbol recubridor mínimo.
¿Cuál es la diferencia principal entre Kruskal y Prim?
Para un grafo con N nodos:
- Kruskal comienza con N árboles aislados.
- Prim comienza con 2 árboles aislados: S (con 1 nodo) y V-S (con N-1 nodos).
Explique el Algoritmo de Eliminación Inversa
- Inicialmente, se tiene el grafo completo
- Iterativamente, se recorren los ejes de E, del más costoso al menos costoso
2.a. En cada iteración, se analiza el eje. Si al eliminarlo, el grafo es conexo, se elimina.
2.b. Si al eleiminarlo, el grafo deja de ser conexo, se mantiene. - El resultsdo es un árbol recubridor mínimo.
El algoritmo de Eliminación Inversa, al contrario de Kruskal y Prim, puede generar ciclos. ¿Cómo los eliminamos?
Si existe un ciclo en el grafo, el eje de mayor costo en el ciclo no pertenece al árbol recubridor mínimo.
Algoritmo de Eliminación Inversa: ¿Qué pasa si tengo ejes con costos iguales? ¿Existe un único árbol recubridor mínimo?
Es indiferente cuál se selecciona, la eliminación de cualquiera de los dos lleva a un árbol recubridor mínimo.
Pueden existir varios Árboles Recubridores Mínimos
Resolver con Kruskal, Prim y Eliminación Inversa.
Encontrar el árbol recubridor mínimo para el siguiente grafo:
EJES
- A : B = 7
- A : C = 1
- C : D = 6
- C : E = 6
- B : E = 1
- D : E = 3
- E : F = 5
- B : F = 4
- D : G = 8
- E : H = 8
- H - I = 2
Se mantienen los ejes:
- A : C
- C : D (o C : E, es lo mismo)
- D : G
- D : E
- E : B
- E : H
- H : I
- B : F
