GRAFOS HAMILTONIANOs

7/25/2019 GRAFOS HAMILTONIANOs

1/25

GRAFOS HAMILTONIANOSubttulo


2/25

INTRODUCCIN Los caminos y ciclos hamiltonianos se llaman ashonor de William Rowan Hamilton, inventor de uque consista en encontrar un ciclo hamiltonianoaristas de un grafo de un dodecaedro.
http://es.wikipedia.org/wiki/William_Rowan_Hamiltonhttp://es.wikipedia.org/wiki/Dodecaedrohttp://es.wikipedia.org/wiki/Dodecaedrohttp://es.wikipedia.org/wiki/William_Rowan_Hamilton


3/25

Grafos HamiltonianosSea G=(V,E) un grafo no dirigido

Se llama camino hamiltoniano de G a todo caminque contenga a todos los vrtices del grafo (

Se llama ciclo hamiltoniano de G a todo ciclo C contenga todos los vrtices de G

Se dice que un grafo es hamiltoniano si conticiclo hamiltoniano.


4/25

Ejemplo: Observe es siguiente grafo G y diga si camino o ciclo hamiltoniano?

Es un grafo hamiltoniano

Si G es hamiltoniano tiene camino

hamiltoniano


5/25

Ejemplo: Observe el siguiente grafo G y tiene camino o ciclo hamiltoniano

Camino hamiltoniano

No hay camino hamiltoniano

Ciclo hamiltoniano

No hay ciclo hamiltonia

No es grafo hamiltonian


6/25

Ejercicio. Observe los grafos no dirigidos sig

analice si tienen camino hamiltoniano

hamiltoniano


7/25

Hay alguna forma sencilla de determinar si grafo contiene o no un camino o ciclohamiltoniano?

Sorprendemente no.

No se conocen condiciones necesarias y suficientsencillas para la existencia de ciclos hamiltoniano

Pero por suerte hay teoremas que dan condicionesuficientes para la existencia de circuitos hamilton

tambin hay propiedades que se pueden utilizar pdemostrar que un grafo no contiene circuito ham


8/25

Condiciones necesarias

Sea G= V,E) grafo no dirigido

G es hamiltoniano entonces ,

Si existe un vrtice con < entonces Ghamiltoniano

~


9/25


10/25

Cundo y cmo hallar ciclos hamilton

Teorema de Dirac

Sea G= V,E) un grafo no dirigido, simple y con al men

vrtices, |V| = n 3.

Si cada vrtice tiene grado mayor o igual que n/2,

es Hamiltoniano.(Tiene ciclo hamiltoniano)

Veamos:Este grafo tiene 3 vrtices y vemos que

hamiltoniano y se puede verificar que

hiptesis del Teorema de Dirac


11/25

Los siguientes ejemplos muestran como la est

es bastante precisa

1)

n=6 3

=

=3

gr A)=gr B)=gr C)=gr U)=gr V)=gr

=

=3

El teorema de Dirac nos ayuda a

que se trata de un grafo hamilton

un ciclo hamiltoniano)


12/25

2) El grafo tiene 5 vrtices, n=5

2=

5

2= 2.5

gr(A)=gr(B)=3

gr(C)=gr(D)=gr(E)=2 < 2.5

No se puede concluir que se

encontrar un ciclo Hamiltoni

Pero al analizar el grafo se ve no se puede acabar en el ladoque se empieza por tanto no

hamiltoniano.


13/25

La condicin es suficiente pero no nec

como muestra el siguiente ejemplo:


14/25

Teorema de Ore

Sea G=(V,E) un grafo no dirigido con al menos 3 v

|V| = n 3.Si para cada pareja de vrtices no adyacentes x, yque

gr(x) + gr(y) n,

entonces el grafo es Hamiltoniano.


15/25

Ejemplo:En este grafo de n= las parejas de vrticesadyacentes son:

A,E

gr(A) +gr(E)=3+2 5

C,E

gr(C) +gr(E)=3+2 5

Vemos que la condicinecesaria se cumple ppodemos asegurar que

de un ciclo hamiltonia

B,D

gr(B) +gr(D)=3+3 5 =


16/25

Ejemplos En este grafo de n= 5 vrticparejas de vrtices no adyac

son: C,D); D,E); C,E); A,B)

C,D

gr C) +gr D)=2+2=4

Documents

GRAFOS HAMILTONIANOs