caminos Eulerianos y Hamiltonianos

Páginas: 8 (1899 palabras) Publicado: 30 de octubre de 2013
CAMINOS Y CICLOS DE EULER Y DE HAMILTON
1.- CAMINOS Y CICLOS EULERIANOS
¿Se puede dibujar la siguiente figura, empezando y terminando en el mismo punto, sin levantar el lápiz del papel?

La respuesta es que no es posible.
Königsberg es famosa por sus siete puentes y por el problema que consistía en saber si una persona podría cruzar todos los puentes una sola vez, volviendo al lugar dedonde partió.

En 1736 Leonhard Euler publicó el artículo “Solutio problematis ad geometriam situs pertinentis” (La solución de un problema relativo a la geometría de posición), en el cual resolvió lo que se conocía con el nombre de “Problema de los puentes de Königsberg”. Este trabajo se considera el primer artículo sobre lo que hoy conocemos como la Teoría de grafos.
Fue Euler quien encontró quetal camino era imposible, sin embargo no hizo una demostración de estas afirmaciones.
No fue hasta 1873 que se publicó una demostración. Su autor, Hierholzer, que desconocía, aparentemente, el trabajo de Euler.
Hoy en día se trata el Problema de los puentes de Königsberg representando el mapa de la figura anterior por un multígrafo en el que cada una de las zonas de la ciudad estabarepresentada por un vértice y cada puente por una arista que unía los vértices correspondientes a las zonas conectadas por dicho puente, aunque esto no fue lo que hizo Euler. Hierholzer, sin embargo, pudo haber planteado el problema de esta forma, ya que el definió, básicamente, el concepto de grafo cuando hablaba de un “sistema de líneas entrelazadas”.


1.1 Camino de Euler
Un camino euleriano es uncamino que pasa por cada arista una y solo una vez, puede entenderse también como una forma de dibujar el grafo sin levantar el lápiz del papel y sin pintar dos veces la misma arista.

1.2 Ciclo de Euler
Un ciclo de un grafo o multígrafo se dice de Euler si pasa por todos los vértices recorriendo cada arista exactamente una vez, siendo condición necesaria que regrese al vértice inicial de salida.1.3 Grafo Euleriano
Un grafo que admita un ciclo de Euler se denomina grafo euleriano.

1.4 Primer Lema
Una condición necesaria para que un grafo o multígrafo sea Eureliano es que todos sus vértices sean de grado par, el grafo sea conexo y no tenga algún vértice de grado impar, es decir, si en un grafo G existe, al menos, un vértice de grado impar, entonces G no es Euleriano.



1.5Segundo Lema

Una condición necesaria para que un grafo o multígrafo admita un camino de Euler es que el número de vértices de grado impar sea 2 o ninguno.



“Si G es un grafo con un camino de Euler, entonces el número de vértices de grado impar es 2 o ninguno”.

1.6 Tercer Lema

Si G es un grafo en el que todos sus vértices tienen grado par, entonces para cada par de vértices adyacentesde G, puede encontrarse un ciclo que contiene a la arista que forman ambos.

1.7 Teorema

Un grafo o multígrafo G = (V, A) es euleriano si, y solo si es conexo y todos sus vértices tienen grado par.

Demostración:

Sea G = (V, A) un grafo o multígrafo.

“Solo sí.” En efecto, supongamos que G admite un ciclo de Euler.
Dados dos vértices cualesquiera de G, u y v, la parte del ciclo quecomienza en u y acaba en v es un camino que une u con v, luego G es conexo.

Además, el primer lema asegura que todos los vértices de G tienen grado par.



1 Sean u y v dos vértices adyacentes de G. Como G tiene todos sus vértices de grado par, el tercer lema asegura la existencia de un ciclo γ1 que contiene a la arista uv. Pues bien, sea G’ = (V, A’) el subgrafo de G que resulta eliminandolas aristas que están en γ1, es decir,

A’ = A \ {aristas de γ1}.

G’ tiene todos sus vértices de grado par (o cero) ya que en el ciclo γ1 cada vértice habrá aportado dos aristas, luego si los vértices de G eran de grado par, los de G seguirán siéndolo.

− Si A’ = ∅, entonces γ = γ1 es el ciclo de Euler que buscamos y la demostración habrá concluido.

− Si A’ ≠ ∅, continuamos el proceso....
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • Eulerianos y hamiltonianos
  • Caminos Hamiltonianos
  • Aplicación De Los Caminos Hamiltonianos
  • Grafos Hamiltonianos
  • numero euleriano
  • Integrales eulerianas
  • lagrangiana y euleriana
  • Principio Hamiltoniano

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS