Gregorio Hernández Peñalver Teoría de GrafosFacultad de Informática, UPM

1

GRAFOS HAMILTONIANOS

DefinicionesUn camino hamiltoniano en un grafo es un camino que contiene a todos los vértices del grafoexactamente una vez (salvo v0=vn, si el camino es cerrado). Un grafo hamiltoniano es aquel que contieneun ciclo hamiltoniano.

A pesar de la aparente analogía entre grafos eulerianos y hamiltonianos, hay profundas diferencias en suestudio. La fundamental es que no se conoce ninguna caracterización para los grafos hamiltonianos.Veamos en primer lugar un par de condiciones necesarias, la primera de ellas válida sólo para grafosbipartidos.

TeoremaSi el grafo bipartido G=(V1 ∪V2 , A) es hamiltoniano entonces V1=V2

TeoremaSi G es un grafo hamiltoniano entonces, para todo S⊂V se cumple que el número de componentesconexas de G − S, es menor o igual que S.

Esta condición necesaria no es suficiente para asegurar que el grafo sea hamiltoniano. El grafo dePetersen la cumple pero no es hamiltoniano

Los siguientes resultados proporcionan condiciones suficientes para asegurar la hamiltonicidad. Sinembargo, hay grafos hamiltonianos, como Cn, que no las cumplen.

Teorema (Ore)Sea G un grafo simple de n vértices (n≥3). Si para todo par de vértices x e y no adyacentes se cumple qued(x)+d(y) ≥≥ n , entonces G es hamiltoniano.

Corolario (Dirac)Sea G un grafo simple de orden n≥3 y tal que d(v)≥n/2 ∀v∈V(G). Entonces G es hamiltoniano.

CÓDIGOS DE GRAYConsideremos el alfabeto I={0,1} y las 2n palabras de longitud n que se pueden formar con las letras deeste alfabeto.Un código de Gray de orden n es una ordenación de esas 2n palabras tal que palabras consecutivasdifieren en un sólo dígito.Por ejemplo, {000, 100, 110,010, 0111, 111, 101, 001, 000} es un código de Gray de orden 3.

Recordemos la construcción de los grafos n-cubos (Qn es el grafo cuyo conjunto de vértices es el de lascadenas de longitud n de 0's y 1's, y donde dos vértices son adyacentes si las correspondientes cadenasdifieren sólo en un dígito). Con esto resulta que un código de Gray de orden n corresponde a un ciclohamiltoniano en Qn.

S

001101

111011

010110

100000

Un ciclo hamiltoniano en Q3

Gregorio Hernández Peñalver Teoría de GrafosFacultad de Informática, UPM

2

La existencia de códigos de Gray de todos los órdenes es así equivalente a que los grafos Qn seanhamiltonianos. Veamos, gráficamente, la construcción del código de Gray de orden 3 a partir del códigode orden 2.

TeoremaEl grafo n-cubo Qn es hamiltoniano para todo n>1Dem.Q2 es hamiltoniano pues es un 4-ciclo. Si Qn es hamiltoniano entonces existe un ciclo hamiltoniano quedesignamos por . El ciclo hamiltoniano que buscamos para Qn+1 es

Transmisión de fotografías desde un satéliteLas fotografías se transmiten a la Tierra por medio de largas sucesiones de números, cada uno de loscuales indica el color (o el grado de gris, si la foto es en blanco y negro) de uno los pixeles de la foto. Si,por ejemplo, se dispone de una escala de grises de 1 a 8 (el 1 es el blanco y el 8 el negro) y un pixel estámarcado con el valor 5, su código de Gray es el 011. Al transmitir la señal 011 las interferencias puedencambiar algún dígito y transformarla en 010, que corresponde al valor 4 de gris por lo que la foto no sealterará sustancialmente. Así pues, la ventaja de la utilización de los códigos de Gray es que permitencodificar las fotos de forma que los errores de transmisión causados por interferencias no alteranesencialmente las fotos enviadas.

Problema del viajante

Un viajante de comercio desea visitar n ciudades volviendo al punto de partida. ¿Qué ruta debe seguirpara minimizar la distancia total recorrida? Esta cuestión se conoce con el nombre de Problema delviajante (Travelling Salesman Problem) y tiene una clara interpretación en términos de grafos. Sea G elgrafo ponderado y conexo cuyos vértices vi representan las ciudades a visitar, y donde el peso wij de laarista vivj indica la distancia recorrida para viajar directamente desde vi hasta vj. Podemos suponer que elgrafo G es completo, pues si no hay ruta directa entre v i y vj podemos definir wij=dist(v i, vj). El Problemadel viajante pregunta por un ciclo hamiltoniano de mínimo peso.

Un algoritmo obvio para resolver este problema consiste en calcular el peso de todos los cicloshamiltonianos del grafo G. Pero el número de estos ciclos es (n-1)!/2, por lo este algoritmo no eseficiente. (Por ejemplo, para n=50 una computadora que realice 108 operaciones por segundo, tardaría1049 años en calcular el peso de todos los ciclos de G). Y más aún, se puede probar que el problema delviajante es NP-completo.

Presentamos a continuación tres algoritmos eficientes que obtienen ciclos hamiltonianos de peso cercanoal mínimo. En estos algoritmos, asumimos que los pesos de las aristas satisfacen la desigualdadtriangular, es decir, wik≤wij+wjk. Esta hipótesis adicional es totalmente razonable.

