teoria de grafos.-clase 4 grafos eulerianos y grafos hamiltonianos

Teoria de grafos.-clase 4

Grafos Eulerianos

Y

Grafos Hamiltonianos

El problema de los puentes de Konigsberg

A

B

C

D

A tiene que aparecer al menos 3 vecesB tiene que aparecer al menos 2 vecesC tiene que aparecer al menos 2 vecesD tiene que aparecer al menos 2 veces

Se necesitarían 9 letras Por tanto no existe ningún recorrido

Definición: Un circuito es un recorrido con el mismo origen y final.Un circuito euleriano de un multi - grafo conexo G es un circuito que contiene todas las aristas de G.Un grafo G con un circuito euleriano se denomina un grafo euleriano.

u2

u9

u6

u4

u3

u5

u7

u1

u8

u1– u2–u8-u9-u2-u3-u4-u2-u7-u4-u5-u6-u7-u1

Otra posibilidad:u1-u2-u7-u4-u2-u8-u9-u2-u3-u4-u5-u6-u7-u1

u1 u2

u5u7 u6

u8 u9 u2 u3 u4

u4 u7 u2

Definición: Un recorrido es una cadena sin aristas repetidas (se pueden repetir vértices). Un recorrido euleriano de un multi - grafo conexo G es un recorrido que contiene todas las aristas de G.

v1

v2

v6

v5

v3

v4

v1–v2-v4-v3-v2-v6-v5-v4

Otra opción:v1-v2-v3-v4-v2-v6-v5-v4

Teorema: Un multigrafo conexo G es euleriano si y solo si el grado de cada vérticees par.

Si G es euleriano entonces todos los vértices tienen grado par.

si todos los vértices tienen grado par entonces G es euleriano.

Entonces contiene un circuito euleriano que empieza y acaba en un vértice v. Cada vez que aparece un vértice u ≠ v en el circuito , se añade dos a su grado. Yaque por una arista se accede y por otra se sale.Lo mismo ocurre con v, excepto para la primera y ultima aparición que añaden 1.

Suponemos que todos los vértices tienen grado par y construimos el circuito euleriano T.Elegimos un vértice v y empezamos un recorrido hasta que llegamos a un vértice que ya no tiene aristas que no hayamos usado. Entonces cuando esto pasa, este vértice esv. ¿Por qué?

Antes de llegar a w por ultima vez, cada vez que hemos pasado por el hemos restado dos grados: el de la arista de entra y el de la arista de salida. Cuando accedemos a wpor ultima vez, hemos usado un numero impar de aristas. Si este vértice w no fuese v debería tener otra arista que no hemos usado porque si no tendría grado impar. Esto contradeciría la hipótesis de que no tiene mas aristas que no han sido usadas.Entonces, T es un circuito.

si todos los vértices tienen grado par entonces G es euleriano. (continuación)

Si T ha usado todas las aristas es un circuito euleriano.

Si no se han usado todas las aristas y como G es conexo, existe algún vértice v de Tque tiene aristas que no han sido usadas. (Si no el resto de los vértices no usados no estarían conectados a los de T)

Sea H el grafo que se obtiene de G eliminando las aristas del circuito T. Por el mismo razonamiento anterior, podemos encontrar un circuito T’ que comience en v. Este circuito se puede insertar en T de forma que tengamos un circuito T1 quecontiene las aristas de ambos circuitos.

Si este circuito ha usado todas las aristas de G seria un circuito euleriano.Si no vamos repitiendo el proceso hasta que en algún momento se hayan usado todas las aristas.

v1

v6

v4

v3v5

v2

Ejemplo1:

-Es conexo.-Todos los vértices tienen grado par.Entonces existe un circuito euleriano.

v1

v6

v4

v3v5

v2

Ejemplo1:

v1-v2

v1

v6

v4

v3v5

v2

Ejemplo1:

v1-v2-v3

v1

v6

v4

v3v5

v2

Ejemplo1:

v1-v2-v3-v4

v1

v6

v4

v3v5

v2

