OIA-Wiki

Un árbol generador de un grafo, es un subgrafo conexo del mismo, que contiene a todos los vértices y no es un árbol. Estas propiedades son equivalente a decir que es un árbol que contiene todos los nodos del grafo en cuestión, y a partir del cual se puede llegar al grafo agregando aristas.

Por ejemplo:

$\rightarrow$

El árbol generador mínimo (AGM, o “MST” por sus siglas en inglés) de un grafo con aristas con pesos, es el grafo generador cuya suma de las aristas del árbol es mínimo dentro de todas las sumas de aristas de árboles generadores. En el caso de arriba, sería:

Hay dos algoritmos conocidos para encontrar el AGM: el de Prim y el de Kruskal.

Voy a contar la idea básica de ambos, sin detallar las demostraciones. Para conocerlas bien, pueden ver el link de wikipedia de Prim y Kruskal.

Idea: Inicializar un árbol con un solo nodo, cualquiera. Ir agregando de a un eje: Agrego el eje más chico de todos los que unen al árbol con nodos que no están todavía en el árbol.

Ejemplo con el grafo de arriba: Supongamos que agarramos el nodo $4$ como el árbol inicial. De todas las aristas que conectan al $4$ con otros nodos, la de valor más bajo es la arista de valor $3$, que une al $4$ con el $1$. Luego, podemos elegir la arista $(4,2)$ ó la arista $(1,5)$, ambas de valor $4$. Supongamos que agregamos la arista $(1,5)$ (es indistinto, con cualquier de las dos funciona igual). Ahora sí, la arista de valor más bajo que conecta a alguno de los nodos $4,1,5$ con los otros, es la arista $(4,2)$, de valor $4$. Entonces en nuestro árbol están los nodos $4,1,5,2$. Luego, agregamos al nodo $0$ mediante la arista $(2,0)$ de valor $4$. Y por último, el $3$ no está en el árbol, por lo que debo agregar la arista $(2,3)$. Finalmente termino con el AGM de la imagen anterior.

Este algoritmo, se puede ver como similar al algoritmo de Dijkstra, sólo que en vez de agarrar el nodo no recorrido de distancia más chica, agarramos el nodo fuera del árbol de distancia al árbol más chica.

// CODIGO

$\large O(E*log(V)$ ??

Prerrequisitos: Estructura Union Find

Idea: La idea es, ordenar las aristas de menor valor a mayor, e ir agregando desde las más chicas, las que pueda sin que se genere un ciclo. La diferencia con Prim es que en Prim tenés siempre un árbol, y agregás de a un nodo al árbol. Acá, podés tener varios arbolitos separados, que de repente agregás una arista y unís dos árboles en uno. Esta oración es copada para entender el uso de Union Find. Empezamos con todos nodos separados, y vamos agregando aristas que conecten dos árboles diferentes, es decir que pertenezcan a distintos grupitos de nodos.

Ejemplo con el grafo de arriba: Primero ponemos la arista $(1, 4)$, de valor $3$. Luego, por ejemplo, la arista $(2,0)$, de valor $4$. Es lo mismo cómo ordenamos las de mismo valor. Quizás obtenemos un AGM distinto pero seguro va a tener el mismo valor total. Acá se ve que tenemos por un lado el grupito $\{0, 2\}$ y por otro el $\{1, 4\}$. Además de los grupitos de nodos aislados $\{3\}$ y $\{5\}$. Luego, agregamos por ejemplo la arista $(2,4)$ de valor $4$. Luego $(4,5)$ de valor $4$. Ahora, la arista de menor valor que deberíamos recorrer es $(4,5)$, de valor $5$. Pero eso nos genera un ciclo. O hablando en términos de union-find, los nodos $4$ y $5$ tiene el mismo representante, ya están unidos. Entonces no la agregamos. Tampoco la arista $(4,0)$ de valor $7$. Y por último, agregamos la arista $(3,2)$ de valor $8$, ya que el $3$ era un grupito aislado del resto. Terminamos, ya que agregamos $5$ aristas y hay $6$ nodos. Tenemos el mismo AGM que nos dio Prim y que está ilustrado más arriba. (En este ejemplo, el AGM es único.)

Este código, en mi opinión, es más lindo de implementar que Kruskal. Más allá de que requiera de la estructura Union-Find, el código queda simplemente “ordenar aristas; recorrer; if(tienen distintos represantes) entonces mergear nodos”.

// CODIGO, usando lo que haya en la wiki de union find

$\large O(E*log(E))$ ??