><−

0b,1b,,1b,1b,0b,,0b,0b 11122221 nnn KK

>< 1221 b,b,,b,b nK

1000

01 11

1000

01 11

001101

111011

010110

100000

Gregorio Hernández Peñalver Teoría de GrafosFacultad de Informática, UPM

3

Algoritmos aproximadosUn algoritmo aproximado para un problema de optimización es un algoritmo que alcanza una solución delproblema pero que no garantiza la solución óptima. ¿Cómo medir cuánto nos acercamos a ella?Si S* es la solución óptima con un coste c(S*), un algoritmo δ-aproximado es un algoritmo que devuelveuna solución S tal que

c(S) ≤ δ c(S*) (para un problema de minimización)c(S*) ≤ δ c(S) (para un problema de maximización)

Algoritmo de inserción (2-aproximación)En este algoritmo insertamos en un ciclo de longitud k un nuevo vértice con la condición de que la aristaque lo une al ciclo sea la de menor peso. Consideraremos K1y K2 como ciclos degenerados.

Entrada: Un grafo G, completo y ponderado, satisfaciendo la desigualdad triangularSalida: Un ciclo hamiltoniano de peso “bajo”.Paso 1: Elegir cualquier vértice y considerarlo como un 1-ciclo C1 de G. Tomar i=1Paso 2: Si i=n, entonces FIN, pues C=Cn es el ciclo buscado. En caso contrario buscamos un vértice x, nodel ciclo Ci, tal que el peso de la arista xz (con z sí en el ciclo Ci) sea mínimo.Paso 3: Sea Ci+1 el ciclo de longitud i+1 obtenido al insertar el vértice x inmediatamente antes de z en Ci.Hacemos i=i+1 y volvemos al paso 2.

TeoremaEl algoritmo anterior obtiene un ciclo hamiltoniano cuyo peso es menor que dos veces el peso de un ciclohamiltoniano de peso mínimo.

Análisis de la complejidadEl paso 2 es el fundamental en el análisis y se repite n veces. ¿Cuál es el coste cada vez?. Si se haconstruido Ci, se debe hallar la arista de menor peso entre i(n-i) aristas. Como i(n-i)<n2, la complejidaddel paso 2 es O(n2), luego la complejidad total es O(n3) ¿Se puede mejorar?

Algoritmo del árbol (2-aproximación)

Este algoritmo comienza construyendo un árbol generador mínimo T del grafo de partida G=Kn. Si C esun ciclo hamiltoniano mínimo, al borrar cualquier arista de C se obtiene un árbol generador de G, luegow(T)≤w(C). Sea H el grafo euleriano obtenido al duplicar las aristas de T. Un circuito euleriano de H nosda un camino cerrado de G cuyo peso es 2w(T). Ahora construimos un árbol de búsqueda en profundidadde T comenzando en una cualquiera de sus hojas, sea v1, v2,…, vn el orden en que aparecen los vértices enla búsqueda. Por la desigualdad triangular, el peso del ciclo C’ v1, v2,…, vn, v1 es a lo más el peso de H.Por tanto, w(C’) ≤2w(T)<2w(C). Es decir, el peso del ciclo hamiltoniano C’ que se construye es, a lo más,el doble del peso del ciclo hamiltoniano mínimo.

DescripciónPaso 1: Encontrar un árbol generador mínimo T del grafo completo ponderado G.Paso 2: Duplicar las aristas de T obteniendo un grafo euleriano G*Paso 3: Construir un recorrido euleriano en G* comenzando en una hoja de TPaso 4: Si v1, v2,…, vn es el orden en que se visitan los vértices de T en el paso 2, entonces la salida es elciclo v1, v2,…, vn, v1.

Paso 4Paso 1 Pasos 2 y 3 Solución óptima

Gregorio Hernández Peñalver Teoría de GrafosFacultad de Informática, UPM

4

ComplejidadVimos como se construye el árbol generador mínimo en O(n2). Los pasos 2, 3 y 4 se realizan en tiempolineal, luego la complejidad total es O(n2).

Algoritmo de Christofides (3/2-aproximación)Este algoritmo obtiene un ciclo hamiltoniano cuyo peso es, a lo más, 3/2 del peso del ciclo hamiltonianomínimo.

DescripciónPaso 1: Determinar un árbol generador mínimo T del grafo completo ponderado GPaso 2: Sea S el conjunto de vértices de grado impar de T. Se construye el grafo completo sobre S y seasigna a sus aristas el peso que tenían en G.Paso 3: Determinar un emparejamiento perfecto M de mínimo peso en KS.Paso 4:Sea G* el grafo que resulta de añadir las aristas de M al árbol T. Determinar un circuito eulerianoC de G*.Paso 5: Elegir un ciclo hamiltoniano en C tomando los vértices en el orden en que por primera vezaparecen en C y no teniéndolos en cuenta en las siguientes apariciones.

ComplejidadEl único paso que no se ha analizado en casos anteriores es el tercero. Existe un algoritmo de complejidadO(n3) que encuentra un emparejamiento perfecto de mínimo peso para K2n.

Los vértices de G MST(G) Emparejamiento de peso mínimo entrelos vértices impares de MST(G)

G* grafo euleriano Recorrido euleriano en G*

1

2 3

4 5

6

78

9

1

2 3

4 5

6

78

9

Ciclo hamiltonianoobtenido por el algoritmo