17237313 grafos-eulerianos

Teoría de GrafosUnidad Académica Elementos Discretos

Elementos DiscretosFa

culta

dFa

culta

dde

de

Cie

ncia

sC

ienc

ias

y y Te

cnol

ogTe

cnol

ogíí aa

Dep

arta

men

to d

e D

epar

tam

ento

de

Com

puta

ciC

ompu

taci

óó nn

Teoría de Grafos:

Grafos EulerianosTeoría de Grafos:

Grafos Eulerianos


Los Puentes de Königsberg:Königsberg (populosa y rica ciudad de la Prusia Oriental), nombre antiguo de la actual ciudad de Kaliningrado (Rusia).

Problema de los Puentes de Königsberg:

Problema delos Puentes de

Königsberg

La solución deEuler

Definición deGrafo

Euleriano

Teorema delCircuito

Euleriano

Demostracióndel Teorema

Corolario delCamino

Euleriano

El río Pregel atraviesa la ciudad y existen 2 islas en el medio del río, conectadas entre sí y con las márgenes del río, a través de 7 puentes.


Los Puentes de Königsberg:Protagonistas de uno de los problemas de los matemáticos del siglo XVIII.

Problema de los Puentes de Königsberg:


Königsberg


Definición deGrafo

Euleriano

Teorema delCircuito

Euleriano


Corolario delCamino

Euleriano

Problema:¿Es posible partir de un punto de la ciudad y recorrer cada puente

una sola vez regresando al punto de partida.?


Euler:En 1736, el matematico suizo Leonhard Eulermodelo el problema usando un grafo G = (V, A)donde: V = {las islas y las dos márgenes del río} y A = {los puentes}

La solución de Euler:


Königsberg


Definición deGrafo

Euleriano

Teorema delCircuito

Euleriano


Corolario delCamino

Euleriano

Problema:¿Existirá un circuito en el grafo G que recorra todos los arcos una

sola vez?

1707 - 1783

isla 1 isla 2

margen 1

margen 2

G = (V, A)

Respuesta:Euler demostró que no existe dicho circuito.


Construcción de puentes:Si se construyeran dos puentes el problema tendría solución afirmativa.

Euler:Para que existiera el circuito buscado, todos los vértices de G debían ser de grado par (en este caso todos son de grado impar).

La solución de Euler:


Königsberg


Definición deGrafo

Euleriano

Teorema delCircuito

Euleriano


Corolario delCamino

Euleriano

G = (V, A)3

3

5 3

4

G = (V, A)4

6 4


Definiciones:Camino euleriano:Es un camino que recorre todos los arcos del grafo una sola vez. Por lo tanto, es un camino simple que transita por todos los arcos del grafo.

Definición de Grafo Euleriano:


Königsberg


Definición deGrafo

Euleriano

Teorema delCircuito

Euleriano


Corolario delCamino

Euleriano

Circuito euleriano:Es un camino euleriano, donde el vértice de partida coincide con el vértice de llegada.

Eje

mpl

os:

G1 = (V1, A1, ϕ)

C = (e1, e2, e3, e4, e5, e6, e7, e8)circuito euleriano

e1 e3

e2

e4

e5

e6

e7

e8

G = (V, A, ϕ)

C = (e2, e3, e4, e5, e6, e7, e8, e1, e9, e10, e11)camino euleriano

e1 e3

e2

e4

e5

e6

e7

e8

e9

e10

e11

3 44

4

4 3

2 42

2

4 2


Por

lo ta

nto

Grafo Euleriano:Un grafo es euleriano si contiene un camino o un circuito euleriano.

Definición de Grafo Euleriano:


Königsberg


Definición deGrafo

Euleriano

Teorema delCircuito

Euleriano


Corolario delCamino

Euleriano

G1 = (V1, A1, ϕ)

C = (e1, e2, e3, e4, e5, e6, e7, e8)circuito euleriano

e1 e3

e2

e4

e5

e6

e7

e8

G = (V, A, ϕ)

C = (e2, e3, e4, e5, e6, e7, e8, e1, e9, e10, e11)camino euleriano

e1 e3

e2

e4

e5

e6

e7

e8

e9

e10

e11

3 44

4

4 3

2 42

2

4 2

euleriano euleriano

No se puede construir uncamino euleriano

G = (V, A)3

3

5 3

no es euleriano


Teorema:Para cualquier grafo G = (V, A).Si G es conexo y todos sus vértices son de grado par, entonces G tiene un circuito Euleriano.

Teorema del Circuito Euleriano:


Königsberg


Definición deGrafo

Euleriano

Teorema delCircuito

Euleriano


Corolario delCamino

Euleriano

grado par grado impar


Demostración:Por inducción y por construcción.

Demostración del Teorema:


Königsberg


Definición deGrafo

Euleriano

Teorema delCircuito

Euleriano


Corolario delCamino

Euleriano

Hipótesis:Sea G = (V, A) un grafo, tal que:(i) G es conexo,(ii) G tiene todos sus vértices de grado par

Tesis:G tiene un circuitoeuleriano

Observaciones:El problema del circuito euleriano radica en los arcos de G, por eso se va a hacer inducción sobre el número de arcos de G, es decir, sobre |A| = m.

