Tarea 2 de grafo

UNIVERSIDAD NACIONAL DEL CALLAO Grafos Eulerianos Teorema de Euler G (conexo) es euleriano ⇔ Todos los vértices son pares ⇒ G=(V,A) euleriano ⇓
a3
a4

TEORIA DE GRAFOS

a1

a2

Existe circuito euleriano {v,....,v}

a
a2k
-1

2k

El vértice tiene valencia par Lema 1: Si de un grafo con todos sus vértices pares eliminamos las aristas de un ciclo, el grafo resultante sigue teniendotodos sus vértices pares. G=(V,A) ⇒ vértices pares Demostración C ciclo en G=(V, A) v ∉ ⇨ ∂(v) no cambia v ∈V ( ∂(v) par ) ⇨ v ∊ ⇨ ∂(v) se reduce en 2 unidades v ∊ V sigue siendo par Lema 2: En un grafo conexo, con todos sus vértices pares (y valencias mayores que cero), todo vértice está contenido en un ciclo no trivial. Demostración: v∊ V v1 par v2 par v3 par Ciclo: {v, v1 , v2 , v3 , ... , v}v3 v v1

v2

GUISSELA ROMERO SUCA

UNIVERSIDAD NACIONAL DEL CALLAO

TEORIA DE GRAFOS

Lema 3: Si de un grafo conexo quitamos las aristas de un ciclo, en cada componente conexa del grafo resultante hay, al menos, un vértice del ciclo. Demostración: G

C

G

H

v

c

h

Algoritmo de Euler: P.1 Leemos el grafo G conexo con todos los vértices pares P.2 C = {v}, siendo v unvértice cualquiera de G P.3 Mientras que en G queden aristas P.3.1 Sea v un vértice de C, no aislado en G P.3.2 Sea D un ciclo empezando en v P.3.3 Eliminar de G las aristas de D P.3.4 Insertar D en C por el vértice v P.4 Retorna C

⇐ Lema 3 ⇐ Lema 3 ⇐ Lema 2 ⇐ Lema 3 y Lema 1

GUISSELA ROMERO SUCA

UNIVERSIDAD NACIONAL DEL CALLAO EJEMPLO : Algoritmo de Euler: P.1 Leemos el grafo G conexo contodos los vértices pares P.2 C = {v}, siendo v un vértice cualquiera de G P.3 Mientras que en G queden aristas P.3.1 Sea v un vértice de C, no aislado en G P.3.2 Sea D un ciclo empezando en v P.3.3 Eliminar de G las aristas de D P.3.4 Insertar D en C por el vértice v P.4 Retorna C

TEORIA DE GRAFOS

a b e h c D {a,b,e,a} f g d

Paso 2 3.1-3.2 3.3-3.4 3.1-3.2 3.3-3.4 3.3-3.2 3.3-3.4 3.1-3.23.3-3.4 4 h c a a a

v {a}

C

{a,b,e,a} {a,c,g,f,a} {a,c,g,f,a,b,e,a} {c,b,h,c} {a,c,b,h,c,g,f,a,b,e,a} {a,c,b,h,e,f,d,g,h,c,g,f,a,b,e,a} {a,c,b,h,e,f,d,g,h,c,g,f,a,b,e,a} {h,e,f,d,g,h}

Teorema: Un grafo conexo admite un recorrido euleriano (pero no un circuito euleriano) si, y sólo si, tiene exactamente dos vértices de valencia impar.

a x b

G

El nuevo grafo G’ es eulerianoCircuito euleriano: {x , a , v1, .... , vp , b , x } en G’ Recorrido euleriano: {a , v1, .... , vp , b } en G

GUISSELA ROMERO SUCA

UNIVERSIDAD NACIONAL DEL CALLAO

TEORIA DE GRAFOS

Teorema: Un grafo conexo admite un recorrido euleriano (pero no un circuito euleriano) si, y sólo si, tiene exactamente dos vértices de valencia impar. Algoritmo de Euler-1: P.1 Leemos el grafo G con todos losvértices pares excepto a y b P.2 Añadimos un vértice x y las aristas {x,a} y {x, b} P.3 C = {x} P.4 Mientras que en G queden aristas P.4.1 Sea v un vértice de C, no aislado en G P.4.2 Sea D un ciclo empezando en v P.4.3 Eliminar de G las aristas de D P.4.4 Insertar D en C por el vértice v P.5 Retorna C-{x} Teorema de Euler para digrafos: Un digrafo G(V,A) débilmente conexo es euleriano si, y sólo si,todos sus vértices tienen el mismo grado de entrada que de salida: ∀ v ∊ V , ∂e(v) =∂s(v) Recorrido euleriano en digrafos: Un digrafo G(V,A) débilmente conexo admite un recorrido euleriano si, y sólo si, todos sus vértices tienen el mismo grado de entrada que de salida, excepto dos de ellos, en uno de los cuales el grado de salida es una unidad superior que el de entrada, mientras que en el otroocurre lo contrario. ∀v∊V-{a,b} , ∂e(v) =∂s(v) , ∂e(b) =∂s(b)+1, ∂s(a) = ∂e(a)+1

Grafos hamiltonianos Condiciones necesarias de grafo hamiltoniano: *Si un grafo G = (V,A) es hamiltoniano entonces es conexo. *Si un grafo G = (V,A) es hamiltoniano entonces (G) 2. *Si un grafo G = (V,A) es hamiltoniano entonces es conexo y no tiene vértices de corte. *Si un grafo G = (V,A) es hamiltoniano...