GRAFOS, TRAYECTORIAS Y CICLOS EULERIANOS Y HAMILTONIANOS

POR:

JUAN CAMILO MARTINEZ CORONADO

FECHA:

19 / 04 / 2010

MATERIA:

MATEMATICA AVANZADA PARA LA INFORMATICA

PROFESOR:

ALVARO MONTOYA

MEDELLIN

INSTITUTO TECNOLOGICO METROPOLITANO

2010
Grafo Euleriano

Se denomina grafo euleriano, a un grafo conexo G que tiene una cola cerrada que
incluye todas las aristas de G.

Teorema de Euler: Un grafo es euleriano si y sólo si cada vértice es de grado
par. Si tiene exactamente dos vértices impares es recorrible (la cola no será cerrada) y se
llama semieuleriano.

A continuación se muestran ejemplos de grafos no eulerianos, semieulerianos y
eulerianos respectivamente.

[pic]

Trayectoria de Euler: es un camino que pasa por todo arco solo una vez

Circuito de Euler: es un ciclo que pasa por todo arco solo una vez

La solución al problema de existencia de ciclos de Euler se puede establecer mediante el grado de un vértice (es el numero dearcos que tiene ese vértice como extremo).

Teorema 1: Si una grafica G tiene un vértice de grado impar, entonces no puede existir un circuito de Euler en G.
Si G es una grafica conexa y todos los vértices tienen grado par, entonces existe un circuito de Euler en G.

Teorema 2: Si una grafica G tiene mas de dos vértices de grado impar, entonces no puede existir una trayectoria de Euler en G.
Si G es conexa y tiene exactamente dos vértices de grado impar, entonces existe una trayectoria de Euler en G. Cualquier trayectoria de Euler debe comenzar en un vértice de grado impar y terminar en el otro.

Ejercicios:

¿Es posible trazar las siguientes figuras sin levantar el lápiz?

Son Eulerianos:

No Son Eulerianos:

Grafo Hamiltoniano

Se denomina grafo hamiltoniano, si existe un camino cerrado que contiene todos
los vértices una sola vez (no tiene porque contener todas las aristas). Un grafo que posea
una trayectoria que pase a través de cada vértice es [continua]

Leer Ensayo Completo

Cite este ensayo

APA

(2010, 05). Eulerianos y hamiltonianos. BuenasTareas.com. Recuperado 05, 2010, de http://www.buenastareas.com/ensayos/Eulerianos-y-Hamiltonianos/368937.html

MLA

"Eulerianos y hamiltonianos" BuenasTareas.com. 05 2010. 2010. 05 2010 <http://www.buenastareas.com/ensayos/Eulerianos-y-Hamiltonianos/368937.html>.

MLA 7

"Eulerianos y hamiltonianos." BuenasTareas.com. BuenasTareas.com, 05 2010. Web. 05 2010. <http://www.buenastareas.com/ensayos/Eulerianos-y-Hamiltonianos/368937.html>.

CHICAGO

"Eulerianos y hamiltonianos." BuenasTareas.com. 05, 2010. consultado el 05, 2010. http://www.buenastareas.com/ensayos/Eulerianos-y-Hamiltonianos/368937.html.