caminos y ciclos hamiltonianos

8/19/2019 Caminos y Ciclos Hamiltonianos

1/27

CAMINOS Y CICLOS

HAMILTONIANOSIntegrantes:

Cedillo García Miguel Zuriel

García Baeza Nahim AlexisRazo Ibarra Jorge Uriel

Profesor:

Dr. Jaime Rangel Mondragón

24 de Noviembre del 2014


2/27

• INTRODUCCIÓNEn 1859 el matemático irlandés Sir WilliamRowan Hamilton (1805-1865) desarrollo un juego,el cual era un dodecaedro regular de madera con20 esquinas (vértices) en las que aparecían

inscritos los nombres de ciudades importantes.El objetivo era encontrar un ciclo alrededor de lasaristas de modo que cada ciudad estuviera en elciclo solamente una vez.

2


3/27

DEFINICIONES Arista: Línea que resulta de la intersección dedos superficies, considerada por la parte exteriordel ángulo que forman.

Vértice: Punto en que concurren los dos lados deun ángulo.

Grado: El grado de un vértice en un grafo es elnúmero de caminos que inciden en el vértice, esdecir, es el número de líneas (aristas) que pasanpor un nudo (vértice) del grafo.

3


4/27

Para el grafo de la figura

Grad(b)=grad(d)=grad( f)=grad( g)=2.

Grad(c)=4.

Grad( e)=0.

Grad(h)=1, Comohtiene grado 1, se le llamavérticecolgante.

Grad(a)=3 ya que contamos el lazo dos veces.

4


5/27

Grafo: Diagrama que representa mediantepuntos y líneas las relaciones entre pares deelementos y que se usa para resolver problemaslógicos, topológicos y de cálculo combinatorio.

Grafo conexo: Un grafo en el que para cualquier

par de vérticesa yb existe al menos unatrayectoria que los conecta.

Grafo bipartita: Es un grafo cuyos vértices se

pueden separar en dos conjuntos disjuntosU yV,de manera que las aristas sólo pueden conectarvértices de un conjunto con vértices del otro.

5


6/27

Camino: Sucesión alternada finita (sin lazos) de

vértices y aristas de G, que comienza en el vértice x y termina en el vértice y y que contiene las naristas de G.

Ciclo: Consiste en un camino cerrado en el que nose repite ningún vértice de G a excepción delprimero que aparece dos veces como principio yfin del camino.

6


7/27

Vértice(s)

repetido(s)

Arista(s)

repetida(s)

abierto

cerrado

Nombre

Sí Sí Sí Camino

Sí Sí Sí Camino (cerrado)

Sí No Sí Recorrido

Sí No Sí Circuito

No No Sí Camino simple

No No Sí Ciclo

7


8/27

CAMINOS Y CICLOSHAMILTONIANOS

El ciclo (camino) Hamiltoniano tiene comoobjetivo pasar por cada vértice de un grafo unasola vez; el circuito (recorrido) recorre el grafopasando por cada arista exactamente una vez.

El problema de encontrar un ciclo (o camino)hamiltoniano en un grafo arbitrario se sabe quees NP-completo.

8


9/27

Demostrar que la figura 1.2 no contiene un ciclohamiltoniano y demostrar que la figura 1.3 si lo

contiene.

9


10/27

TEOREMA DE L’REDEI

Sea G=(V, E) un grafo son lazos,para todos x, y entonces G tiene un camino o cicloHamiltoniano.

TEOREMA DE OREUn grafo conn vértices (n > 3) es hamiltoniano sila suma de los grados de 2 vértices no adyacenteses mayor o igual quen.

10


11/27

EJEMPLOTenemos un grafo con n = 6

Sabemos que n-1=5

Contamos el grado de cada grafo

Grad(A)=4 Grad(B)=3

Grad(C)=4

Grad(D)=2

Grad(E)=4 Grad(F)=3

11


12/27

Hacemos las sumas de 2 vértices

Grad(A)+Grad(B)= 4+3=7

Grad(B)+Grad(C)= 3+4=7

Grad(C)+Grad(D)= 4+2=6

Sabemos que n-1=5 y todas las sumas sonmayores a 5 entonces concluimos que existe unciclo Hamiltoniano en el grafo.

12


13/27

Ejemplo:

Este ejemplo proporciona una aplicación quenecesita los ciclos hamiltonianos en un grafocompleto.

En el campamento que el profesor ha organizadocon su grupo de antropología, 17 estudiantescomen juntos en una mesa circular. Comointentan conocerse mejor, tratan cada tarde desentarse con dos compañeros distintos. ¿Durantecuántas tardes pueden hacer esto? ¿Cómo puedenhacerlo?

13


14/27

Para resolver el problema, consideramos , donden ≥ 3 y n es impar. Este grafo tiene n vértices(uno para cada estudiante) y aristas. Un ciclohamiltoniano corresponde a una disposición delugares. Cada uno de estos ciclos tienen aristas,por lo que se tiene como máximo cicloshamiltonianos sin que dos de ellos tengan una

