INVESTIGACION DE OPERACIONES

Just another WordPress.com weblog

2.3 Problema Árbol Expandido Mínimo abril 9, 2010

  • Á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úmero de 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 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 aristas 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 marca 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 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, es decir, 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 arista con 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 que no forma ciclos con ninguna arista de las marcadas anteriormente.
  • Elegimos la siguiente arista con menor valor (6, 7) = 4 y la desechamos, ya que forma ciclos con las aristas (5, 7) y (5, 6) marcadas anteriormente.
  • Elegimos la siguiente arista con menor valor (2, 5) = 5 y la marcamos, ya que no forma ciclos con ninguna arista de las marcadas anteriormente.
  • Elegimos la siguiente arista con menor valor (4, 5) = 6 y la marcamos, ya que no forma ciclos con ninguna arista de las marcadas anteriormente.
  • FIN. Finalizamos dado que los 7 nodos del grafo están en alguna de las aristas, o también ya que tenemos marcadas 6 aristas (n-1).
  • Por tanto el árbol de mínima expansión resultante sería:

 

  

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. Se marca un nodo cualquiera, será el nodo de partida.
  2. Seleccionamos la arista de menor valor incidente en el nodo marcado anteriormente, y marcamos el otro nodo en el que incide.
  3. Repetir el paso 2 siempre que la arista elegida enlace un nodo marcado y otro que no lo esté.
  4. El proceso termina cuando tenemos todos los nodos del grafo marcados.

Ejemplo: Determinar el árbol de mínima expansión para el siguiente grafo:

 

 

 

Siguiendo el algoritmo de Prim, tenemos:

  • Elegimos, por ejemplo, el nodo 1 y lo marcamos.
  • Elegimos la arista con menor valor incidente en 1, la (1, 3) = 1 la marcamos y marcamos el otro nodo en el que incide, el 3.
  • Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (1, 2) = 3 la marcamos y marcamos el nodo no marcado, el 2.
  • Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (2, 5) = 5 la marcamos y marcamos el nodo no marcado, el 5.
  • Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 6) = 1 la marcamos y marcamos el nodo no marcado, el 6.
  • Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 7) = 2 la marcamos y marcamos el nodo no marcado, el 7.
  • Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 4) = 6 la marcamos y marcamos el nodo no marcado, el 4.
  • FIN. Finalizamos dado que tenemos marcados los 7 nodos del grafo.
  • Por tanto el árbol de mínima expansión resultante sería:

 

VIDEO DEL METODO DEL ÁRBOL

  

 

Tema 2.4: Problema de Flujo Máximo

 

2 Responses to “2.3 Problema Árbol Expandido Mínimo”

  1. Claudio Dice:

    exelente trabajo, gracias por compartirlo…

  2. angel Dice:

    realmente el mejor trabajo de estos dos algoritmos, gracias me hiciste un parote, solo una observación, en la arista (2,4), falta un numero supongo que tiene que ser mayor a 9, gracias bye.


Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

 
Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.