Estudiante

Arturo Díaz Pérez

Análisis y Diseño de Algoritmos

Teoría de Gráficas
Arturo Díaz Pérez
Sección de Computación
Departamento de Ingeniería Eléctrica
CINVESTAV-IPN
Av. Instituto Politécnico Nacional No. 2508
Col. San Pedro Zacatenco
México, D. F. CP 07300
Tel. (5)747 3800 Ext. 3755
e-mail: adiaz@cs.cinvestav.mx

Análisis y Diseño de Algoritmos

Graph-1

Un Problema
¿Puededibujar la siguiente figura sin despegar el lápiz y
sin remarcar (pasar más de una vez por una línea ?

Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

Graph-2

1

Arturo Díaz Pérez

Otro Problema
¿Qué tal con esta?

Análisis y Diseño de Algoritmos

Graph-3

Nuevo Problema

ßLos residentes de Köniesberg, Alemania, se
preguntaban si era posible hacer unrecorrido de su
villa cruzando cada uno de los puentes sobre el río
Presel solo una vez
Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

Graph-4

2

Arturo Díaz Pérez

Otro Problema

F Lenhardt Euler (1736). Padre de la teoría de gráficas
ß Se imaginó solo lo que es esencial para el problema
ß ¿Es posible inicial en algún nodo, hacer un recorrido pasando
porcada puente una sola vez y terminar en el nodo inicial ?
Graph-5

Análisis y Diseño de Algoritmos

Otro Problema
1
1

4

2
2

4
3

3

FLenhardt Euler (1736). Padre de la teoría de gráficas
ß Se puede redibujar la gráfica siempre y cuando para cada arco
entre un par de vértices i,j se coloca un arco en la gráfica
redibujada sobre los vértices correspondientes
ß Euler demostróque en la gráfica de arriba no se puede encontrar
el recorrido buscado. ¿Puede ver por qué?
Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

Graph-6

3

Arturo Díaz Pérez

Recorridos de Euler
ß Un recorrido en una gráfica es llamado un recorrido de Euler si
inicia y termina en el mismo lugar y utiliza cada arco
exactamente una sola vez
ß Un recorrido en unagráfica es llamado un camino de Euler si
usa cada arco exactamente una sola vez

Graph-7

Análisis y Diseño de Algoritmos

Recorridos de Euler
F Si una gráfica tiene un recorrido de Euler se dice que es
una gráfica Euleriana
F Para nuestro ejemplo, se tiene que mostrar que la
gráfica no es Euleriana
1

4

Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

23

Graph-8

4

Arturo Díaz Pérez

Definiciones
F Una gráfica es conectada si es posible ir de cualquier
vértice a cualquier otro vértice
F Dos nodos (vértices) son adyacentes si hay al menos un
arco entre ellos
F El grado de un vértice es el número de arcos que salen de
él.

Grado 5

Gráfica conectada
Análisis y Diseño de Algoritmos

Cada ciclo cuenta por 2
Graph-9Teorema de Euler
¬ Una gráfica es Euleriana si y solo si es conectada y no
tiene vértices de grado impar.
- Una gráfica tiene un camino de Euler de un nodo a a
algún otro nodo b si y solo si a ≠ b y a y b son los únicos
nodos de grado impar.

Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

Graph-10

5

Arturo Díaz Pérez

Prueba del Teorema de Euler
F ⇒ ¬, ßSuponga que una gráfica G Euleriana tiene un camino C de un
nodo a a un nodo b, no necesariamente distintos.
ß G debe ser conectada ya que el camino (recorrido) de Euler
alcanza cada nodo de G
ß Para cada nodo de G diferente de a y de b, C usa un arco para
llegar y un arco para salir de un nodo. Así el grado de cada
nodo, diferente a a y b, debe ser par.
ß Si a = b, entonces, tiene también ungrado par.
ß Si a ≠ b, entonces, ellos tienen grado impar.

Graph-11

Análisis y Diseño de Algoritmos

Prueba del Teorema de Euler
F⇐ ß Suponga que G es conectada. Si no hay vértices de grado
impar, escoja a = b
ß Si existen dos vértices de grado impar, llámelos a y b
ß Inicie en a, tome un camino W1 hasta que ya no pueda continuar
más; debe estar en b. Si no hay un vértice en W1 que...