Carolina tres

Árbol de Mínima Expansión - Algoritmo de Kruskal y algoritmo de Prim |
* Árbol: Es un grafo en el que existe un único nodo desde el que se puede acceder a todos los demás y cada nodo tiene unúnico predecesor, excepto el primero, que no tiene ninguno. También podemos definir un árbol como: * Un grafo conexo y sin ciclos. * Un grafo sin ciclos y con n-1 aristas, siendo n el númerode vértices. * Grado de un nodo en un árbol es el número de subárboles de aquel nodo (en el ejemplo, el grado de v1 es 2 y de v2 1). * Denominamos hojas en un árbol a los nodos finales (v3, v5 yv6). * Un árbol de máximo alcance es aquel que obtenemos en un grafo conexo y sin ciclos. * Árbol de mínima expansión: Árbol de máximo alcance cuyo valor es mínimo, es decir, la suma de susaristas es mínima. * Algoritmo de Kruskal: El algoritmo de Kruskal permite hallar el árbol minimal de cualquier grafo valorado (con capacidades). Hay que seguir los siguientes pasos: 1. Se marcala arista con menor valor. Si hay más de una, se elige cualquiera de ellas. 2. De las aristas restantes, se marca la que tenga menor valor, si hay más de una, se elige cualquiera de ellas.3. Repetir el paso 2 siempre que la arista elegida no forme un ciclo con las ya marcadas. 4. El proceso termina cuando tenemos todos los nodos del grafo en alguna de las aristas marcadas, esdecir, cuando tenemos marcados n-1 arcos, siendo n el número de nodos del grafo. * Ejemplo: Determinar el árbol de mínima expansión para el siguiente grafo: * Siguiendo el algoritmo de Kruskal,tenemos: * Elegimos, por ejemplo, la arista (5, 6) = 1 (menor valor) y la marcamos. * Elegimos la siguiente arista con menor valor (1, 3) = 1 y la marcamos. * Elegimos la siguiente aristacon menor valor (5, 7) = 2 y la marcamos, ya que no forma ciclos con ninguna arista de las marcadas anteriormente. * Elegimos la siguiente arista con menor valor (1, 2) = 3 y la marcamos, ya...