Circuito de Euler

Polito
Circuito de Euler
Leonard Euler – matemático suizo que resolvió el problema de que un grafo tuviese un solo camino cerrado que contenga a cada una de las aristas.
El camino cerrado quecontiene exactamente cada una de las aristas se conoce como circuito de Euler o Euleriano
Teorema de Euler o Circuito de Euler
Todos los vértices de un grafo conexo tienen valencia o grado par,entonces el grafo tiene un circuito Euleriano.
Euler demostró que un grafo que tiene un circuito Euleriano tiene valencia par en todos sus vértices. Si exactamente dos de los vértices son impares (y elresto es par) entonces es un camino Euleriano.
PASES Y CIRCUITOS EULERIANOS (DE EULER)
Definición:
Un paseo de Euler (Euleriano) es un camino que incluye todos los lados - y por lo tanto todos losvértices - de un grafo dado, una y solo una vez.
Ingrid
Definición:
Un circuito de Euler (Euleriano) es un circuito cerrado que incluye todos los lados - y por lo tanto todos los vértices - de ungrafo dado una y solo una vez.

Condiciones para saber si un grafo dado tiene un paseo o circuito de Euler.
1) Un grafo no dirigido G tiene un paseo de Euler si y solo si tiene cero o dos vértices devalencia impar.
2) Si un grafo no dirigido G tiene un circuito de Euler entonces todo vértice de G tiene valencia par, además de ser conexo.
3) Si G es un grafo no dirigido con vértices {v1, v2,...,vn} y la suma (v1), (v2),..., (vn) es par, entonces el grafo tiene un circuito de Euler.
4) Un grafo G tiene un camino de Euler de v ≠ w si y solo si v y w son los únicos vértices de valenciaimpar.
Ejemplo: 
Verificar si los siguientes grafos no dirigidos tienen un paseo o circuito de Euler.

Paseo de Euler
SI
Si
Si
Circuito de Euler
No
Si
No
 

Paseo de Euler
Si
Si
Circuitode Euler
No
Si










Ciclo de Euler: Recorre todas las aristas del grafo sin repetir ninguna.
Teorema: Sea G un grafo (finito y conexo).
Valeria
(a) la suma de las valencias de...