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

  • Published on
    28-Jan-2016

  • View
    231

  • Download
    8

Embed Size (px)

Transcript

  • Teoria de grafos.-clase 4Grafos Eulerianos YGrafos Hamiltonianos

  • El problema de los puentes de KonigsbergA 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

  • Definicin: 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.u1 u2u8-u9-u2-u3-u4-u2-u7-u4-u5-u6-u7-u1Otra posibilidad:u1-u2-u7-u4-u2-u8-u9-u2-u3-u4-u5-u6-u7-u1

  • Definicin: Un recorrido es una cadena sin aristas repetidas (se pueden repetir vrtices). Un recorrido euleriano de un multi - grafo conexo G es un recorrido que contiene todas las aristas de G.v1v2v6v5v3v4v1v2-v4-v3-v2-v6-v5-v4Otra opcin:v1-v2-v3-v4-v2-v6-v5-v4

  • Entonces contiene un circuito euleriano que empieza y acaba en un vrtice v. Cada vez que aparece un vrtice u v en el circuito , se aade 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 aparicin que aaden 1.Suponemos que todos los vrtices tienen grado par y construimos el circuito euleriano T.Elegimos un vrtice v y empezamos un recorrido hasta que llegamos a un vrtice que ya no tiene aristas que no hayamos usado. Entonces cuando esto pasa, este vrtice 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 vrtice w no fuese v debera tener otra arista que no hemos usado porque si no tendra grado impar. Esto contradecira la hiptesis de que no tiene mas aristas que no han sido usadas.Entonces, T es un circuito.

  • (continuacin)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 algn vrtice v de Tque tiene aristas que no han sido usadas. (Si no el resto de los vrtices no usados no estaran 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 algn momento se hayan usado todas las aristas.

  • v1v6v4v3v5v2Ejemplo1:-Es conexo.-Todos los vrtices tienen grado par.Entonces existe un circuito euleriano.

  • v1v6v4v3v5v2Ejemplo1:v1-v2

  • v1v6v4v3v5v2Ejemplo1:v1-v2-v3

  • v1v6v4v3v5v2Ejemplo1:v1-v2-v3-v4

  • v1v6v4v3v5v2Ejemplo1:v1-v2-v3-v4-v5

  • v1v6v4v3v5v2Ejemplo1:v1-v2-v3-v4-v5-v6

  • v1v6v4v3v5v2Ejemplo1:v1-v2-v3-v4-v5-v6

  • v1v6v4v3v5v2Ejemplo1:v1-v2-v3-v4-v5-v6v3-v5

  • v1v6v4v3v5v2Ejemplo1:v1-v2-v3-v4-v5-v6v3-v5-v6

  • v1v6v4v3v5v2Ejemplo1:v1-v2-v3-v4-v5-v6v3-v5-v6-v3v1-v2-v3-v5-v6-v3-v4-v5-v6

  • Ejemplo2:-Es conexo.-Todos los vrtices tienen grado par.Entonces existe un circuito euleriano.v2v6v5v4v7v1v3

  • Ejemplo2:v2v6v5v4v7v1v3v1-v4-v6-v2-v5-v1

  • Ejemplo2:v2v6v5v4v7v1v3v1-v4-v6-v2-v5-v1

  • Ejemplo2:v2v6v5v4v7v1v3v1-v4-v6-v2-v5-v1v2-v7-v6-v5-v7-v3-v4-v2v1-v4-v6-v2-v7-v6-v5-v7-v3-v4-v2- v5-v1

  • Sea G un grafo con nicamente dos vrtices impares u y v. Sea H el grafo que se obtiene aadiendo un vrtice z que no pertenece a G y las aristas uz y vz. Entonces como H es conexo y todos los vrtices tienen grado par existe un circuito euleriano: u1u2u3uvun-1unEntonces:Es un recorrido euleriano.

  • La demostracin puede encontrase en:G. Chartrand, Applied and algorithmic graph theoryseccin 7.2, pgina 212.

  • Aplicacin 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 vrtices.El problema tiene solucin porque si doblamos las aristas para crear un multigrafoTodos los vrtices tendran grado par.

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

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

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

    Se define la distancia de la particin emparejada comod()= d (ui1,ui2)

    Y m(G)= min ( d() ).El camino euleriano se obtendra 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 vrtices impares.2.- Los pesos de las aristas corresponden a las distancias entre vrtices.(Moore).3.- Se escoge la particin mnima de este grafo.

  • u1u2u5u6u3u4u7u8Ejemplo1:

  • u1u2u5u6u3u4u7u8Ejemplo1:(1)(3)(1)(2)(4)(2)(2)(3)d {u1 u2}{u4u8}=1+3=4d {u1 u4}{u2 u8}=3+3=6d {u1 u8}{u2 u4}=4+2=6

  • Ejemplo2:BEFGADC79268741125

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

  • Definicin: Un grafo G se dice que es Hamiltoniano si tiene un ciclo recubridor. Es decir, un ciclo que pasa por cada vrtice una sola vez.Grafos Hamiltonianos

  • 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 vrtice de Gi i sea vi el vrtice que inmediatamente sigue a ui en C. Entonces vi pertenece a S y hay tantosvrtices en S como componentes en G-S.

  • Observar que este teorema sirve para probar que un grafo es no Hamiltoniano. PeroPodra habar algunos grafos no Hamiltonianos que tienen esta propiedad.!!!!!!!!El Grafo de Petersen.Definicin: Un camino Hamiltoniano de un grafo G es un camino recubridor de G

  • 1.- Sea P el camino mas largo que se puede encontrar.Entonces todos los vecinos de v1 y vn ya han sido usados ya que si no se podra hacer la cadena mas larga. Esta cadena tiene longitud al menos p/2 +1 (los vecinosde v1 mas el v1). 2.- Existe un vrtice vi , 2 i n, que es adyacente a v1 y que vi-1 es adyacente a vn. Si esto no fuera as, como todos los vecinos de v1 han sido usados y el anterior no es adyacente a vn, existiran p/2 vrtices distintos de vn que no son adyacentes. Perogrado ( vn ) (p-1)-p/2 < p/2 que contradecira la hiptesis de grado(vn) p/2.

  • 3.- Hemos visto que existe un ciclo C. Veamos que este ciclo contiene todos los vrtices.

    Si no contuviese todos los vrtices, existira algn vrtice u que no pertenece a C.Este vrtice tiene grado mayor que p/2.En 1.- vimos que la cadena tenia longitud mayor que 1 +p/2.Entonces u seria adyacente a algn vrtice de C.Pero u unido a C formara una cadena mas larga que la inicial, lo cual es absurdo.Por tanto C contienen todo los vrtices y G es Hamiltoniano.

  • Sea v un vrtice que no pertenece a G. Sea H el grafo que se obtiene a unir v con todos los vrtices de G.Entonces H tiene orden p +1 y v tiene grado p.Adems el grado de los vrtices 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 vrtice u de C tendramos el camino Hamiltoniano.

  • Definicin: Se define la clausura c(G) de un grafo G de orden p como el grafo obtenido de G uniendo recursivamente pares de vrtices no adyacentes cuya suma es al menos p hasta que no queden mas pares con esta propiedad.

  • La clausura es nica.Sean e1, e2,, em y f1, f2, , fn las aristas aadidas 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 contradiccin 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.Consecuencia del Teorema anterior y del Teorema de Dirac.Basta observar que la clausura seria completa.

  • Aplicacin de los grficos 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 solucin de bajo coste (no necesariamente la mnima)1.- n=12.- Selecciona cualquier vrtice v de G. C1=v v Mientras n< p- Encuentra un vrtice vn que no este en Cn y que unvn sea mnimo 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 0Ejemplo:v1 v3 v4 v2 v6 v1

  • Ejemplo:v1

  • Ejemplo:v1 v4 v1

  • 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 0Ejemplo: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 0Ejemplo: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 0Ejemplo:v1 v5 v3 v4 v2 v6 v1Coste 26 (El mnimo que se poda encontrar inicializandocon otro vrtice seria 21)