Manual algoritmo de prim

Solo disponible en BuenasTareas
  • Páginas : 4 (772 palabras )
  • Descarga(s) : 0
  • Publicado : 23 de mayo de 2011
Leer documento completo
Vista previa del texto
MANUAL 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 notiene ninguno. También podemos definir un árbol como:
        o Un grafo conexo y sin ciclos.
        o Un grafo sin ciclos y con n-1 aristas, siendo n el número de vértices.
[pic]
    •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 y v6).
    •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 sus aristases mínima.
    • Algoritmo de prim: El algoritmo de prim permite hallar el árbol minimal de cualquier grafo valorado (con capacidades). Hay que seguir los siguientes pasos:
        1. Semarca la 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 deellas.
        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 lasaristas marcadas, es decir, cuando tenemos marcados n-1 arcos, siendo n el número de nodos del grafo.

Matriz = input('digite la matriz recuerde que debe ser una matriz simétrica:')

ifnorm(Matriz-Matriz','fro') ~= 0 ,
disp(‘arreglar la matriz, recuerde debe ser simétrica’)
return,
end;

% valores iniciales
nodGra = [2:length(Matriz)];
nodArb = [1];
ariArb =[0];
adyArb = zeros(size(Matriz));

% ver el grafo , ShowWeights esta encendido así que muestra el valor de las artistas, y ShowArrows esta apagado ya que no es dirigido el grafo.

h =...
tracking img