Notas de Graficas y Juegos Sección 4 Recorridos Eulerianos y Ciclos Hamiltonianos PDF

Preview

Summary

Download Notas de Graficas y Juegos Sección 4 Recorridos Eulerianos y Ciclos Hamiltonianos PDF

Description

CAPÍTULO 4. RECORRIDOS EULERIANOS Y CICLOS HAMILONIANOS

Capítulo 4 Recorridos Eulerianos y Ciclos Hamilonianos 4.1.

Recorridos Eulerianos

En Euler (1736) el matemático suizo Leonhard Paul Euler publicó el primer artículo conocido en el que apareció la teoría de gráficas. En él Euler probó que no es posible cruzar a cada uno de los puentes de Königsberg una y sólo una vez durante un recorrido por la ciudad, es por esto que se bautizaron a éste tipo de recorridos como “paseos eulerianos”. Definición 4.1. Un paseo euleriano de la gráfica G es un recorrido que toma a cada arista de G una y sólo una vez. Un ciclo euleriano es un recorrido euleriano cerrado. Una gráfica es euleriana si tiene un ciclo euleriano. Teorema 4.2. Una gráfica conexa es euleriana si y sólo si todos sus vértices son de grado par. Demostración. Ida: Si G es euleriana con ciclo euleriano C que inicia y termina en u entonces por cada aparición de un vértice v en el interior de C se suma dos al grado de v pues hay dos aristas incidentes en él, como en C aparecen todas las aristas entonces el grado de v debe ser dos veces la cantidad de veces que aparece internamente en C por lo que es par. Para u tenemos lo mismo pero hay que añadir 2 a la cuenta, una por cada extremo, y sigue siendo par. Como G es conexa, todos los vértices de G deben aparecer en C de donde todos los vértices de G tienen grado par. Regreso: Por contradicción: Supongamos que G es una gráfica conexas con todos sus vértices de grado par pero que no es euleriana. Como en G todos los vértices son de grado par podemos construir un paseo cerrado C en G tomando a v un vértice cualquiera de G y siguiendo aristas sin repetir en cualquier orden y deteniéndonos en cuanto volvamos a v, si no hemos vuelto a v y

4.2. CICLOS HAMILTONIANOS estamos en un vértice u entonces u aún tiene una arista que podemos recorrer pues sólo hemos usado una cantidad impar de aristas de u. G tiene paseos cerrados, sea C un paseo cerrado de G de longitud máxima, G ´ AC tiene aristas incidentes en vértices de C pues G no es euleriana pero sí es conexa. C en sí misma es euleriana por lo que sus vértices tienen grado par, luego los vértices de G ´ AC tienen todos grado par también, sea v un vértice de C con por lo menos una arista de G ´ AC entonces v pertenece a un paseo cerrado C 1 de G ´ AC con por lo menos una arista (siguiendo el proceso del párrafo anterior), supongamos sin pérdida de generalidad que C también empieza y acaba en v entonces el paseo CC 1 es un paseo cerrado de longitud mayor que la de C lo cual es una contradicción. Corolario 4.3. Una gráfica conexa G tiene un paseo euleriano no cerrado si y sólo si tiene exactamente dos vértices de grado impar. Más aún, todo paseo euleriano no cerrado de G inicia y acaba en esos vértices de grado impar. Demostración. Ida: Si G tiene un uv-paseo euleriano no cerrado C entonces la gráfica H “ G ` a con ψH paq “ uv tiene como ciclo euleriano a Cpv, a, uq por lo que H tiene a todos sus vértices con grado par y luego en G todos los vértices tienen el mismo grado que en H excepto u y v que tienen el grado de H menos uno, por lo que u y v son los únicos dos vértices de G con grado impar. Regreso: Supongamos que en G sólo los vértices u y v (distintos) tienen grado impar, luego H “ G ` a con ψH paq “ uv es conexa con todos sus vértices de grado par por lo que tiene un ciclo euleriano C, podemos acomodar al ciclo de manera que C “ pv, a, u, a1 , v1 , . . . , am , v q donde ta1 , . . . , am u “ AG luego la uv-sección de C pu, a1 , v1 , . . . , am , v q es un uv recorrido euleriano de G.

4.2.

Ciclos Hamiltonianos

