Árbol de máximo Alcance y mínima Expansión

Objetivo: Construir un árbol que conecte todos los nodos de la red con un costo total mínimo o con utilidades máximas.

Importancia

1)    Lo que realmente se minimiza es la longitud del árbol obtenido. No se minimiza el número de arcos.

2)    Hay varios problemas en los que se desea minimizar la interconexión de varios puntos. Por ejemplo en la confección de circuitos impresos.

3)    El problema consiste en minimizar la suma de todas las longitudes (los pesos) de los arcos que interconectan todos los nodos de un grafo no dirigido.

4)    En caso de requerir maximizar utilidades se usan el mismo procedimiento lo único que se buscan lo mayores valores.

Términos

Árbol: Es un diagrama,  desde un único nodo  se puede acceder a todos los demás y cada nodo tiene un único predecesor, excepto el primero, que no tiene ninguno. Otras definiciones de árbol como:

  • Un esquema conexo y sin ciclos.
  • Un diagrama de 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).

Hojas en un árbol a los nodos finales (v3, v5 y v6).

Árbol de máximo alcance es aquel que obtenemos en un esquema 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 accede encontrar el árbol mínima de cualquier esquema valorado (con capacidades). Sus pasos son:

  1. Marcar la arista con menor valor. Si hay más de una, se elige cualquiera al azar.
  2. De las aristas restantes, se busca la que tenga menor valor, si hay más de una, se opta por cualquiera de ellas.
  3. Repetir el paso 2 siempre que la arista preferida no cree un ciclo con las ya marcadas.
  4. Finaliza el proceso cuando  todos los nodos del esquema están marcadas menos uno. Es decir, cuando tenemos marcados n-1 arcos, siendo n el número de nodos del diagrama

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

Red del problema ha realizar

Siguiendo el algoritmo de Kruskal, tenemos:

  • Se elije  la arista (5, 6) = 1 (menor valor) y se marca
  • Elegir  siguiente arista con menor valor (1, 3) = 1 y marcar
  • Elegir arista con menor valor (5, 7) = 2 y  marcar, porque no forma ciclos con ninguna arista de las marcadas anteriormente.
  • Elegir la siguiente arista con menor valor (1, 2) = 3 y  marcar, no forma ciclos con ninguna arista de las marcadas anteriormente.
  • Elegir la siguiente arista con menor valor (6, 7) = 4 y se desecha, ya que forma ciclos con las aristas (5, 7) y (5, 6) marcadas anteriormente.
  • Elegir la siguiente arista con menor valor (2, 5) = 5 y marcar, No forma ciclos con ninguna arista de las marcadas anteriormente.
  • Elegir la siguiente arista con menor valor (4, 5) = 6 y marcar, ya que no forma ciclos con ninguna arista de las marcadas anteriormente.
  • FIN. Se Finaliza dado que los 7 nodos del esquema están en alguna de las aristas, o también porque tenemos marcadas 6 aristas (n-1).
  • Por tanto el árbol de mínima expansión resultante sería:

Respuesta del primer algoritmo

 

ALGORITMO DE PRIM

El algoritmo de Prim permite hallar el árbol mínimo de cualquier diagrama 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 diagrama

Red del problema ha realizar

Siguiendo el algoritmo de Prim:

  1. Elegir, por ejemplo, el nodo 1 y marcar.
  2. Elegir la arista con menor valor incidente en 1, la (1, 3) = 1 se  señala. Marcar el otro nodo en el que incide, el 3.
  3. Elegir la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (1, 2) = 3 señalar y marcar el nodo no marcado, el 2.
  4. Elegir la arista con menor valor incidente en un nodo señalado y otro que no lo esté, la (2, 5) = 5 se  indica y marcar el nodo no marcado, el 5.
  5. Elegir  la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 6) = 1 se señala y marcar el nodo no marcado, el 6.
  6. Elegir la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 7) = 2  marcar e indicar el nodo no marcado, el 7.
  7. Elegir la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 4) = 6 se señala y marcar el nodo no marcado, el 4.
  8. FIN. Es el fin dado que se tiene marcado los 7 nodos del diagrama.

Por tanto el árbol de mínima expansión resultante sería:

Respuesta del segundo algoritmoAhora resuelva los siguientes problemas:

Problema 1: En la fProblema 1 de arbol de comunicaciónigura se ven las distancias, en millas, de las conexiones
factibles que unen nueve pozos marinos de gas natural con un punto de
entrega en tierra. Como la ubicación del pozo 1 es la más cercana a la
costa, tiene capacidad de bombeo y de almacenamiento suficiente para
bombear la producción de los ocho pozos restantes hasta el punto de
entrega. Determine la red mínima de tubería que una las bocas de pozo
con el punto de entrega

Diagrama de problema 2Problema 2:  Cablediversión está en el proceso de proporcionar servicio de cable a cinco nuevas áreas habitacionales. La figura representa los enlaces posibles de TV entre las cinco áreas. Las millas de cable se muestran en cada arco. Determine la red de cable más económica.

pensamientos-frases-motivacion-superacion-exito-45

About these ads

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