Mate Discretas

matematicas discretas

Capitulo 2: TEORÍA DE GRAFOS

________________________________________

INTRODUCCIÓN

La Teoría de Grafos es parte de Matemáticas Discreta que es una asignatura del plan de estudios de Ingeniería en Informática, que tiene un marcado enfoque práctico, aplicado y computacional, además de un acentuado carácter formativo. El contenido referido a esta temática se plantea como respuesta a una variada serie de problemas de la «vida real» (diseño de bloques, flujo de redes, diseño de circuitos, transporte de viajeros, asignaciones horarias o de tareas, programación, etc.), lo que le confiere el enfoque aplicado que señalamos arriba, aprendiendo el alumno, además, a buscar modelos matemáticos adecuados para gran número de situaciones diferentes, lo que suele ser muy habitual en el desarrollo profesional. El tratamiento que se pretende dar a la asignatura es práctico pues, aparte de la resolución de ejemplos y ejercicios que tiene que desarrollar sobre el papel, se debe dedicar una buena parte de tiempo a realizar prácticas en el computador para resolver algún problema en lo posible concreto (extraído de un caso real).

6.4 Algoritmo para una ruta mas corta

Un algoritmo en una representación grafica s la cual se asigna valores a las aristas y que la longitud de una ruta (camino) en una grafica con pesos es la suma de los pesos de las aristas en una ruta.

Al iluscytar el algoritmo, encerraremos en un círculo los vértices que tienen etiqueta permanente. Mostraremos posterior mente que si L(v) es la longitud de una ruta de A a v. en principio , todos los vértices tienen etiquetas temporales. Cada interacción del algoritmo modifica el estado de una etiqueta, de temporal a permanente; así , podemos concluir el algoritmo cuando Z recibe una etiqueta temporal . en este momento , L(z) proporciona la longitud de una ruta mas corta de A a z.

Este algoritmo determina la longitud de una ruta mas corta del vértice A al vértice Z en una grafica conexa con pesos , el peso de la arista (i,j) es W(i,j) >0 y la etiqueta del vértice x es L (x). Al concluir , L(z) es la longitud de una ruta mas corta de a a z.

ENTRADA: una grafica conexa , con pesos , el la cual todos lo pesos son positivos .los vértices a y z

SALIDA: L (z), la longitud de una ruta mas corta de a a z .

1 procedure dijistra(w,a,z,L)

2 L(a): =0

3 for todos los vértices x =/ a do

4 L(x):=infinito

5 T:=conjunto de todos lo vértices

6 //T es el conjunto de vértices cuya distancia mas corta a A

7 // no ha sido determinada

8 while z E t do

9 begin

10 elegir v E T con L (v) minimo

11 T:=T-(V)

12 for cada x E T adyacente a v do

13 L(x) :=mi {L(x),L(v)+w(v,x)}

14 end

15 end dijikstra

Demostración. Utilizamos la inducción matemática i para demostrar que la i – esima ves que llegamos a la line 10 , L(v) es la longitud de la ruta mas corta de a a v. al demostrar esto , tendremos que el algoritmo es correcto, pues al elegir z en la línea 10 , L(z) la longitud de la ruta mas corta de a a z .

Paso base. (i=l). la primera ves que llegamos a la línea 10 , debido a que los pasos inicialización (líneas 2-4), L(a) es = o y todos lo de mas valores a L son infinitos. A si , ac elige la primera ves que llegamos a la línea 10. Como L (a)=0 , L(a) es la longitud de una ruta mas corta a a hasta a.

Paso inductivo. Supongamos que para toda K <i ,la K-isima v y que elegimos v en T con el valor mínimo L(v) .

Primero mostraremos que si existe un camino de a a un vértice w, cuya longitud sea menos que L(v) , entonces w no esta en T. Sea P una ruta mas corta de a a w, x el vértice mas cercano a A sobre p y que pertenezca a p y u el predecesor de x en p. Entonces u no esta en T , por lo que u fue elegido en la línea 10 durante una iteraccion anterior de ciclo while . Por la ipotecis de inducción , L(u) es la logitud de una ruta mas corta de a a u . Ahora ,

L(x)<_L(u)+w(u,x)<_logitud de p<L(v).

Pero esta desigualdad muestra que v no es el vértice en T con L (v) minimo { L(x)<}.Esta contradicion concluye la demostración de que si existe una ruta de a a un vértice w cuya longitud se a menor que L(v) , entonces w no esta en T.

6.5 REPRESENTACIONES DE GRAFICAS

Puede representarse por un diagrama de la siguiente manera. Los elementos de x se representan por puntos(geométricos) dispuestos de modo completamente arblitario.

Las condiciones de representara diferentes maneras, dependiendo de que le grafico sea orientado

A) Si es relevante para la representación determina cual es el vértice origen y cual el destino , la sconexionces entre vértices se representan mediandte flechas (denominadas arcos) : tendremos entonces un grafo orientado.Se traza una flecha de x a y y si y solo si (x,y) E V

.

B) Si no es relevante determinar el sentido de la relación entre vértices, tenf¿dremos un grafo no orientado: los vértices se unirán mediante segmentos, denominados aristas.

Matriz asociada a un grafo

El principio en el eque nos basamos para realizar una matriz asociada a un grafo es idéntico a asociar una tabla a una relación.

Si G tiene n =|X| puntos formamos una matriz (o tabla) de n filas y n columnas. Cada uno de los componentes de la matriz representa una posibilidad de conexión

A la i-esima fila asociamos el punto Xi EX: a la j-esima columna. El punto Xj E X. cada punto esta asociado a una fila y a una columna. Los elementos de la matriz se pueden denotar por gij= 1

Si (Xi.Xj) E V o gij =0 si (Xi.Xj) E/ V. con esto tenemos representados por unos las conexiones existentes. Y por ceros la ausencia de conexión.

Nos referimos a la matriz asociada al grafico G con la notación ||G||. Por lo tanto una matriz ||G|| de nxn expresara que n es el numero de vértices.

Una

...