EulerIanos

7/24/2019 EulerIanos

1/9

Captulo 5

Grafos eulerianos


2/9

Definicin de grafo euleriano:

Un grafo se dice euleriano si

contiene un circuito euleriano.

Un circuito euleriano es un circuito

simple que recorre todas las aristas

del grafo.


3/9

Ejemplos

1. El ciclo Cn es euleriano.

2. K2,2 es euleriano.


4/9

esultado de Euler

!eorema: "n multigrafo G se dice euleriano si #

solamente si todos sus $%rtices son de grado

par # todas sus aristas est&n en la misma

componente cone'as (cone'o sal$o $%rticesaislados).

*i es euleriano entonces el grado de cada $%rticees par puesto +ue el circuito euleriano (+ue

contiene todas las aristas) entra # sale de %l.


5/9

El recproco es constructi$o

-aso 1: uscamos un circuito simple en G

(/a# +ue demostrar +ue e'iste).

-aso 2: orramos de G dic/o circuito # los$%rtices +ue se +ueden aislados.

-aso 0: ol$emos a empear con el

nue$o grafo.


6/9


7/9

Continuamos

-aso 3: 4nsertamos adecuadamente el

circuito para ir constru#endo el circuito

euleriano (+ue $a creciendo).


8/9


9/9

E'iste el circuito simple

!omamos cual+uier $%rtice $.

!omamos un camino simple de longitud

m&'ima partiendo de $.

$u1,u2,6,us. *i us$ fin. *i no, e'iste un

$%rtice +ue es ad#acente con us (pues su

grado es par), contradiciendo +ue la

longitud es m&'ima.

Documents

EulerIanos