Definición 4.4. Un camino hamiltoniano de G es una trayectoria que toma a los vértices de G una y sólo una vez. Un ciclo hamiltoniano de G es un ciclo que toma a todos los vértices de G. Una gráfica es hamiltoniana si tiene un ciclo hamiltoniano. Tales caminos y ciclos llevan el nombre de Hamilton (1856), quien describió, en una carta a su amigo Graves, un juego matemático sobre el dodecaedro en el que una persona pega cinco clavijas en cualesquiera cinco vértices consecutivos y el otro debe completar la trayectoria formada para hacer un ciclo generador.

CAPÍTULO 4. RECORRIDOS EULERIANOS Y CICLOS HAMILONIANOS A diferencia de con las gráficas eulerianas, no se conoce una condición suficiente y necesaria sencilla para que una gráfica sea hamiltoniana; de hecho el problema de encontrar dichas condiciones es uno de los más grandes problemas no resueltos de la teoría de gráficas. Presentamos a continuación una condición necesaria sencilla pero muy útil: Teorema 4.5. Si G es una gráfica hamiltoniana entonces para todo subconjunto propio S Ă VG no vacío ωpG ´ Sq ď |S| Demostración. Sea C un ciclo y S Ă VC entonces ωpC ´ Sq ď |S| pues al quitar un vértice C sigue siendo conexa y a partir de ahí C ´ S es una unión de caminos por lo que al quitar un vértice uno puede quitar un extremo en cuyo caso la cantidad de componentes no aumenta o uno puede quitar un vértice del interior de un camino en cuyo caso la cantidad de componentes aumenta sólo en uno. Si G es hamiltoniana entonces tiene un subciclo generador C, por lo anterior ωpC ´ Sq ď |S| pero como C ´ S es subgráfica generadora de G ´ S entonces ωpG ´ Sq ď ωpC ´ Sq de donde ωpG ´ Sq ď |S|. Lamentablemente esta condición no implica que una gráfica sea hamiltoniana, por ejemplo la gráfica de Petersen es cumple que ωpG ´ Sq ď |S| para todo ‰ S Ă VG pero no es hamiltoniana. Discutamos ahora sobre las condiciones suficientes para que una gráfica sea hamiltoniana. Como un ciclo de longitud mayor que 2 siempre es simple y los casos de uno o dos vértices son suficientemente sencillos, nos restringimos sólo a gráficas simples para el resto de la sección. Empecemos con un resultado dado por Dirac (1952). Teorema 4.6. Si G es una gráfica simple con nG ě 3 y δ ě hamiltoniana.

nG 2

entonces G es

Demostración. Por contradicción: supongamos que existen gráficas simples G con nG ě 3 y δ ą nG2´1 pero no hamiltonianas. Sea n ě 3 un orden para el que existen gráficas así, sea G una gráfica simple de orden n con δ ě n2 y con la mayor cantidad de aristas que sigue sin ser hamiltoniana, esta gráfica existe pues si nG ě 3 entonces la gráfica completa siempre es hamiltoniana. Por lo anterior G no es completa, sean u y v dos vértices que no son vecinos de G, consideremos a H “ G ` uv. Por la maximalidad del tamaño de G tenemos que H es hamiltoniana y además todo ciclo hamiltoniano C de H debe contener a la arista uv por lo que lo podemos acomodar como C “ pv, u, v1 , v2 , . . . , vn´2 , v q y luego C 1 “ pu, v1 , . . . , vn´2 , v q es un camino hamiltoniano de G. Consideremos a los conjuntos siguientes de u y v , ˇ ˇ ve1 puq “ tvi ˇ uvi`1 P AG u y vepvq “ tvj ˇ vvj P AG u,

