DISCRETAS TERMINADO








ESCUELA SUPERIOR POLITÉCNICA DEL LITORAL
PROYECTO DE MATEMÁTICAS DISCRETAS

ALGORITMO DE RIGUET


Autores:
Condoy Kerly
Rueda Aaron
Santana Allisson

Tutor:
Ing. Edgar Johni Bustamante Romero


GUAYAQUIL-ECUADOR
2016


TEORÍA DE GRAFOS

Llamaremos grafo a un par formado por un conjunto de puntos (llamados vértices o nodos) y un conjunto de relaciones orientadas entre ellos oflechas que los unen (arcos o aristas).
Al decir orientadas nos referimos a que usualmente esas flechas deben indicar en qué sentido van, de forma que si no lo indican supondremos que pueden ir en los dos sentidos.



Formalmente, podemos definir un grafo G, lo notaremos como G=(V,E) como el par constituido por un conjunto finito V cuyos elementos se denominan vértices y subconjunto E del productocartesiano VxV cuyos elementos llamamos arcos.
Cuando V es finito, con n elementos, diremos que el grafo es finito de orden n.


ALGUNAS DEFINICIONES
Al número de vértices en el grafo (número de elementos de V), lo llamaremos orden de grado G. Usualmente los vértices se enumeran, 1,2,3…
Dado un arco (a,b) llamaremos extremo inicial a a y extremo final a b. Si a coincide con b, diremos que es un lazo.Los arcos de (a,b) y (b,a) diremos que son simétricos.
Dos vértices son adyacentes si existe un arco que los une.
Un vértice b es sucesor del vértice a si existe un arco de a a b. Similarmente, se dice que a es predecesor de b.
Llamaremos grado de un vértice al número de arcos que terminan en él. Cuando todos los vértices de un grafo tengan el mismo grado, diremos que el grafo es regular.
Diremosque un grafo es simétrico cuando todos los arcos poseen su simétrico y antisimétrico cuando los vértices adyacentes solo lo son en un sentido, no pueden tener lazos.
Diremos que un grafo es completo si todos sus vértices están relacionados, es decir, dos vértices cualesquiera son adyacentes.
Por último, llamaremos grafo simple aquel que cumple que no contiene lazo y que solo hay una arista que unea cada dos vértices.

CONCEPTO DE CAMINO: OBTENCIÓN DEL CAMINO MÁS CORTO
Llamaremos camino o cadena entre dos vértices a una secuencia de arcos de forma que el final de uno es el origen del siguiente. Dado un camino, llamaremos origen del camino al origen del primer arco y final del camino al final del último arco.
Diremos que un camino es simple si no contiene más de una vez a cualquier arco. Encaso contrario, se denomina compuesto. Mientras no se diga lo contrario, trabajaremos con caminos simples.
Dado un camino simple C de un grafo, llamamos longitud del camino, y lo notamos 1(C), al número de arcos que lo definen, o lo que es lo mismo, al número de vértices menos uno.
Llamaremos circuito (o ciclo) a un camino que solo coinciden los vértices inicial y final.
Por último, diremos queun grafo es conexo si de un vértice a otro cualquiera existe al menos un camino.

ALGORITMO DE RIGUET
Es un algoritmo que nos proporciona todos los caminos existentes entre dos vértices; nosotros queremos encontrar el camino mínimo entre un vértice de salida, Vs y otro final, Vf. Una vez obtenidos estos, nos bastará con sumar los valores asignados a cada arco, con lo que obtenemos la longitud decada camino y quedarnos con aquel cuya longitud es mínima.
En este método se construye un arborescencia cuya raíz es nuestro nodo inicial, Vs. Las ramas se van formando colgando de cada vértice Vi todos los vértices a los que se puede llegar desde este vértice y así sucesivamente hasta que llegamos al vértice final, Vf, o no podemos continuar por esa rama. Luego nos bastará quedarnos con las ramasque acaban en nuestro nodo final.







EJEMPLO

Dado el siguiente grafo:












Obtener el camino más corto del nodo 1 al 5, usando el algoritmo de Riguet.

SOLUCIÓN:

El algoritmo de Riguet construye una arborescencia dese nuestro nodo inicial, en este caso el vértice 1, y se queda con todas las ramas que acaban en el nodo final, el vértice 5.

De estás escoge la que tenga longitud...