Eulerianos y hamiltonianos
Páginas: 2 (436 palabras)
Publicado: 30 de mayo de 2010
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...
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...
Leer documento completo
Regístrate para leer el documento completo.