4.2. CICLOS HAMILTONIANOS (donde vn´1 “ v ). Tenemos que |ve1 puq|, |vepvq| ą n´1 pues sus cardinalidades son los grados de u y 2 vértices de v respectivamente. Sea S “ tv1 , . . . , vn´2 u, vepvq toma a más de n´1 2 S mientras que ve1 puq toma a más de n´1 ´ 1 vértices de S (pues v puede estar en 2 ve1 puq pero no está en S), en conjunto toman a más de n ´ 1 ´ 1 “ n ´ 2 vértices de S, pero como S sólo tiene n ´ 2 elementos entonces tienen que reperit a algún vértice, digamos a vl . Tenemos entonces que uvl`1 , vvl P AG consideremos entonces al siguiente ciclo: p u, v1 , v2 , . . . , vl´1 , vl , v, vn´2 , vn´3 , . . . , vl`2 , vl`1 , u q. Este ciclo toma a todos los vértices de G por lo que G es una gráfica hamiltoniana, lo que es una contradicción. Bondy and Chvatal (1974) observaron que la prueba del teorema anterior se puede modificar para obtener condiciones suficientes más fuertes que las obtenidas por Dirac. Primero consideremos el siguiente lema: Lema 4.7. Sea G una gráfica simple y sean u y v vértices no adyacentes de G tales que gpuq ` g pvq ě n, G es hamiltoniana si y sólo si G ` uv es hamiltoniana. Demostración. Si G es hamiltoniana entonces trivialmente G ` uv también lo es. Por otro lado si G ` uv es hamiltoniana entonces podemos seguir a la prueba del teorema anterior y llegar a que ve1 puq y vepvq deben tomar en conjunto a n ´ 1 vértices o más de S pero en este caso porque los grados de u y v suman n o más, luego la conclusión es idéntica. El lema anterior motiva a la siguiente definición: Definición 4.8. La cerradura de G es la gráfica cpGq obtenida recursivamente agregando aristas que hagan adyacentes a vértices previamente no adyacentes cuya suma de grados sea mayor o igual que nG hasta que ya no se pueda más. Teorema 4.9. La cerradura de G está bien definida, es decir, no importa cómo vayamos agregando a las aristas siempre llegamos a la misma gráfica al final. Demostración. Supongamos que G1 y G2 son dos cerraduras de G, debemos probar que G1 “ G2 . Supongamos que G1 ‰ G2 , sea A “ pa1 , a2 , . . . , ak q las aristas en el orden que se fueron agregando a G para obtener a G1 , como G1 ‰ G2 entonces hay aristas de A que no pertenecen a G2 (o viceversa, pero tomemos este caso sin pérdida de generalidad), sea ai la primera arista de A que no pertenece a G2 , sean ai “ uv y G11 “ G ` ta1 , . . . , ai´1 u

CAPÍTULO 4. RECORRIDOS EULERIANOS Y CICLOS HAMILONIANOS entonces G11 ď G2 pero como ai se agregó después a G11 , necesariamente gG11 puq ` gG11 pvq ě n, pero como G11 ď G2 entonces gG2 puq ` gG2 pvq ě gG11 puq ` gG11 pvq ě n y como G2 es cerrada entonces ai “ uv debe ser una arista de G2 lo que es una contradicción. De aquí que G1 “ G2 y la cerradura de G está bien definida (siempre es la misma). Teorema 4.10. Una gráfica es hamiltoniana si y sólo si su cerradura es hamiltoniana. Demostración. Supongamos que cpGq “ G ` ta1 , . . . , ak u donde pa1 , . . . , ak q están en el orden en el que se fueron agregando, entonces por el lema 4.7 G es hamiltoniana si y sólo si G ` a1 lo es y en general G ` ta1 , . . . , al u es hamiltoniana si y sólo si G ` ta1 ` . . . , al , al`1 lo es y así inductivamente obtenemos que G es hamiltoniana si y sólo si G ` ta1 , . . . , ak u “ cpGq lo es. Corolario 4.11. Si nG ě 3 y cpGq es completa entonces G es hamiltoniana. Demostración. Usando el teorema anterior y el hecho de que si n ě 3 entonces Kn es hamiltoniana. Del corolario anterior Chvatal (1972) obtuvo una condición suficiente para que G sea hamiltoniana más general que la de Dirac: Teorema 4.12. Sea G una gráfica simple con secuencia de grados pg1 , g2 , . . . , gn q donde gi ď gi`1 y n ě 3. Si para todo entero positivo k ă n2 se tiene que gk ą k o gn´k ě n ´ k entonces G es hamiltoniana. La prueba es relativamente larga y no es de nuestro interés explorar con tanto detalle este tema considerando que éste es un texto introductorio. La prueba de este resultado y más condiciones suficientes para que una gráfica sea hamiltoniana se pueden encontrar en la sección 4.2 del libro Bondy and Murty (1982).

4.3. 4.3.1.

Aplicaciones El problema del cartero chino y el algoritmo de Fleury

Un cartero debe recoger en la mañana el correo en la oficina postal y luego ir a entregarlo cubriendo cada calle de su zona y al final regresar a la oficina postal. Sujeto a estas condiciones él quiere, por supuesto, hacer su ruta de manera que camine lo menos posible. Este problema es conocido como el problema del cartero chino pues fue formulado por primera vez por el matemático chino Kuan (1962).

4.3. APLICACIONES Definición 4.13. En una gráfica simple pesada G “ pV, A, pq con pesos positivos llamamos a un camino cerrado óptimo si toma a todas las aristas de G por lo menos una vez y su longitud es mínima. Nuestro problema consta entonces en encontrar un camino cerrado óptimo. Como tomamos a G conexa todos los vértices de G se deben usar por lo que no importa dónde empiece y termine nuestro camino cerrado óptimo siempre lo podemos acomodar para que empiece y acabe en la oficina postal. Claramente si G es euleriana entonces el ciclo euleriano es un camino cerrado óptimo pues los pesos van aumentando cuando se toman aristas más de una vez. En este caso existe un buen algoritmo para encontrar a un ciclo euleriano dado por Fleury (ver Lucas (1921)). En el algoritmo de Fleury se empieza en un vértice y se van tomando aristas consecutivas con la única condición de que no se tome una arista de corte a menos que no haya otra opción: Algoritmo de Fleury 1. Elije a un vértice arbitrario v0 y sean C “ pv0 q, i “ 0, y A1 “ H. 2. (*) Elije a ai de AzA1 de manera que vi incide en ai y, a menos que no sea posible, ai no es arista de corte de G ´ A1 . 3. vi`1 es el vértice incidente en ai que no es vi . A1 Y tai u ÞÑ A1 , Cpvi , ai , vi`1 q ÞÑ C, i ` 1 ÞÑ i. 4. Si vi es incidente en alguna arista de AzA1 regresa a (*). El algoritmo anterior se puede usar para gráficas conexas no triviales en general. Por su definición es claro que C es un paseo de G, hace falta ver que si G es euleriana entonces en efecto toma a todas las aristas. Teorema 4.14. Si G es euleriana entonces cualquier paseo construido usando el algoritmo de Fleury es un ciclo euleriano. Demostración. Supongamos que G es euleriana y que el ciclo obtenido al final del algoritmo es C “ pv0 , a1 , v1 , . . . , vk q. Sea G1 “ G ´ A1 “ G ´ ta1 , . . . , ak u, por el último paso del algoritmo vk debe ser de grado cero en G1 . Como todos los vértices tienen grado par, se sigue que vk “ v0 por lo que C es un paseo cerrado. Supongamos que C no es un ciclo euleriano y sea S el conjunto de vértices de G1 que tienen grado positivo. Por suposición S no es vacío y v0 “ vk P S c . Todos los vértices de S c pertenecen a C pues los vértices que no aparecen en C tienen el mismo grado en G que en G1 y todo vértice tiene grado positivo en G. Veamos que también hay un elemento de S en C: Como G es conexa entonces hay por lo menos una arista a “ uv con u P S y v P S c si u P C entonces ese ya es un elemento de S en C pero si u no está en C entonces a tampoco está en C, luego

