Grafos - Camino De Euler

GRAFOS – CAMINO DE EULER
INTRODUCCIÓN
Esta guía pretende ayudarlo a mejorar su comprensión y desarrollar habilidades para entender la estructura de datos no lineal denominada grafos y de manera especial cómo se encuentra en un grafo un camino de Euler.
Una estructura de datos no lineal se caracteriza por que en ella no existe una relación de adyacencia, entre sus elementos, es decir, unelemento puede estar relacionado con cero, uno o más elementos. Una de las estructuras no lineales más generales es el grafo donde sus nodos pueden relacionarse de cualquier manera sin una relación de orden predefinida.
¿QUÉ ES UN GRAFO?

Un grafo G es un conjunto finito, no vacío de vértices V(G) y un conjunto de aristas E(G) que puede ser vacío formado por pares no ordenados de elementospertenecientes a V(G). Solo se establecerá un orden cuando se hable de grafos dirigidos y a las aristas se las denomina arcos.
Son aquellos que tienen un número arbitrario de conexiones en cada nodo. Esto hace que se pierda la noción de jerarquía que había en los arboles para tener una estructura más libre y general.

A continuación se encuentra la terminología generalmente utilizada para grafos:* Nodo: Un nodo, al igual que en los arboles, representa a una unidad de la estructura de grafos que puede contener un objeto y que puede también estar conectado a otros nodos.
* Arista: La arista es el artificio que permite crear una relación entre dos nodos. Las aristas pueden también tener dirección y peso. Si no tienen dirección se sobrentiende que la relación es de ambos lados
*Camino: Es una lista de nodos. Entre los nodos, deben existir relaciones (aristas) para que tengamos un camino conexo.
* Grafo dirigido: Cuando las aristas del grafo tienen dirección.

Los grafos se van complicando a medida de que se coloquen o no diferentes pesos en los arcos y si tienen o no dirección. De la misma manera, los nodos de un grafo no tienen por qué estar conectados forzosamenteentre si y puede un grafo tener varias componentes conexas.
CONCEPTOS CLAVES

* Camino o Trayectoria: sucesión de vértices con la propiedad de que cada vértice es adyacente al siguiente y tal que en la correspondiente sucesión de aristas todas son distintas.

* Circuito o camino cerrado: cuando un camino comienza y termina en el mismo vértice.

* Grado de un vértice: En un grafo nodirigido es el número de aristas que llegan al él. En grafos dirigidos se distingue entre grado de entrada y salida del vértice.

* Longitud del camino: Es el número de aristas o arcos que contiene el camino.

* Grafos Conexos: Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Un grafo G se dice conexo si cadapar de vértices está unido al menos por un camino.


* Grafos Dirigidos (Digrafos): En estos grafos, las aristas que comunican dos nodos tienen un único sentido. Gráficamente se expresa con flechas que indican el sentido de la relación entre cada par de nodos.

* Tamaño y orden de un grafo: El orden de un grafo G es el número de vértices del grafo y tamaño es el número de aristas. p =orden (G) = | V (G) |.q = tamaño (G) = | E (G) |.

CAMINO DE EULER

INICIOS

EL PROBLEMA DE LOS SIETE PUENTES DE KONIGSBERG:
En la ciudad alemana de Koenigsberg (en la época soviética, Kaliningrado) siete puentes atravesaban el río Plegel en su curso sinuoso por la ciudad. Sencillos ciudadanos se preguntaban: ¿Cómo puede una persona planear su paseo del domingo en la tarde, de modo quecruce una sola vez cada puente?
Así, estos siete puentes del siglo xviii proporcionaron el material para uno de los más célebres problemas de las matemáticas. Siendo Euler quien en 1735 presentó la solución a la Academia Rusa de San Petersburgo.

TEOREMA DE EULER
¿Existirá un circuito en el grafo G que recorra todos los arcos una sola vez?
Existe un circuito euleriano en un grafo si y sólo...