Primero empezaremos por definir algunos términos y conceptos que se deben conocer sobre los caminos.
Un camino
En un grafo G es una sucesión finita de vértices y aristas alternos, donde cada arista tiene por extremos los vértices adyacentes.
(v0, v0v1, v1, v1v2,..., vn-1, vn-1vn, vn)
A v0 y vn se les denomina extremos del camino.
Es el número de aristas que contiene.
Los extremos coinciden, v0=vn, son el principio y el final del grafo
En un grafo, un camino puede expresarse por la sucesión de vértices
(v0, v1,..., vn-1, vn)
En la sucesión de vértices no hay ninguno repetido.
Camino Euleriano
Inicio del problema
El origen de la teoría de los caminos eulerianos fue planteado y resuelto por el propio Leonhard Euler en 1736 en un problema que tiene el nombre de Siete puentes de la ciudad de Königsberg (Prusia oriental en el siglo XVIII y actualmente, Kaliningrado, provincia rusa) dando origen a la Teoría de los grafos.
El problema se enuncia de la siguiente forma: Dos islas en el río Pregel, en Königsberg se unen entre ellas y con la tierra firme mediante siete puentes. ¿Es posible dar un paseo empezando por una cualquiera de las cuatro partes de tierra firme, cruzando cada puente una sola vez y volviendo al punto de partida?
Euler enfocó el problema representando cada parte de tierra por un punto y cada puente, por una línea, uniendo los puntos que se corresponden. Entonces, el problema anterior se puede trasladar a la siguiente pregunta: ¿se puede recorrer el dibujo sin repetir las líneas?
Euler demostró que no era posible puesto que el número de líneas que inciden en cada punto no es par (condición necesaria para entrar y salir de cada punto, y para regresar al punto de partida, por caminos distintos en todo momento).
- Un grafo no dirigido contiene un ciclo euleriano si y sólo si (1) es conexo y (2) cada vértice es de grado par.
- Un grafo no dirigido contiene un camino euleriano si y sólo si (1) es conexo y (2) todos menos dos vértices son de grado par. Estos dos vértices serán los puntos de inicio y final de la ruta.
- Por último, un grafo dirigido contiene un camino euleriano si y sólo si (1) es conexo y (2) todos menos dos vértices tienen el mismo grado y estos dos tienen sus vértices en grados diferentes
Pues al realizar este proyecto se me hizo un poco difícil ya que no encontraba la información necesaria para realizarlo pero al final encontré la información que requería.
ResponderEliminarEn cuanto al trabajo creo que lo hice bien aunque me falto un poco mas de análisis pero lo que hice creo que esta bien.
Que triste que nadie te comentó nada :(
ResponderEliminar