Caminos Hamiltonianos
Páginas: 2 (428 palabras)
Publicado: 11 de febrero de 2013
Problema del viajante
Un viajante de comercio desea visitar n ciudades volviendo al punto de partida. ¿Qué ruta debe seguir para minimizar la distancia total recorrida?
Caminos hamiltonianosGregorio Hernández Peñalver UPM
Teoría de Grafos A
B
C
Algoritmo
1. Calcular la distancia total de cada ciclo.
D
2. Hallar la mínima de las distancias anteriores ¿Cómo describirTODOS los ciclos?
F
E
¿Cuántos hay?
2
Complejidad
2 8 32 100
log n 1 3 5 6
n 2 8 32 100
n2 4 64 1024 104
2n n! 4 2 256 40320 4,3×109 2,6 ×1035 1,2×1027 9,3×10177
Un caminohamiltoniano en un grafo es un camino que contiene a todos los vértices del grafo exactamente una vez (salvo v0=vn, si el camino es cerrado). Un grafo hamiltoniano es aquel que contiene un ciclohamiltoniano.
a G d c G' d c d c b a b a b G''
Un siglo tiene 3,1×109 segundos Si la edad del Universo es de 15000 millones de años, el big-bang ocurrió hace 4,5×1017 segundos
3 4
PropiedadTeorema
Sea G un grafo simple de n vértices. Si para todo par de vértices x e y no adyacentes se cumple que d(x)+d(y) ≥ n , entonces G es hamiltoniano.
Un grafo bipartido G=(V1 ∪V2 , A) con⏐V1⏐≠⏐V2⏐ no es hamiltoniano
Teorema
Si G es un grafo hamiltoniano entonces, ∀ S ⊂ V se cumple que | comp. conexas de (G − S) | ≤ ⏐S⏐
S G−S
5
NO hay caracterización para los grafoshamiltonianos.
6
1
Recorrido del caballo en un tablero de ajedrez
Recorrido del caballo en un tablero de ajedrez
Tablero 4×4 Tablero 5×5
7
Tablero 8×8
8
Problema del Viajante(Travelling Salesman Problem)
Hallar la ruta de longitud mínima que vista todas las ciudades es un problema NP-completo
CÓDIGOS DE GRAY Alfabeto I={0,1} 2n palabras de longitud n Un código de Gray deorden n es una ordenación de esas 2n palabras tal que palabras consecutivas difieren en un sólo dígito. {000, 100, 110, 010, 011, 111, 101, 001, 000} es un código de Gray de orden 3.
011 111 101...
Un viajante de comercio desea visitar n ciudades volviendo al punto de partida. ¿Qué ruta debe seguir para minimizar la distancia total recorrida?
Caminos hamiltonianosGregorio Hernández Peñalver UPM
Teoría de Grafos A
B
C
Algoritmo
1. Calcular la distancia total de cada ciclo.
D
2. Hallar la mínima de las distancias anteriores ¿Cómo describirTODOS los ciclos?
F
E
¿Cuántos hay?
2
Complejidad
2 8 32 100
log n 1 3 5 6
n 2 8 32 100
n2 4 64 1024 104
2n n! 4 2 256 40320 4,3×109 2,6 ×1035 1,2×1027 9,3×10177
Un caminohamiltoniano en un grafo es un camino que contiene a todos los vértices del grafo exactamente una vez (salvo v0=vn, si el camino es cerrado). Un grafo hamiltoniano es aquel que contiene un ciclohamiltoniano.
a G d c G' d c d c b a b a b G''
Un siglo tiene 3,1×109 segundos Si la edad del Universo es de 15000 millones de años, el big-bang ocurrió hace 4,5×1017 segundos
3 4
PropiedadTeorema
Sea G un grafo simple de n vértices. Si para todo par de vértices x e y no adyacentes se cumple que d(x)+d(y) ≥ n , entonces G es hamiltoniano.
Un grafo bipartido G=(V1 ∪V2 , A) con⏐V1⏐≠⏐V2⏐ no es hamiltoniano
Teorema
Si G es un grafo hamiltoniano entonces, ∀ S ⊂ V se cumple que | comp. conexas de (G − S) | ≤ ⏐S⏐
S G−S
5
NO hay caracterización para los grafoshamiltonianos.
6
1
Recorrido del caballo en un tablero de ajedrez
Recorrido del caballo en un tablero de ajedrez
Tablero 4×4 Tablero 5×5
7
Tablero 8×8
8
Problema del Viajante(Travelling Salesman Problem)
Hallar la ruta de longitud mínima que vista todas las ciudades es un problema NP-completo
CÓDIGOS DE GRAY Alfabeto I={0,1} 2n palabras de longitud n Un código de Gray deorden n es una ordenación de esas 2n palabras tal que palabras consecutivas difieren en un sólo dígito. {000, 100, 110, 010, 011, 111, 101, 001, 000} es un código de Gray de orden 3.
011 111 101...
Leer documento completo
Regístrate para leer el documento completo.