Diseño y Analisis De Algoritmos

Diseño y Análisis de Algoritmos con Java (I Sem. 2004) GRAFOS

Prof. Dr.Eric Jeltsch F.

Retomando el tema de las metodologías de programación, digamos que existen otras aplicaciones que sirven para ilustrar la metodología Greedy, pero esta vez en grafos, uno de ellos es el método para hallar un árbol expandido mínimo en un grafo no dirigido, Algoritmo de Prim, y Algoritmo de Kruskal, hallarcaminos más cortos en grafos dirigidos y no dirigidos, es el ideado por E. W. Dijkstra. Los tres algoritmos emplean una de las estructuras de datos más frecuentes en este tipo de problemas y que son las cola de prioridad (Heap) para seleccionar la mejor opción actual de entre un conjunto de opciones candidatas. Veamos brevemente una introducción al tema de los grafos para luego concluir con lasaplicaciones antes mencionadas. Grafos es una forma sencilla de expresar digamos que los grafos comprenden de una estructura de datos basada en un conjunto de nodos o vértices V (conjunto de Objetos) y una relación R sobre este conjunto. La conexión entre los nodos se pueden describir facilmente a través de una relación binaria por ejemplo, R ={(1,2),(1,3),(2,4),(2,5),(2,6),(3,5),(3,7),(5,7),(6,7)}. La que representa el grafo G0. 1 G0: 3 2 5 6 7 La siguiente representación muestra el plano de una red de actividades, en donde los nodos del grafo representan el comienzo o el fin de una actividad, descrita por el arco. Lo novedoso de esta representación es que los arcos describen exactamente la duración de la actividad a través de un peso. Entre los nodos existe una relación de orden parcial.Actividad A 50 Dias Tarea B 1 20 Dias 4 25 Dias Test B 2 15 Dias Administración 60 Dias ____________________________________________________________

________ Ingeniería en Computación, Universidad de La Serena
1

4

Corregir faltas 3

Diseño y Análisis de Algoritmos con Java (I Sem. 2004)

Prof. Dr.Eric Jeltsch F.

En general muchos problemas pueden ser resueltos o representados porgrafos, de ahí que las aplicaciones de los grafos sean muy amplias, desde las comunicaciones, redes, descripción de modelos, circuitos lógicos, y otros. La forma de aplicar los grafos en la descripción de problemas, es a
través de nodos, desde el origen (estado inicial) o punto de partida hasta la solución (estado final), pasando por una serie de estados intermedios. En particular, con ayuda delos grafos dirigidos podemos describirlo, en donde, los nodos corresponden a un determinado estado del problema, los arcos corresponden a determinadas operaciones, mientras que la solución queda descrito por un nodo o estado final. En general podemos decir que la solución para un problema cualquiera puede ser siempre representado como un camino a través de un grafo o árbol, el comienzo es la raízdel árbol y se alcanza el origen en la medida que uno llega a las hojas del árbol. Un ejemplo, en este sentido es el Problema del Laberinto. Para analizar mejor este problema, es útil utilizar la representación de árboles: Si se encuentra en un punto arbitrario del laberinto, comprende en teoría que Ud. tiene 4 posibilidades de movidas, arriba (ar), abajo (ab), izquierda (iz) y derecha(de). Estas4-reglas se aplican para determinan las variantes, recorridos o desvíos dentro del laberinto.
1. ir a la derecha 2. en caso de no poder, ir a la izquierda 3. en caso de tampoco funcionar, ir hacia arriba 4. en al caso que tampoco se pueda, ir hacia abajo.

Como podrá imaginarse, no siempre el camino conduce del inicio al final, pues por ejemplo se da la situación de buscar el objetivo (2b), dedonde se tiene,

1

2

3

a

b

c

____________________________________________________________

________ Ingeniería en Computación, Universidad de La Serena

2

Diseño y Análisis de Algoritmos con Java (I Sem. 2004)

Prof. Dr.Eric Jeltsch F.

1a 1b 1c 2c 3c 3b 3a 2a 1a 2b 2a 3a 3b 3c 2c 1c 1b 1a

En este caso, es necesario notar que ya se estuvo una vez en (1a), de...