arista en común.

14


15/27

Consideremos el círculo de lafigura a) y el subgrafo de queconsta den vértices yn aristas{1,2}, {2,3}, ... , {n–1,n}, {n, 1}.Mantenemos los vértices en lacircunferencia fijos y rotamoseste ciclo hamiltoniano en el

sentido de las manecillas delreloj. Esto produce el ciclohamiltoniano formado por lasaristas {1,3}, {3,5},{5,2},{2,7}, ...

, { n, n–3},{n–3,n–1}, {n–1, 1}( b) ). Este ciclo hamiltonianono tiene aristas en común conel primer ciclo.

15


16/27

Sin≥ 7 y seguimos rotando de esta manera elciclo de la figura a), hasta que obtenemos un totalde (n–1)/2 ciclos hamiltonianos, sin que haya dosaristas en común.

16


17/27

Por lo tanto, los 17 estudiantes que participan enel campamento pueden comer durante días antesde que tengan que sentarse junto a otroestudiante por segunda vez. Usando la figura a)conn=17, podemos obtener ocho de estas posiblesdisposiciones.

17


18/27

APLICACIONES

EL PROBLEMA DEL AGENTE DE VENTAS VIAJERO

El problema del agente de ventas viajero fue la

principal aplicación para los ciclos de Hamilton,fue formulado en 1859 por el matemático irlandésWilliam R. Hamilton.

Originalmente el problema incluye viajes a

Alemania y Suiza y responde a la pregunta ¿Quéruta es mas corta visitando todas y cada una delas ciudades sin repetir alguna y volver a la delorigen? 18


19/27

EL DODECAEDROEl dodecaedro es un grafo en forma de pentágonocon veinte vértices y treinta aristas, cada vérticerepresenta una ciudad a la cual el agente debeviajar, lo que buscamos es el camino mas corto de

aristas que pase por todos los vértices sin repetiry terminando en la ciudad de origen.

19


20/27

Podemos observar que el ejemplo del dodecaedrosi tiene un ciclo Hamiltoniano, el camino

marcado con rojo representa el ciclo y comopodemos observar termina en el mismo vérticedel origen (X).

20


21/27

EL N-CUBO (HIPERCUBO)

La computadora tradicional llamada en serie, seejecuta una instrucción a la vez .

En los últimos años, se han construido“Computadoras Paralelas” con muchosprocesadores, los cuales pueden ejecutar variasinstrucciones a la vez, se utilizan a los grafospara ilustrar la topografía de estas maquinas

paralelas. Los algoritmos asociados con estosequipos son algoritmos paralelos.

21


22/27

Una maquina paralela muy utilizadaactualmente es conocida como el n-cubo o

hipercubo .El n-cubo tiene 2 procesadores, n ≥ 1,ⁿ

cada procesador se representa mediante un nodo.

Figura 1.4

22


23/27

Cada procesador tiene su propia memoria local.Una arista conecta dos vértices si larepresentación binaria de sus etiquetas difieren enexactamente un bit.

Durante una unidad de tiempo, todos los

procesadores de el n-cubo pueden ejecutar unainstrucción de manera simultánea y luegocomunicarse con el procesador adyacente.

23


24/27

1-CUBO

2 procesadores 0,1

4 procesadores 00,01,10,11

2-CUBO

24


25/27

3-CUBO

000 001

110

111

011

101

010

100

8 procesadores

000,001,010,011,100,101,110,111

25


26/27

CONCLUSIONES

Como se mencionó el problema del ciclo o caminoHamiltoniano es un problema N-P Completo. Esto quieredecir que es un problema muy complejo de resolver en untiempo polinómico.

No existe algoritmo o formula que lleve a la solución de sihay o no un ciclo o camino hamiltoniano en todo tipo degrafo y mucho menos hay algoritmo para indicar cual esdicho camino.

La fama y la fortuna esperan al descubridor de unalgoritmo de tiempo polinomial que resuelva el problemadel ciclo hamiltoniano o que dé una demostración de que noexiste un algoritmo de tiempo polinomial para estosproblemas.

26


27/27

Linkografía.• http://es.wikipedia.org/wiki/Camino_hamiltoniano

•

http://www.cyclopaedia.es/wiki/Grafo-hipercubo• http://www.youtube.com/watch?v=uWqp8rqY4Fs

• http://www.tdx.cat/bitstream/handle/10803/6727/TESM1de1.pdf;jsessionid=6A971E1962CA24CFDE3788735CCC9639.tdx2?sequence=1

Bibliografía• Ralph P. Grimaldi. (1994). Matemáticas Discreta yCombinatoria 3ª Edición. México D.F: Pearson.

•

R. Johnsonbaugh. (1994). Matemáticas Discretas 4ªEdición. Pearson.

27

caminos y ciclos hamiltonianos

Documents