La intención es que al ir variando m, si el grafo cumple las hipótesisdel teorema (G es conexo y todos sus arcos son de grado par) entonces se compruebe que G tiene un circuito euleriano.


Inducción: Colocamos el teorema como la propiedad a probar.P(m): Dado un grafo G = (V, A) con |A| = m. Si G es conexo y todos los vértices de G son de grado par, entonces G contiene un circuito Euleriano.



Königsberg


Definición deGrafo

Euleriano

Teorema delCircuito

Euleriano


Corolario delCamino

Euleriano

La inducción se hace para |A| ≥ 3

Se descartan los casos |A| = 1 y |A| = 2, porque con esa cantidad de arcos, los grafos que satisfacen las hipótesis no son simples.

no son grafos simples


Inducción: Se usará la forma fuerte de inducción.P(m): Dado un grafo G = (V, A) con |A| = m. Si G es conexo y todos los vértices de G son de grado par, entonces G contiene un circuito Euleriano.



Königsberg


Definición deGrafo

Euleriano

Teorema delCircuito

Euleriano


Corolario delCamino

Euleriano

Caso Base: Probar P(m) para m = 3P(3): Dado un grafo G = (V, A) con |A| = 3. Si G es conexo y todos los vértices de G son de grado par, entonces G contiene un circuito Euleriano.

El grafo G = (V, A) con |A| = 3, que cumple las hipótesis es:

Por lo tanto, P(3) es verdadero.

En G existe el siguiente circuito euleriano:C = (v1, v2, v3, v1)

v1

v2

2

22v3


Paso Inductivo:

Hipótesis Inductiva:Asumimos como cierto P(3) ∧ P(4) ∧ ... ∧ P(k-1), es decir, asumimos que:Para cualquier grafo G = (V, A) con |A| < k. Si G es conexo y todos los vértices de G son de grado par, entonces G contiene un circuito Euleriano.



Königsberg


Definición deGrafo

Euleriano

Teorema delCircuito

Euleriano


Corolario delCamino

Euleriano

Tesis Inductiva: Debemos probar P(k), es decir:Dado un grafo G = (V, A) con |A| = k. Si G es conexo y todos los vértices de G son de grado par, entonces G contiene un circuito Euleriano.


Paso Inductivo: Aquí se usa el Proceso de construcción.

Estrategia:Desarrollar la tesis,

partiendo de su antecedente (hipótesis de la tesis), por construcción se hace aparecer la hipótesis inductiva,

se sustituye y se trata de llegar al consecuente de la tesis.



Königsberg


Definición deGrafo

Euleriano

Teorema delCircuito

Euleriano


Corolario delCamino

Euleriano

Antecedente de la tesis inductiva Sea G = (V, A) un grafo con |A| = k, tal que:(i) G es conexo,(ii) G tiene todos sus vértices de grado par

Consecuente de la Tesis inductiva:G tiene un circuitoeuleriano

Asumimos entonces que disponemos de un grafo G = (V, A), con |A| = k arcos, que es conexo y todos sus vértices son de grado par.



Construcción:



Königsberg


Definición deGrafo

Euleriano

Teorema delCircuito

Euleriano


Corolario delCamino

Euleriano

(1) Conseguir un circuito cualquiera en G, denominándolo Cprinc.

Si Cprinc es eulerianoeuleriano entoncesla demostración termina

sino continuamos:

inicio

G4 G2

G1

G3

G5

(2) Quitar de G los arcos del circuito Cpric.Se generan una o varias componentes conexas en G (p ≥ 1).

(3) Cada componente conexa cumple que:tiene cantidad de arcos menor que k, es conexa y todos sus vértices son de grado par. Por hipótesis inductiva, cada componente conexa posee un circuito circuito eulerianoeuleriano.

(1)

inicio

(2)

G4 G2

G1

G3

G5

(3)

Ilustración:



Construcción:



Königsberg


Definición deGrafo

Euleriano

Teorema delCircuito

Euleriano


Corolario delCamino

Euleriano

(4) Escoger p vértices de Cpric: uuii , uno por cada componentes conexas, i ∈ {1, 2, ..., p}en el orden en que fueron visitadas las componentes conexas.

(5) Armar el circuito circuito eulerianoeuleriano de G, ensamblando el circuito Cpric con los circuitos circuitos eulerianoseulerianos de las componentesconexas, en el orden que son visitadaspor el circuito Cpric.

Ilustración:(4)

G4 G2

G1

G3

G5

u4 u2

u1

u3

u5

inicio

u4 u2

u1

u3

u5

(5)

inicio


G = (V, A)

Corolario del Camino Euleriano:


Königsberg


Definición deGrafo

Euleriano

Teorema delCircuito

Euleriano


Corolario delCamino

Euleriano

Corolario:Para cualquier grafo G = (V, A).Si G es conexo y todos sus vértices son de grado par o exactamente dos son de grado impar, entonces G tiene un camino Euleriano.

En G existen exactamentedos vértices de grado impar,

entonces G tiene un camino euleriano

2

4 4

3 3

Ejemplo:

G = (V, A)

Extraemos un camino que inicie en uno de los vértices de grado impary que termine en el otro vértice de grado impar.

G = (V, A)

Queda componente conexa con un circuito

euleriano.Ensamblando ambos se

obtiene el camino camino eulerianoeuleriano.

17237313 grafos-eulerianos

Education