Algoritmo de kruskal en matlab

Solo disponible en BuenasTareas
  • Páginas : 5 (1077 palabras )
  • Descarga(s) : 0
  • Publicado : 12 de mayo de 2011
Leer documento completo
Vista previa del texto
INSTRUCTIVO DEL ALGORITMO DE KRUSKAL

En este instructivo se explicará de una manera profunda el funcionamiento del algoritmo de kruskal1, su función, utilidad y funcionamiento, más específicamente en su ejecución en el software de Matlab. 1. “El algoritmo de Kruskal es un algoritmo (ávido) de la teoría de grafos para encontrar un árbol de recubrimiento mínimo en un grafo conexo y ponderado. Esdecir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor total de todas las aristas del árbol es el mínimo.” Este algoritmo es importante en la búsqueda de un árbol recubridor mínimo en un grafo conexo y ponderado, Si el grafo no es conexo, entonces busca un bosque expandido mínimo, es un algoritmo efectivo por eso muchos ingenieros le dan elcalificativo de un “algoritmo voraz”, ya que en su funcionamiento2 se trabaja por etapas, pues en estas se toma la decisión que le parece más pertinente en la búsqueda de solución optima en cada etapa sin llegar a pensar en las consecuencias futuras, por ello si en cada etapa hay una solución optima, supone que habrá una solución optima global del problema. 2. “Se parte colocando todos los vérticesdel grafo separados, y se decide partir por un vértice de "Inicio". Dado el vértice actual (en el comienzo es el de inicio), armamos una lista de todas las aristas que posee, ordenadas en forma decreciente según su ponderación (costo de la arista). Tomamos la de menor coste, retiramos de la lista de candidatos a la arista utilizada y agregamos las nuevas aristas que nos proporciona el nuevovértice. Así sucesivamente, generando subgrafos conexos hasta llegar a conectar todos los subgrafos conexos formando un Árbol de cubrimiento de costo mínimo”.

__________________________
1. Usuario “Eaven”. Algoritmo de Kruskal. Kruskal . [Citado 8 de mayo Del 2011] Documento de Dr. Joaquín V. González titulado “teoría de grafos”. Instituto Superior del Profesorado. Buenos Aires, Argentina. p.742.Nickolas Cheilakos. Kruskal Algorithm. MATLAB [En línea]. http://www.mathworks.com/matlabcentral/fileexchange/13457-kruskalalgorithm> [Citado 1 de mayo del 2011]

<

Braicovich, T. (2005). Grafos y Algoritmos en EGB3 (V Carem [Conferencia Argentina de Educación Matemática]). Buenos Aires: Prensa Académica.

CODIGO
%ingresamos la matriz de adyacencia matrizadya = input('Porfavor inserte lamatriz de pesos: '); % la matriz de abajo fue utilizada para ensayar el algoritmo. % matrizadya = [0 9 0 8 0 0 0; 7 0 6 5 4 0 0; 0 3 0 0 2 0 0; 1 3 0 0 15 6 0; 0 1 5 35 0 4 2; 0 0 0 7 9 0 11; 0 0 0 0 3 14 0]; h = view(biograph(triu(matrizadya),[],'ShowWeights','on','ShowArrows','off')) ; % esto nos ayuda a la generacion de un cuadro que nos muestra la grafica solicitada, view biograph % debemos desacar los nodos y sus determinados nodos % se generan 3 vectores para almacenar datos y ejecutar las diferentes % relaciones entre ellos rel = []; %se almacenan los datos segun la matriz de adyacencia,el peso de las aristas nodoA = []; % se almacenan los indices de la parte superior de la matriz de adyacencia teniendo en cuenta el peso de la aristas; y las relaciones pertinentes con los nodosnodoB = []; % se almacenan los indices de la parte lateral de la matriz de adyacencian teninedo presente el peso de la arista; y las relaciones con los nodos for i = 1:length(matrizadya) %la variable i forma un ciclo y recorre las filas de la matriz ingresada %el tength llega hasta el tamaño del vector for j = i:length(matrizadya) %la variable i forma un ciclo y recorre las filas de la matriz%ingresada if matrizadya(i,j) > 0 %la i y la j recorrerán la matriz mientras se cumpla la %condicion de que sea mayor que cero, entonces rel funciona con los pesos del vector, la i y j recorrerán los datos y pertinentes relaciones con el nodoA y nodoB rel = [rel matrizadya(i,j)]; nodoA = [nodoA i]; nodoB = [nodoB j]; end end end matriz = [nodoA' nodoB' rel']; % lo que se hace es trabajar con la...
tracking img