Informe "Segundo Taller de Algoritmo y Estructuras de Datos II" - GRAFOS -
Introducción
Un
grafo es un conjunto de vértices conectados por medio de aristas. Las aristas
pueden estar direccionadas, en cuyo caso se las denomina arcos, y a las mismas
se les puede asignar un peso que puede representar por ejemplo su longitud o un
tiempo asociado con la misma, etc. Un grafo en el que las aristas están
direccionadas se denomina dígrafo.
En
este breve informe se presentara las distintas aplicaciones de los algoritmos
de grafos.
Aplicación: Algoritmo
de PRIM y KRUSKAL:
Para el desarrollo de
los Algoritmos PRIM y
KRUSKAL,
se utilizó la Teoríade grafos y se aplica en el
modelamiento de problemas de sistemas reales, en el cual los pesos y los costos son
asociados a los arcos del grafo, así tenemos su utilización para resolver:
• En diseño de redes
de transporte, donde los pesos pueden representar distancias asociadas a la
interconexión entre un lugar y otro.
• En diseño de redes
de telecomunicaciones, donde los pesos podrían representar distancias asociadas
a la interconexión entre un par de servidores.
• En sistemas
distribuidos, donde los pesos representarían el tráfico de los sistemas.
• En un mapa de una
línea aérea, donde los arcos del grafo representan las rutas de vuelo y los pesos representan
distancias o tarifas.
• En un circuito
eléctrico, donde los arcos representan los cables y los pesos están asociados a
la longitud de los cables o los costos de los cables.
La solución a cada
uno de los problemas mencionados, consiste en hallar la forma de interrelacionar
todos los vértices del modelo al menor costo, y en el grupo de algoritmos que
solucionan este tipo de problemas tenemos a: PRIM y KRUSKAL.
Estos algoritmos
generan una solución óptima, que es un árbol minimal o
Maximal, que es un
árbol que contiene todos los vértices del grafo, con los arcos cuya suma total
de pesos sea mínima o máxima según corresponda.
Algoritmo de KRUSKAL
Este algoritmo fue
desarrollado por Joseph Bernard Kruskal en 1956, es del tipo ávido o voraz
(greedy). El algoritmo de Kruskal tiene como entrada un grafo conexo con sus
correspondientes pesos en sus arcos y como salida un árbol maximal o minimal,
donde el peso total de las aristas en el árbol es maximizada o minimizada según
corresponda. También es factible aplicarlo sobre grafos no conexos, para lo
cual se aplica el algoritmo a cada componente conexo del grafo que modela el
problema.
Desde un enfoque
sistémico, usando el modelo básico podemos representar a este algoritmo de esta
forma:
PseudoCodigo :
Kruskal(G,w)
A←Ø
para cada vertice v pertenece V[G] hacer
Make-set(v)
O(V)
ordenar las aristas de E por no decrecientes peso w
O(ElogE)
para cada arista (u,v) pertenece E en orden por no decreciente peso hacer
O(E)
si Find-set(u)≠Find-set(v)
entonces
A←A υ
{(u,v)}
union(u,v)
O(V)
return A
Algoritmo de PRIM
Este algoritmo fue
diseñado en 1930 por el matemático Vojtech Jarnik y posteriormente de manera
independiente por el científico computacional RobertC. Primen 1957, y redescubierto por Dijkstra en
1959, razón por la cual muchosautores consideran a este algoritmo como:
algoritmo DJP o algoritmo de Jarnik, es del tipo ávido o voraz (greedy).
El algoritmo de Prim
tiene como entrada un grafo conexo con sus correspondientes pesos en sus arcos
y como salida un árbol maximal o minimal, donde el peso total de las aristas en
el árbol es maximizada o minimizada según corresponda.
También es factible
aplicarlo sobre grafos no conexos, para lo cual se aplica el algoritmo a cada
componente conexo del grafo que modela el problema.
Desde un enfoque
sistémico, usando el modelo básico podemos representar a este algoritmo de esta
forma:
Los grafos constituyen
una herramienta de gran utilidad en la resolución de un sinfín de números de
problemas en una gran variedad de áreas. Por citar sólo algunas de ellas
mencionaremos flujos en redes, árboles genealógicos, emparejamientos,
programación de actividades, análisis de estructuras, resultados de torneos,
coloreado de mapas, análisis lingüísticos, diversos juegos, circuitos
electrónicos,etc. Si bien su uso se remonta a muchos siglos atrás, su
desarrollo actual puede considerarse iniciado con los trabajos de Euler. Es un
área de las matemáticas en la que no existe una nomenclatura generalmente
aceptada, tal vez porque son muchos los autores que han realizado aportaciones
de interés, sin que haya una figura dominante. De hecho, hay todavía numerosos
problemas sin resolver, que se van ampliando a medida que se profundiza en su
estudio. Algunos nombres de matemáticos que han hecho aportaciones importantes,
tanto teóricas o en forma de algoritmos, son Hamilton, Kirchoff, Kónig, Tutte,
Kuratowski, Menge, Verge, Girdle, Djkstra, Ramsey, Eulkerson, fiarari, etc.
Aplicando el
algoritmo de Prim en un problema de la vida real:
Situación:
Implementación del cableado para el
servicio de televisión por cable en ciertos puntos de un sector de la
ciudad de Puno.
Problema:
Ahorrar la mayor cantidad de cable (recursos) en los puntos estratégicos (torres de distribución) para llegar a
todos los destinos deseados.
Datos:
Distancia entre torres y casas es de 10 metros (cada casa)
Planteamiento:
En el figura 3 se observa la ubicación de las torres de distribución y las
viviendas.
Algoritmo de Dijkstra
Su nombre se refiere a Edsger Dijkstra, quien lo describió
por primera vez en 1959.
El
algoritmo de Dijskstra resuelve los problemas de caminos mínimos con pesos de
destino simple en un grafo dirigido G = (V, E) para el caso en el cual todas
las aristas tienen pesos no negativos. Además se debería asumir que ω(u, v) ≥ 0
para cada arista (u, v) ∈
E. El algoritmo de Disjkstra mantiene un conjunto de vértices cuyo camino de
pesos mínimos final desde el inicio (fuente) s se ha determinado. Esto es, para
todos los vértices v ∈
S, donde d[v] = δ(s, v). El algoritmo selecciona repetidamente el vértice u ∈ V −S con la menor estimación de
camino mínimo, inserta u en S y relaja todas las aristas salientes de u. En la
siguiente implementación, mantendremos la cola de prioridades Q que contiene
todos los vértices en V − S, ingresado por sus valores d. La implementación
asume que el grafo G es representado por una lista de adyacencia.
Pseudocódigo:
/*
DIJKSTRA(G,w,s) */
1.
INICIALIZAR-FUENTE-SIMPLE(G,s);
2.
S
= vacio;
3.
Q
= V[G];
4.
Mientras
Q <> vacio;
5.
Hacer u = Extraer-min(Q);
6.
S= S U {u};
7.
Para cada vertice v en Adj[u];
8.
Hacer RELAJAR(u,v,w);
El
algoritmo de Dijkstra relaja todas las aristas. En la línea 1, se realiza la
inicialización respectiva de d y los valores π, en la línea 2 inicializa el
conjunto S como el conjunto vacio. En la línea 3 luego de inicializar la cola
de prioridad Q que contiene todos los vértices en V − S = V − ∅ = V. En cada instante que se produzca
el ciclo MIENTRAS desde la línea 4-8 un vértice u es extraído de Q = V −S e
insertado en el conjunto S (Al inicio del ciclo u = s). El vértice u, por lo
tanto, tiene la más pequeña estimación de camino mínimo de cualquier vértice en
V − S. Entonces, en las líneas 7-8 se relaja cada arista (u, v) que salen de u,
así actualizando la estimación d[v] y el predecesor π[v] si el camino mínimo
hacia v puede ser mejorado al ir a través de u. Observemos que los vértices
nunca son insertados en Q después de la línea 3 y que cada vértice es extraído
de Q e insertado en S exactamente una vez. Así que el ciclo MIENTRAS de las
líneas 4-8 interactúa exactamente | V | veces. Con el siguiente teorema y su
respectivo corolario mostraremos que el algoritmo de Dijkstra calcula caminos
mínimos. La clave está en mostrar que cada vértice u es insertado en el
conjunto S y tener d[u] = δ(s, u).
Comparación entre Grafos
y Graphthing:
Para usar los programas nos informamos
mirando tutoriales en internet…
Tratamos de hacer las mismas consignas en
ambos programas pero nos dimos cuenta que el programa GRAFOS era más
completo... ya que resolvía los problemas que siempre se suelen ver cuando
aprendemos sobre recorrido de grafos , por ejemplo el algoritmo de recorrido
mínimo de Prim, el algoritmo de recorrido de Kruskal y “el problema del
viajante”. Mientras que en el programa GRAPHTHING era más básico permitiéndonos
graficar mejor pero no resolvía todas las consignas como el otro programa
anteriormente mencionado.
Conclusión
La
teoría de grafos es un instrumento utilizado en la aplicación de estos métodos,
permitiéndonos evaluar las relaciones entre los puntos del espacio conectados
por la red desde un punto a otro.
Algunas
de las aportaciones más relevantes de la teoría de grafos como aplicación a la
planificación del transporte consisten en encontrar una relación entre la falta
de conexión al conjunto de la red y las posibles causas de la marginación de
una parte del territorio.
En este estudio podemos observar que el algoritmo de Kruskal
comienza con una Arista, por otro lado, algoritmo de Prim se inicia desde un Nodo
(Vertice), aunque en ambos Algoritmos llegamos a un árbol con el mismo costo mínimo, El recorrido entre vértices pueden llegar a ser diferentes.
Bibliografía
·
http://arodrigu.webs.upv.es/grafos/doku.php?id=algoritmo_kruskal
Comentarios
Publicar un comentario