CAPÍTULO 4. RECORRIDOS EULERIANOS Y CICLOS HAMILONIANOS a está en G1 y así v es incidente en una arista en G1 por lo que v P S, lo cual es una contradicción. Con esto probamos además que si u P S y está conectado a algún vértice de S 1 entonces u es vértice de C . Como hay elementos de S en C y vk P S c entonces podemos tomar al máximo entero l tal que vl está en S y vl`1 P S c de aquí que al`1 es la única arista de Gl1 “ G ´ ta1 , . . . , al u que une a S con S c ya que, de haber otro, el extremo que pertenece a S debería estar en C por lo visto en el párrafo anterior y como C termina en S c en algún momento posterior C debería volver a tomar una arista de S a S c , contradiciendo a la maximalidad de l. De aquí que al`1 es una arista de corte de Gl1. Sea a ‰ al`1 cualquier otra arista incidente en vl de Gl1 (que existe pues vl P S ), sigue del paso 2 del algoritmo que a debe ser también arista de corte en Gl1 y por lo tanto es arista de corte en Gl1rSs (por ser subgráfica de Gl1 ). Gl1 rSs “ G1 rSs pues ningún vértice de G1 a partir de al aparece en S pero G1 rSs “ G ´ C pues todos los vértices de S c están en C, luego a es arista de corte de G ´ C. En G ´ C todos los vértices tienen grado par pues en G lo tenían y C es un paseo cerrado, luego la componente de G ´ C que contiene a a es euleriana por lo que a no puede ser de corte, lo que es una contradicción. Concluimos que S tiene que ser vacío por lo tanto C es un circuito euleriano. Probar que el algoritmo de Fleury es bueno queda como ejercicio para el lector. No es muy difícil ver que si G tiene un paseo euleriano y v0 tiene grado impar entonces el algoritmo de Fleury encontrará a un paseo euleriano. Si G no es una gráfica euleriana entonces cualquier camino cerrado que cubra a todas las aristas debe repetir aristas y en particular un camino cerrado óptimo debe repetir aristas. Para atacar este problema introducimos el concepto de duplicación de aristas: Definición 4.15. Sea G una gráfica pesada (posiblemente con multiaristas), y a P AG , definimos a la gráfica H “ G`ad con arista duplicada ad de a tal que ψH pad q “ ψG paq y pH pad q “ pG paq, en este caso ad se vuelve una multiarista de a con el mismo peso. Podemos pensar que en vez de cruzar dos veces o más a la misma arista, el cartero debe recorrer aristas duplicadas posiblemente varias veces, pero de esa manera siempre podemos reducir el problema a encontrar ciclos eulerianos. El problema del cartero chino se puede reformular como 1. Encontrar a una gráfica G˚ euleriana obtenida duplicando aristas de G tal que el peso de G˚ ´ AG sea mínimo. 2. Encontrar un ciclo euleriano de G˚ . Ya hemos dado un buen algoritmo para resolver el segundo punto y un buen algoritmo que resuelve el primer punto fue dado por Edmonds and Johnson (1973). Desafortunadamente es demasiado complicado para ser presentado aquí.

4.3. APLICACIONES Un caso particular que podemos explorar es en el que exactamente dos vértices de G tienen grado impar, digamos u y v. En ese caso para que G˚ sea euleriana u y v necesitan tener grado par en G˚ por lo que necesitan tener grado impar en G˚ ´ AG y todos los demás vértices de G˚ ´ AG también deben tener grado par, de aquí que en G˚ ´ AG debe haber una uv-trayectoria (no puede haber un sólo vértice de grado impar en una componente de conexidad por lo que ambos deben estar en la misma componente), digamos C ˚ . Es claro que es suficiente también que haya una uv-trayectoria de aristas duplicadas C ˚ en G˚ para que G˚ sea euleriana por lo que basta con que encontremos una uv-trayectoria de longitud mínima en G y duplicar esas aristas para obtener a G˚ y así obtendremos a la gráfica euleriana G˚ óptima. Ya presentamos en la sección 1.8.1 un buen algoritmo para encontrar el camino mínimo, ese algoritmo junto con el de Fleury nos da un buen algoritmo para encontrar el camino cerrado óptimo de G.

4.3.2.

El problema del vendedor viajero

Un vendedor quiere viajar a ciertos pueblos y luego regresar a su punto de partida, dados los tiempos de viaje entre cualesquiera dos pueblos ¿Cómo debería el viajero planear su itinerario para viajar a todos los pueblos exactamente una vez en el menor tiempo posible? Éste es conocido como el problema del vendedor viajero. En términos de gráficas buscamos al ciclo hamiltoniano más ligero H en una gráfica pesada y completa (simple) G. Llamamos a un ciclo así un ciclo óptimo. A diferencia de antes, y considerando que los ciclos hamilotnianos son más complicados que lo eulerianos, no se conoce ningún algoritmo eficiente para resolver el problema del vendedor viajero. No obstante existen métodos para obtener soluciones razonablemente buenas (aunque no necesariamente óptimas). Mostraremos como algo de nuestra teoría previa puede ser empleada con este propósito. Una primera idea es la de encontrar un ciclo hamiltoniano cualquiera C y tratar de encontrar un ciclo más ligero modificando apropiadamente a C. Posiblemente la modificación más sencilla es la que sigue: Sea C “ pv1 , v2 , . . . , vn , v1 q y sean i y j tales que 1 ă i ` 1 ă j ă n, podemos obtener a un nuevo ciclo hamiltoniano Ci,j “ pv1 , v2 , . . . , vi´1 , vi , vj , vj´1 , . . . , vi`2 , vi`1 , vj`1 , vj`2 , . . . , vn´1 , vn , v0 q. El ciclo Ci,j se obtiene de C invirtiendo a su vi`1 vj -sección. La única diferencia en aristas entre Ci,j y C es que Ci,j tiene a las aristas vi vj y vi`1 vj`i per C no y C tiene a las aristas vi vi`1 y vj vj`1 pero Ci,j no de manera que la diferencia de pesos es ppCq ´ ppCi,j q “ ppvi vi`1 q ` ppvj vj`1 q ´ ppvi vj q ´ ppvi`1 vj`1 q de modo que si ppvi vi`1 q` ppvj vj`1 q ą ppvi vj q` ppvi`1 vj`1 q entonces Ci,j es un camino más ligero que C .

vez.

entonces...