Buenas, hoy en clase de prácticas con MaGraDa hemos hecho actividades y tambén hemos visto un un poco más el método de Warshall para hallar la matriz de accesibilidad a partir de la matriz de adyacencia.

Esta será por tanto la última entrada que haga en el blog de matemáticas, ha sido un placer

Sesión correspondiente al día (21/12/2010).

Grafo ponderado

Definición y ejemplos

1- Un grafo simple G = (V, A) (grafo simple dirigido, respectivamente) diremos que es un grafo ponderado si tiene asociado una función W: A -> R llamada función de ponderación.

La imagen de cada arista (arco, respectivamente) determinada por los vértices v_i y v_j la llamaremos peso de la arista (arco) y lo denotaremos por w_ij.

2- Sea G = (V, A) un grafo ponderado finito tal que V = {v1, …, vn}. Llamaremos matriz de peso del grafo G a la siguiente matriz de orden n x n

3- En un grafo ponderado llamamos peso de un camino a la suma de los pesos de las aristas (arcos respectivamente) que lo forman.

4- En un grafo ponderado llamamos camino más corto entre dos vértices dados al camino de peso mínimo entre dichos vértices.

5- En un grafo ponderado llamaremos camino más largo o camino crítico entre dos vértices al camino de peso máximo entre dichos vértices.

Como siempre la teoría está muy bien para quien la entienda, aquí va un ejemplo que espero que os ayude más:

EJEMPLO

Caminos  más cortos

Supondremos  que los pesos asociados a los arcos son todos no negativos y que el grafo es dirigido. Supondremos además que los vértices del grafo están numeradores de 1 a n, de forma que w_ij representa el peso del arco (i, j) y que el vértice 1 es el origen del camino. Además u_j denotará el peso del camino más corto de 1 a j.

Dicho de otra forma, vamos a suponer que el peso es siempre positivo y que el grafo es dirigido, además numeraremos los vértices del grafo de 1 a n.

Además debemos saber que cada sección a su vez es el camino más corto que se puede considerar. Esto viene demostrado por el siguiente teorema.

Teorema

Sea 1, …., k, …..,j un camino más corto entre los vértices 1 y j de un grafo ponderado G. Entonces las secciones de este camino 1, …., k y k, …., j son los caminos más cortos entre los vértices respectivos.

Tenemos pues que si tenemos un camino de 1 a 3 pasando por 2, podemos considerar que el camino de 1 a 2 y el camino de 2 a 3 son los caminos más cortos también de las respectivas secciones.

Corolario

Supongamos que en un grafo ponderado tenemos un camino más corto entre los vértices 1 y j. Sea k el vértice inmediatamente anterior a j en ese camino. Entonces la sección de este camino desde 1 a k es el camino más corto entre estos dos vértices. Además se cumple que:

u_j = u_k + w_kj

Con esto y las ecuaciones de Bellman podemos calcular el camino más corto:

Ecuaciones de Bellman

Grafos acíclicos. Método del camino crítico o camino más largo

Un grafo dirigido no tiene circuitos si y sólo si existe una numeración de los vértices para la que se cumple que si (i, j) es un arco del grafo entonces i < j.
Con esta numeración, las ecuaciones de Bellman pueden ser reemplazadas por:

Algoritmo de numeración

Antes de lanzarnos a realizar un problema debemos aprender a numerar los vértices ya que como puse más arriba, es una condición necesaria. Para ordenarlos podemos seguir el siguiente algoritmo de ordenación:

Etapa 1. Inicializar i<-i, V⁽¹⁾= V

Etapa 2. Tomar v E V⁽ⁱ⁾ tal que de(v)=0 en G[Vi].

Etapa 3. Numerar el vértice V como vértice 2

-Hacer V⁽ⁱ⁺¹⁾ = V⁽¹⁾ – {V}

-Hacer i<-i+1

Etapa 4. Si V⁽ⁱ⁾ = ø

Algoritmo de Pert

También es interesante comentar la utilizadad del algoritmo de Pert:

Se denomina camino más largo entre dos vértices dados, al camino de peso máximo entre dichos vértices. Un ejemplo típico de obtención de un camino más largo en un grafo dirigido, es la secuenciación de actividades, también llamada red de actividades.
Así por ejemplo, un proyecto de construcción grande se suele dividir en varias actividades menores; estas actividades están relacionadas, en el sentido de que algunas no pueden comenzar hasta que otras hayan finalizado. Por ejemplo, para la construcción de una casa son necesarios cimientos, muros, carpintería, tejados, instalación eléctrica, … Una actividad como la instalación eléctrica, no puede empezar hasta haber completado otras actividades. La realización de este tipo de proyectos hace necesaria una planificación racional de las actividades a realizar que se denomina PERT (Program Evaluation and Review Technique). Para planificar un proyecto de esta clase podemos representar cada actividad de las que se compone el proyecto por un vértice. En este caso el peso lo tomamos como el tiempo necesario para realizar una actividad, por ello vamos a hacer las actividades que más tiempo requieran y así que puedan hacerse también las que requieran menor tiempo, si lo hacemos al contrario las actividades que requieran más tiempo no podrían realizarse por completo.

Hoy hemos visto los cálculos básicos que se pueden realizar con MaGraDa. Dichos cálculos son:

• Grado: nos diŕa el grado del vértice que toquemos si nos encontramos en el modo gráfico o nos mostrará una gráfica con los grados de cada uno de los vértices si nos encontramos en el modo texto.
• Ver (aristas o arcos): para el modo texto, ya que no se ven ni aristas ni arcos, tenemos esta opción, que nos mostrará una pantalla donde pondrá las aristas (arcos) que van de un vértice a otro.
• Grafo (simple, cíclico, completo y conexo): tanto en modo texto como en modo gráfico podemos comprobar si un grafo es simple, cíclico, completo y conexo. En cualquiera de las opciones anteriores, nos indicará si lo es o no con una explicación.
• Grafo no dirigido asociado: esta opción, si estamos con un grafo dirigido nos creará un grafo con las mismas propiedades pero no dirigido, es decir, se cambian arcos por aristas.

Sesión correspondiente al día (14/12/2010).

CÁLCULO DE COMPONENTES CONEXAS