Ejemplo1:

v1-v2-v3-v4-v5

v1

v6

v4

v3v5

v2

Ejemplo1:

v1-v2-v3-v4-v5-v6

v1

v6

v4

v3v5

v2

Ejemplo1:

v1-v2-v3-v4-v5-v6

v1

v6

v4

v3v5

v2

Ejemplo1:

v1-v2-v3-v4-v5-v6

v3-v5

v1

v6

v4

v3v5

v2

Ejemplo1:

v1-v2-v3-v4-v5-v6

v3-v5-v6

v1

v6

v4

v3v5

v2

Ejemplo1:

v1-v2-v3-v4-v5-v6

v3-v5-v6-v3

v1-v2-v3-v5-v6-v3-v4-v5-v6

Ejemplo2:-Es conexo.-Todos los vértices tienen grado par.Entonces existe un circuito euleriano.

v2 v6

v5

v4

v7

v1

v3

Ejemplo2:

v2 v6

v5

v4

v7

v1

v3

v1-v4-v6-v2-v5-v1

Ejemplo2:

v2 v6

v5

v4

v7

v1

v3

v1-v4-v6-v2-v5-v1

Ejemplo2:

v2 v6

v5

v4

v7

v1

v3

v1-v4-v6-v2-v5-v1

v2-v7-v6-v5-v7-v3-v4-v2

v1-v4-v6-v2-v7-v6-v5-v7-v3-v4-v2- v5-v1

Teorema: Sea G un multigrafo conexo no trivial. Entonces G contiene un recorrido euleriano si y solo si tiene dos vértices de grado impar. Además, el recorrido empieza en uno de ellos y acaba en el otro.

Sea G un grafo con únicamente dos vértices impares u y v. Sea H el grafo que se obtiene añadiendo un vértice z que no pertenece a G y las aristas uz y vz. Entonces como H es conexo y todos los vértices tienen grado par existe un circuito euleriano:

u1 u2 u3 u z v un-1 un

u1 u2 u3 u v un-1 un

Entonces:

Es un recorrido euleriano.

Teorema: Un grafo conexo G es euleriano si y solo si toda arista de G se encuentra en un número impar de ciclos de G.

La demostración puede encontrase en:G. Chartrand, “ Applied and algorithmic graph theory”sección 7.2, página 212.

Aplicación de grafos eulerianos: El problema del cartero chino.

- Un cartero quiere repartir las cartas con el menor coste posible.- Debe recorrer todas las calles que tiene asignadas- Debe empezar en la oficina de correos y acabar en la oficina de correos.

Objetivo: Encontrar la cadena cerrada mas corta posible que recorre todas las aristas.Esta cadena se denomina cadena euleriana.

Las calles pueden ser representadas por aristas.Las intersecciones son los vértices.El problema tiene solución porque si doblamos las aristas para crear un multigrafoTodos los vértices tendrían grado par.

Sea V0(G)={u1, u2, …., u2n} el conjunto de vértices de grado impar de G.Recordamos que son un numero par.

Definimos una partición emparejada de Vo(G) como una partición de Vo(G) en n conjuntos de dos elementos:

Π={ {u11, u12}, {u21, u22}, … , {un1,un2} }

Se define la distancia de la partición emparejada comod(Π)= ∑ d (ui1,ui2)

Y m(G)= min ( d(Π) ).

Teorema: Si G es un grafo conexo de tamaño q, entonces una cadena euleriana de G tiene longitud q+m (G).

El camino euleriano se obtendría duplicando únicamente las aristas de los caminos quevan de ui1 a ui2.

El teorema anterior es muy costoso ya que necesita evaluar todas las particiones.Una forma mas eficiente consiste en:

1.- Crear un grafo completo usando los vértices impares.2.- Los pesos de las aristas corresponden a las distancias entre vértices.(Moore).3.- Se escoge la partición mínima de este grafo.

u1

u2

u5

u6

u3

u4

u7

u8

Ejemplo1:

u1

u2

u5

u6

u3

u4

u7

u8

