[go: up one dir, main page]
Scribd
Cargar
72 vistas2 páginas

Hamilton 08

Este documento trata sobre el problema del viajante de comercio y los caminos hamiltonianos en grafos. Explica que el problema del viajante busca encontrar la ruta más corta que visita todas las ciudades y regresa al punto de partida, mientras que un camino hamiltoniano visita cada vértice de un grafo exactamente una vez. También presenta algunos teoremas y algoritmos relacionados con estos temas.

Cargado por

Car So
Derechos de autor
© Attribution Non-Commercial (BY-NC)
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
72 vistas2 páginas

Hamilton 08

Este documento trata sobre el problema del viajante de comercio y los caminos hamiltonianos en grafos. Explica que el problema del viajante busca encontrar la ruta más corta que visita todas las ciudades y regresa al punto de partida, mientras que un camino hamiltoniano visita cada vértice de un grafo exactamente una vez. También presenta algunos teoremas y algoritmos relacionados con estos temas.

Cargado por

Car So
Derechos de autor
© Attribution Non-Commercial (BY-NC)
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
Está en la página 1/ 2

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 hamiltonianos
Gregorio Hernndez Pealver UPM
Teora de Grafos A

Algoritmo
1. Calcular la distancia total de cada ciclo.

2. Hallar la mnima de las distancias anteriores Cmo describir TODOS los ciclos?

Cuntos 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,3109 2,6 1035 1,21027 9,310177

Un camino hamiltoniano en un grafo es un camino que contiene a todos los vrtices del grafo exactamente una vez (salvo v0=vn, si el camino es cerrado). Un grafo hamiltoniano es aquel que contiene un ciclo hamiltoniano.
a G d c G' d c d c b a b a b G''

Un siglo tiene 3,1109 segundos Si la edad del Universo es de 15000 millones de aos, el big-bang ocurri hace 4,51017 segundos
3 4

Propiedad

Teorema
Sea G un grafo simple de n vrtices. Si para todo par de vrtices 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 V1V2 no es hamiltoniano

Teorema
Si G es un grafo hamiltoniano entonces, S V se cumple que | comp. conexas de (G S) | S

S GS

NO hay caracterizacin para los grafos hamiltonianos.

Recorrido del caballo en un tablero de ajedrez

Recorrido del caballo en un tablero de ajedrez

Tablero 44 Tablero 55
7

Tablero 88
8

Problema del Viajante (Travelling Salesman Problem)


Hallar la ruta de longitud mnima que vista todas las ciudades es un problema NP-completo

CDIGOS DE GRAY Alfabeto I={0,1} 2n palabras de longitud n Un cdigo de Gray de orden n es una ordenacin de esas 2n palabras tal que palabras consecutivas difieren en un slo dgito. {000, 100, 110, 010, 011, 111, 101, 001, 000} es un cdigo de Gray de orden 3.
011 111 101

http://www.tsp.gatech.edu/index.html Algoritmos aproximados


- Vecino ms prximo - Doble intercambio - Duplicando MST - Algoritmo de Christofides

001

Un ciclo hamiltoniano en Q3
110

010 000 100

011

111 101

01 00 01 10

11

001

11 10
000

010 100

110

http://www.dma.fi.upm.es/gregorio/grafos/enlacesgrafos.html
00 9 10

También podría gustarte