Diremos que una componente conexa (CC( asociada a un vértice vi es:

Conjunto de vértices a los que alcanza vi:

R(vi)

Y que alcanza a vi:

Q(vi)

CC asociada a vi: R(vi) ∩ Q(vi)

Una componente conexa asociada a un vértice “v” es un conjunto de vértices alcanzables por”v” y que a su vez pueden alcanzar a “v”.

Hay dos procedimientos o métodos para calcular las componentes conexas de un grafo:

Método 1 – Procedimiento del algoritmo

Sea G=(V, A) un grafo dirigido:

Etapa 1. Inicializar i<-1, V⁽¹⁾ = V

Etapa 2. Tomar vi E V⁽ⁱ⁾

Etapa 3. Calcular R(i) ∩ Q(vi)

-Hacer V⁽ⁱ⁺¹⁾ = V⁽ⁱ⁾ ≈ R(vi) ∩ Q(vi)

-Hacer i<-i+1

Etapa 4. Si V⁽ⁱ⁾ = ø entonces STOP

En otro caso, volvemos a la Etapa 2.

EJEMPLO

Vamos a calcular las componentes conexas del siguiente grafo, para ello necesitamos la matriz de accesibilidad y la matriz de acceso que es la traspuesta de la de accesibilidad:

Ahora sigamos el algoritmo paso a paso:

Debemos hacer dos conjuntos, R y Q.

Inicialmente  cogemos todo el conjunto de vértices que tenemos y de ahí cogemos un vértice.

Una vez hecho vamos a la matriz de accesibilidad y buscamos la fila del vértice elegido, entonces vemos columna a columna si hay un uno o un cero, si hay un uno añadimos el vértice al conjunto R. Una vez hecho debemos hacer lo mismo para el conjunto Q pero mirando en la matriz de acceso.

Hacemos i<-1, V⁽¹⁾ = V = {V1, V2, V3, V4, V5}

Tomamos un vértice de V⁽¹⁾ , Por ejemplo V2.

Primera componente conexa: R(V2) ∩ Q(V2)

R(V2) ∩ Q(V2) = {V2, V4} ∩ {V1, V2, V3, V4, V5} = {V2, V4}

V⁽²⁾ = V⁽¹⁾ ≈ R(V2) ∩ Q(V2) = {V1, V3, V5} es decir, restamos a V⁽ⁱ⁾ lo que obtenemos de realizar la intersección entre R(V2) y Q(V2).

Tomamos lo que obtenemos que hemos denominado V⁽²⁾ y elegimos un vértice de dicho conjunto, una vez hecho repetimos el procedimiento que expliqué al principio.

Tomamos un vértice de V⁽²⁾ , por ejemplo, V1.

Segunda componente conexa: R(V1) ∩ Q(V1).

R(V1) ∩ Q(v1) = {V1, V2, V3, V4, V5} ∩ {V1, V3, V5} = {V1, V3, V5}

V⁽³⁾ = V⁽²⁾ ≈ R(V1) ∩ Q(V1) = ø

Hemos obtenido el conjunto vacío, lo que nos indica que hemos terminado, por lo tanto las componentes conexas son las V⁽ⁱ⁾ que hemos obtenido:

{V2, V4}, {V1, V3, V5}

Gráficamente quedaría de la siguiente forma:

Método 2 – Multiplicación de matrices

Este método es fácil de realizar si sabemos multiplicar matrices.

El procedimiento es el siguiente:

-Hayamos la matriz de accesibilidad y la matriz de acceso.

-Multiplicamos ambas matrices término a término, es decir, R1,1 x Q1,1; R1,2 x Q1,2; etc…Esto nos dará la matriz RxQ.

Dentro de la matriz tendremos tantas filas como vértices y tendremos que ir fila a fila y columna a columna viendo si aparece un uno o un cero, si aparece un uno entonces ese vértice de la columna forma parte de una componente conexa. Es posible que aparezcan filas repetidas, esto se debe a que no tenemos por qué tener el mismo número de componentes conexas que de vértices, las filas que se repiten hacen alusión a la misma componente conexa.

RECORRIDO DE ARISTAS

Es interesante averiguar si es posible recorrer un grafo pasando por cada arista una sola vez ya que en grafos complejos no es tan fácil de ver.

Para introducir los siguientes conceptos voy a contar una historia que puso las bases de los grafos.

“Problema de los puentes de Königsberg”: Königsberg era una ciudad que estaba separada en 4 partes y conectadas dichas partes unas con otras por 7 puentes. Pero surgió una pregunta, ¿es posible salir de un punto de la ciudad y, pasando por todos los puentes una única vez, volver al mismo punto?.

Leonhard Euler lo resolvió introduciendo el concepto de grafo euleriano.

Sea G un grafo conexo y en general no simple:

1 – Llamaremos tour de G a una cadena cerrada que atraviesa cada arista de G al menos una vez.

2 – Llamaremos tour euleriano de G a un tour de G que atraviesa cada arista exactamente una vez.

3 – Llamaremos grafo euleriano a aquel en el que podemos encontrar un tour euleriano.

4 – Llamaremos camino euleriano a una cadena (simple) que atraviesa cada arista exactamente una vez.

Para ver si un grafo tiene un tour euleriano (y por lo tanto es un grafo euleriano) o si tiene un camino euleriano tenemos varios argumentos con los que descartar el tour euleriano, el camino euleriano o ambos:

-Para que el grafo pueda tener un tour euleriano, no debe tener vértices de grado impar.

-Para que el grafo pueda tener un camino euleriano, debe tener exactamente dos vértices de grado impar.

La forma de calcular un tour euleriano y un camino euleriano viene dado por el algoritmo de Fleury.

ALGORITMO DE FLEURY

Grafo no dirigido

Para calcular un tour euleriano en un grafo no dirigido partimos de vi y terminamos en vi. Vamos a ir construyendo una cadena simple de forma que no se repitan aristas y que no se elijan aristas de corte a no ser que no haya otra alternativa, estas aristas de corte son aquellas que al quitarlas, dejan vértices aislados. Cada arista que vamos eligiendo y eliminando la añadimos al tour euleriano. Terminaremos cuando hayamos llegado desde vi a vj y no queden aristas.

Para calcular un camino euleriano partimos de un vértice vi de grado impar y llegamos al otro vértice de grado impar. El proceso que seguimos de un vértice al otro es el mismo que para el tour euleriano.

Modificación para grafos dirigidos

El proceso es el mismo, para calcular el tour euleriano debemos tener cuidado y al eliminar arcos no debemos elegir un arco que al eliminarlo aumente el número de componentes conexas del grafo no dirigido asociado, a no ser que no tengamos otra alternativa.

Para calcular el camino euleriano debemos empezar por un vértice de grado impar y terminar en el otro vértice de grado impar, de la misma forma que hacíamos en el grafo no dirigido, para ver si un vértice de un grado dirigido tiene grado impar se puede hacer comprobar que:

de(p) = ds(p)-1,  de(q) = ds(q)+1

Siendo p y q los vértices inicial y final respectivamente del camino.

EJEMPLO

Teniendo el siguiente grafo no dirigido:

Como podemos ver no hay vértices de grado impar, luego puede haber un tour euleriano y no va a haber un camino euleriano.

Empezamos por el V4 por ejemplo, ya que tenemos menos riesgo de quitar una arista de corte, como estamos buscando un tour euleriano sabemos que debemos volver a este vértice al final del tour euleriano.

Quitamos la arista e3 y llegamos al vértice V3, como todo ha sido correcto pues no queda ningún vértice aislado podemos añadir la arista e3 al tour euleriano y seguir con el proceso.

Esto iremos haciéndolo vértice a vértice y arista a arista hasta llegar nuevamente a V4.

Si alguien tiene alguna duda le paso el ejercicio completo, con imágenes de todo el proceso, de todas formas el tour resultante por si alguien lo intenta y quiere ver si lo hizo bien: e3 e4 e10 e9 e7 e1 e5 e8 e6 e2.

CICLO Y CAMINO HAMILTONIANO

Un camino Hamiltoniano en un grafo G es un camino que atraviesa cada vértice del grafo exactamente una vez.

Un ciclo Hamiltoniano en un grafo G es un ciclo que atraviesa cada vértice del grafo exactamente una vez.

Un grafo es Hamiltoniano si existe un ciclo hamiltoniano.

Reglas básicas para construir caminos y ciclos hamiltonianos

Regla 1 – Si G no es conexo, no posee ciclos Hamiltonianos.

Regla 2 – Si G es un grafo con “n” vértices, entonces un camino Hamiltoniano debe tener exactamente n-1 aristas, y un ciclo Hamiltoniano n aristas.

Regla 3 – Si v es un vértice del grafo, entonces un camino Hamiltoniano debe tener al menos una arista incidente con v y como mucho dos.

Regla 4 – Si G es Hamiltoniano, entonces d_G(v) >=2, donde todos los vértices pertenecen a V.

Regla 5 – Si v perteneciente a V tiene grado 2, entonces las dos aristas incidentes con v deben aparecer en cualquier ciclo

Hamiltoniano de G.

Regla 6 – Si v perteneciente a V tiene grado mayor que 2, entonces cuando se intenta construir un ciclo Hamiltoniano, una vez que se pase por v, las aristas no utilizadas incidentes se dejan de tener en cuenta.

Regla 7 – Al construir un ciclo o camino Hamiltoniano para G, no se puede dar el caso de obtener un ciclo para un subgrafo de G a menos que contenta todos los vértices de G.

No podemos calcular si un grafo es Hamiltoniano en estos momentos, ni si tiene ciclos o caminos Hamiltonianos, lo único que podemos hacer es ver si no se cumple alguna de estas reglas y demostrar que NO lo es.

A raiz de todo lo mencionado tenemos el siguiente teorema:

Sea G un grafo dirigido bipartido con partición {X, Y}.

(1) Si G tiene un ciclo Hamiltoniano, entonces card(X) =  card(Y).

(2) Si G tiene un camino Hamiltoniano, entonces card (X) y card(Y) difieren a lo sumo en 1.

El recíproco es cierto para grafos bipartidos completos con más de 2 vértices.

Recordad la lógica de primer orden, que un grafo no sea Hamiltoniano no quiere decir que card(X) != card(Y).