Ejemplo1:

(1)

(3)

(1)

(2)

(4)

(2)

(2)

(3)

u4 u8

u1 u21

3

43

2

3

d {u1 u2}{u4u8}=1+3=4d {u1 u4}{u2 u8}=3+3=6d {u1 u8}{u2 u4}=4+2=6

Ejemplo2:

B

EF

G

AD

C

7

9

2

6

8

7

4

1

12

5

Ejemplo2:

B

EF

G

AD

C

7

9

2

6

8

7

4

1

12

5 F E

B G6

9

71

8

9

d {BG}{FE}=6+9=15d {BE}{GF}=7+8=15d {BF}{GE}=9+1=10

Definición: Un grafo G se dice que es Hamiltoniano si tiene un ciclo recubridor. Es decir, un ciclo que pasa por cada vértice una sola vez.

Grafos Hamiltonianos

Ningún grafo conexo con vértices de corte es Hamiltoniano:

Teorema. Si un Grafo G es Hamiltoniano, entoncesK (G-S) ≤ | S |

Para todo subconjunto propio no vacío S de V (G).

Sea G un grafo Hamiltoniano y sea C un ciclo Hamiltoniano. Sea n el numerode componentes de G-S: G1, G2, … , G n. Sea ui el ultimo vértice de Gi i sea vi el vértice que inmediatamente sigue a ui en C. Entonces vi pertenece a S y hay tantosvértices en S como componentes en G-S.

Observar que este teorema sirve para probar que un grafo es no Hamiltoniano. PeroPodría habar algunos grafos no Hamiltonianos que tienen esta propiedad.!!!!!!!!

El Grafo de Petersen.

Definición: Un camino Hamiltoniano de un grafo G es un camino recubridor de G

Teorema de Dirac: Sea G un grafo de orden p ≥3 . Si el grado de cada vértice v es mayor o igual que p/2. Entonces G es Hamiltoniano. ( Kp son Hamiltonianos)

1.- Sea P el camino mas largo que se puede encontrar.

v1 v2 v3 v4 Vn-2 vn-1 vn

Entonces todos los vecinos de v1 y vn ya han sido usados ya que si no se podría hacer la cadena mas larga. Esta cadena tiene longitud al menos p/2 +1 (los vecinosde v1 mas el v1).

2.- Existe un vértice vi , 2 ≤ i ≤ n, que es adyacente a v1 y que vi-1 es adyacente a vn.

v1 v2 vi-1 vi Vn-2 vn-1 vn

Si esto no fuera así, como todos los vecinos de v1 han sido usados y el anterior no es adyacente a vn, existirían p/2 vértices distintos de vn que no son adyacentes. Pero

grado ( vn ) ≤ (p-1)-p/2 < p/2 que contradeciría la hipótesis de grado(vn) ≥ p/2.

3.- Hemos visto que existe un ciclo C. Veamos que este ciclo contiene todos los vértices.

Si no contuviese todos los vértices, existiría algún vértice u que no pertenece a C.Este vértice tiene grado mayor que p/2.En 1.- vimos que la cadena tenia longitud mayor que 1 +p/2.Entonces u seria adyacente a algún vértice de C.Pero u unido a C formaría una cadena mas larga que la inicial, lo cual es absurdo.Por tanto C contienen todo los vértices y G es Hamiltoniano.

u

Consecuencia: Sea G un grafo de orden p. Si grado v es mayor que (p-1)/2 para todo v.Entonces G contiene un camino Hamiltoniano

Sea v un vértice que no pertenece a G. Sea H el grafo que se obtiene a unir v con todos los vértices de G.Entonces H tiene orden p +1 y v tiene grado p.Además el grado de los vértices u de G

grado (u) = grado (u)+1 ≥ (p-1)/2 +1 = (p+1)/2.

Entonces aplicando el teorema de Dirac que H contiene un ciclo Hamiltoniano. Eliminando el vértice u de C tendríamos el camino Hamiltoniano.

Teorema: Sea G un grafo de orden p ≥ 3. Supongamos que u y v son vértices no adyacentes de G tales que

