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 aristasde 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
llamasemieuleriano.

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 vezCircuito 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 losvé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 enel 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 existeun 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 denominado... [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.