Ensayo de Recorridos y Grafos Eulerianos

Recorridos y Grafos Eulerianos

Los puentes de Königsberg incluían dos islas y 7 puentes. La Pregunta que se hacían sus habitantes era, si una persona inicia en cualquier lado y termina en otro podrá hacer todo este recorrido sin pasar dos veces por el mismo puente?. Los habitantes de este pueblo escribieron al suizo Euler para que les resolviera este problema, él lo planteo como un grafo . Euler demostró que esto es imposible hizo que las aristas sean los puentes y las islas los vértices.                                                              

[pic 1]

Como lo vemos es un multigrafo y sabemos que este es recorrible si la curva puede trazarse sin interrupciones y sin que pase 2 veces por alguna de las aristas : es decir, si existe un camino que incluya todos los vértices y use cada arista exactamente una vez. Tal camino debe ser  un recorrido (puesto que ninguna arista se usa dos veces), y se denomina recorrido atravesable o recorrible. Resulta por lo que hemos visto que es un multigrafo finito (finito si tiene un número finito de vértices y aristas) y conexo(ES CONEXO SI EXISTE un camino entre dos vértices).

Veamos como demostró Euler que este camino era imposible de hacer

Recordemos que un vértice es par o impar si su grado es un número par o impar. Suponga que un multigrafo es recorrible y que un recorrido atravesable no empieza o termina en un vértice P. Se afirma que P es un vértice par. Ya que siempre que el recorrido atravesable entra a P por una arista, siempre debe haber una arista no usada previamente por la cual el recorrido puede abandonar P. En consecuencia las aristas que inciden en P deben ser pares, por lo tanto P es un vértice par. Por consiguiente si Q es un vértice impar, entonces el recorrido atravesarle debe empezar o terminar en Q.

Un multigrafo con más de 2 vértices impares no puede ser recorrible. En nuestro ejemplo vemos que tenemos 4 vértices impares, de modo que cada puente se cruce solamente una vez.

GRAFO EULERIANO Se denomina a un  grafo euleriano si existe un recorrido atravesable cerrado que se lo denomina recorrido euleriano.

Teorema 3 de Euler. Un grafo conexo finito es euleriano sii cualquier vértice tienen grado par.

Corolario 4. Cualquier grafo conexo finito con dos vértices impares es recorrible. Un recorrido atravesable puede empezar en cualquier vértice impar y terminar en el otro vértice impar.

GRAFOS HAMILTONIANOS

En el anterior análisis se recalcan las aristas recorridas , aquí la atención se centra en la visita a los vértices

Un circuito Hamiltoniano

Es un camino cerrado que visita todos los vértices en G exactamente una vez. (Este camino cerrado debe ser un ciclo. Si G admite un círculo Hamiltoniano, entonces G se denomina Grafo Hamiltoniano. Observamos que un circuito de Euler recorre cada arista exactamente una vez, aunque puede repetir vértices, mientras que un circuito Hamiltoniano visita cada vértice exactamente una vez aunque puede repetir aristas En el siguiente ejemplo vemos uno que es Hamiltoniano pero no euleriano y viceversa.

Aunque resulta evidente solo los gafos conexos son  hamiltonianos, no hay ningún criterio simple para decir si un grafo es o no Hamiltoniano, como si lo hay para el caso delos grafos eulerianos, se cuenta con la siguiente condición suficiente.

Teorema 5. Sea G un grafo conexo con n vértices. Entonces G es Hamiltoniano si n ≥ 3 y n ≤ grd(v) para cada vértice v en G.

GRAFOS ETIQUETADOS Y PONDERADOS

Un grafo G se denomina grafo etiquetado si sus aristas y/o vértices son datos asignados de un tipo o del otro. En particular, G se denomina grafo ponderado si a cada arista e de G se asigna un número no negativo w(e) denominado peso o longitud de v. El peso (o la longitud) de un camino en tal grafo ponderado G se define como la suma de los pesos de las aristas en el camino. Un problema importante en teoría de grafos es encontrar el camino más corto; es decir, un camino de peso (longitud) mínimo(a), entre dos vértices arbitrarios dados.

GRAFOS COMPLETOS, REGULARES Y BIPARTIDOS

Hay muchos tipos distintos de grafos. Consideramos  tres: grafos completos, regulares y bipartidos.

Grafos completos

Un grafo G es completo si cualquier vértice en G está unido a todos los demás vértices en G. Por tanto, un grafo completo G debe ser conexo. El grafo completo con n vértices se denomina Kn.

Grafos regulares

Un grafo G es regular de grado k o k-regular si sus vértices tienen grado k, si todos los vértices tienen el mismo grado. Los grafos regulares conexos de grados 0, 1 o 2 se describen con facilidad. El grafo conexo 0-regular es el grafo trivial con un vértice y sin ninguna arista. El grafo conexo 1-regular es el grafo con dos vértices y una arista que los une. El grafo conexo 2-regular con n vértices es el grafo que consta de un solo n-ciclo. Los grafos 3-regular deben tener un número par de vértices, ya que la suma de los grados de los vértices es un número par (teorema 1). En general, los grafos regulares pueden ser bastante complicados. Por ejemplo, hay 19 grafos 3-regular con 10 vértices.

Grafos bipartidos

Un grafo G es bipartido si sus vértices V pueden partirse en dos subconjuntos M y N tales que cada arista de G une un vértice de M con un vértice de N. Por un grafo bipartido completo se entiende que cada vértice de M está unido a cada vértice de N; este grafo se denota por Km,n, donde m es el número de vértices en M y n es el número de vértices en N y, por razones de estandarización, se supone m ≤ n.   Resulta evidente que el grafo Km,n tiene mn aristas.

ÁRBOLES

Un grafo T se denomina árbol si T es conexo y T no tiene ciclos. Un bosque G es un grafo sin ciclos; por tanto, los componentes conexos de un bosque G son árboles. Un grafo sin ciclos es libre de ciclos. El árbol que consta de un solo vértice sin aristas se denomina árbol degenerado. Considere un árbol T. Resulta evidente que sólo hay un camino simple entre dos vértices de T; en caso contrario, los dos caminos formarían un ciclo. También:

...