grado u + grado v ≥ pEntonces G es Hamiltoniano si y solo si G+uv es Hamiltoniano

Definición: Se define la clausura c(G) de un grafo G de orden p como el grafo obtenido de G uniendo recursivamente pares de vértices no adyacentes cuya suma es al menos p hasta que no queden mas pares con esta propiedad.

La clausura es única.

Teorema: Sea G un grafo de orden p. Sean G1 y G2 son grafos obtenidos de G uniendo pares de vértices cuya suma de sus grados es al menos p. Entonces G1=G2.

Sean e1, e2,…, em y f1, f2, …, fn las aristas añadidas para obtener G1 y G2.

Supongamos que existiese una arista e k +1 =uv que pertenece a G1 y no a G2.

Sea H el subgrafo formado por las aristas comunes hasta llegar a ek+1. Es decirH= G+{e1, e2, …, ek}.

Entonces H es un subgrafo de G1 y G2.Por tanto

Grado G2 u +grado G2 v ≥ grado H u +grado H v ≥ p

Lo cual seria una contradicción ya que dijimos que uv no pertenece a G2.

Basta aplicar el teorema que vimos que afirma que G es Hamiltoniano si ysolo si G+uv es Hamiltoniano.

Teorema: Un grafo es Hamiltoniano si y solo si su clausura es Hamiltoniana.

Consecuencia: Sea G un grafo de orden p . Si la clausura de G es isomorfa a Kp

entonces G es Hamiltoniano.

Consecuencia del Teorema anterior y del Teorema de Dirac.

Consecuencia. Sea G un grafo de orden p ≥ 3. Si grado (u) +grado (v) ≥ p.Para todo par u, v de vértices no adyacentes de G entonces es Hamiltoniano.

Basta observar que la clausura seria completa.

Aplicación de los gráficos Hamiltonianos: El problema del Vendedor.

Un vendedor quiere vender su producto en varias ciudades.Las ciudades estan representadas por vertices.El coste para ir de una ciudad a otra por las aristas.Se puede suponer que el grafo es completo.

Algoritmo que encuentra una solución de bajo coste (no necesariamente la mínima)

1.- n=12.- Selecciona cualquier vértice v de G. C1=v v Mientras n< p

- Encuentra un vértice vn que no este en Cn y que unvn sea mínimo siendo un pertenece a Cn

-Adjuntar vn inmediatamente antes que un

-n=n+1

0 3 3 2 7 33 0 3 4 5 53 3 0 1 4 42 4 1 0 5 57 5 4 5 0 43 5 4 5 4 0

Ejemplo:

v1 v3 v4 v2 v6 v1

0 3 3 2 7 33 0 3 4 5 53 3 0 1 4 42 4 1 0 5 57 5 4 5 0 43 5 4 5 4 0

Ejemplo:

v1

0 3 3 2 7 33 0 3 4 5 53 3 0 1 4 42 4 1 0 5 57 5 4 5 0 43 5 4 5 4 0

Ejemplo:

v1 v4 v1

0 3 3 2 7 33 0 3 4 5 53 3 0 1 4 42 4 1 0 5 57 5 4 5 0 43 5 4 5 4 0

Ejemplo:

v1 v3 v4 v1

0 3 3 2 7 33 0 3 4 5 53 3 0 1 4 42 4 1 0 5 57 5 4 5 0 43 5 4 5 4 0

Ejemplo:

v1 v3 v4 v2 v1

0 3 3 2 7 33 0 3 4 5 53 3 0 1 4 42 4 1 0 5 57 5 4 5 0 43 5 4 5 4 0

Ejemplo:

v1 v3 v4 v2 v6 v1

0 3 3 2 7 33 0 3 4 5 53 3 0 1 4 42 4 1 0 5 57 5 4 5 0 43 5 4 5 4 0

Ejemplo:

v1 v5 v3 v4 v2 v6 v1

Coste 26 (El mínimo que se podía encontrar inicializandocon otro vértice seria 21)