Transcript
Page 1: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

Teoria de grafos.-clase 4

Grafos Eulerianos

Y

Grafos Hamiltonianos

Page 2: 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

Page 3: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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

Page 4: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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

Page 5: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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.

Page 6: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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.

Page 7: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

v1

v6

v4

v3v5

v2

Ejemplo1:

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

Page 8: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

v1

v6

v4

v3v5

v2

Ejemplo1:

v1-v2

Page 9: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

v1

v6

v4

v3v5

v2

Ejemplo1:

v1-v2-v3

Page 10: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

v1

v6

v4

v3v5

v2

Ejemplo1:

v1-v2-v3-v4

Page 11: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

v1

v6

v4

v3v5

v2

Ejemplo1:

v1-v2-v3-v4-v5

Page 12: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

v1

v6

v4

v3v5

v2

Ejemplo1:

v1-v2-v3-v4-v5-v6

Page 13: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

v1

v6

v4

v3v5

v2

Ejemplo1:

v1-v2-v3-v4-v5-v6

Page 14: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

v1

v6

v4

v3v5

v2

Ejemplo1:

v1-v2-v3-v4-v5-v6

v3-v5

Page 15: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

v1

v6

v4

v3v5

v2

Ejemplo1:

v1-v2-v3-v4-v5-v6

v3-v5-v6

Page 16: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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

Page 17: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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

v2 v6

v5

v4

v7

v1

v3

Page 18: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

Ejemplo2:

v2 v6

v5

v4

v7

v1

v3

v1-v4-v6-v2-v5-v1

Page 19: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

Ejemplo2:

v2 v6

v5

v4

v7

v1

v3

v1-v4-v6-v2-v5-v1

Page 20: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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

Page 21: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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.

Page 22: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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.

Page 23: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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.

Page 24: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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.

Page 25: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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.

Page 26: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

u1

u2

u5

u6

u3

u4

u7

u8

Ejemplo1:

Page 27: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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

Page 28: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

Ejemplo2:

B

EF

G

AD

C

7

9

2

6

8

7

4

1

12

5

Page 29: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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

Page 30: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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

Page 31: Teoria de grafos.-clase 4 Grafos Eulerianos Y 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.

Page 32: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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

Page 33: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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.

Page 34: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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

Page 35: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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.

Page 36: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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

Page 37: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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.

Page 38: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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.

Page 39: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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.

Page 40: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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

Page 41: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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

Page 42: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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

Page 43: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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

Page 44: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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

Page 45: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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

Page 46: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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

Page 47: Teoria de grafos.-clase 4 Grafos Eulerianos Y Grafos Hamiltonianos

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)


Top Related