Caminos Eulerianos y la
Fórmula de Euler
Jornadas de Investigación en
Análisis Matemático dedicadas al
Tricentenario de Leonhard Euler
12 a 16 de noviembre de 2007
Guadalupe Rodrı́guez — Departamento de Ciencias Básicas
Francisco Zaragoza — Departamento de Sistemas
Universidad Autónoma Metropolitana Azcapotzalco
[email protected] y [email protected]
Caminos Eulerianos y la Fórmula de Euler – p. 1/24
Contenido
1. Caminos eulerianos.
(a) Gráficas eulerianas.
(b) Problema del cartero.
(c) Doble cubierta por ciclos.
2. Fórmula de Euler.
(a) Planaridad.
(b) Poliedros regulares.
(c) Coloración de mapas.
Caminos Eulerianos y la Fórmula de Euler – p. 2/24
El problema de los puentes (1736)
El problema es como sigue: en Koenigsberg
existe una isla llamada Kneiphof y el río que
la rodea se divide en dos ramas y esas
ramas son atravesadas por siete puentes.
Acerca de estos puentes se preguntó si
acaso alguien podría organizar una ruta de
modo que cruzara cada puente exactamente
una vez. Me dijeron que algunas personas
aseguraban que esto es imposible, mientras
que otras dudaban, pero que nadie
aseguraría que de hecho era posible.
Caminos Eulerianos y la Fórmula de Euler – p. 3/24
Los puentes de Koenigsberg
Caminos Eulerianos y la Fórmula de Euler – p. 4/24
Circuitos eulerianos
Un circuito de una gráfica es euleriano si
contiene a cada una de sus aristas
exactamente una vez.
Una gráfica es euleriana si tiene algún
circuito euleriano.
El problema general que nos interesa es el de
decidir si una gráfica dada es euleriana o no.
Supondremos que las gráficas son conexas.
Caminos Eulerianos y la Fórmula de Euler – p. 5/24
Gráficas eulerianas
(Euler 1736 y Hierholzer 1873) Una gráfica es
euleriana si y sólo si todos sus vértices tienen
grado par.
C C
g g
c d c d
h
A e D i A D
e
a b a b
f f
B B
Caminos Eulerianos y la Fórmula de Euler – p. 6/24
Gráficas dirigidas eulerianas
(Kőnig 1936) Una gráfica dirigida D es
euleriana si y sólo si los grados interno y
externo de cada vértice de D son iguales.
C C
g g
c d c d
h h
i A D i A D
e e
a b a b
f f
B B
Caminos Eulerianos y la Fórmula de Euler – p. 7/24
Gráficas mixtas eulerianas
(Ford y Fulkerson 1962) Una gráfica mixta M
es euleriana si y sólo si todo subconjunto S
de los vértices de M es par y balanceado.
C C
g g
c d c d
h h
i A D i A D
e e
a b a b
f f
B B
Caminos Eulerianos y la Fórmula de Euler – p. 8/24
El problema del cartero
(Mei Gu Guan 1960) Cuando el autor estaba
dibujando un diagrama para la ruta de un
cartero, él descubrió el siguiente problema:
Un cartero tiene que cubrir su ruta asignada
antes de regresar a la oficina postal.
El problema es encontrar la distancia más
corta que debe caminar el cartero.
Caminos Eulerianos y la Fórmula de Euler – p. 9/24
Recorridos de cartero
C C
g g
c d c d
A e D A e D
a b a b
f f
B B
Caminos Eulerianos y la Fórmula de Euler – p. 10/24
Sobre el problema del cartero
Se puede resolver eficientemente para
gráficas y gráficas dirigidas.
El problema es NP duro en gráficas mixtas.
Existen muchas variantes de este problema.
Para algunas de estas variantes es NP
completo decidir si existe solución factible.
Caminos Eulerianos y la Fórmula de Euler – p. 11/24
Doble cubierta por ciclos
Si se duplican todas las aristas de una gráfica
se obtiene una gráfica euleriana.
¿Existirá una doble cubierta por ciclos?
Szekeres y Seymour conjeturan que sí
(excepto para los contraejemplos obvios).
Caminos Eulerianos y la Fórmula de Euler – p. 12/24
Fórmula de Euler (1750)
En todo poliedro se cumple que c + v = e + 2.
c es el número de caras, v es el número de
vértices y e es el número de aristas.
En el cubo c = 6, v = 8 y e = 12.
Caminos Eulerianos y la Fórmula de Euler – p. 13/24
Gráficas aplanables
G = (V, E) gráfica y S superficie.
G está encajada si está dibujada en S sin que
se intersecten sus aristas.
Una gráfica es aplanable si se puede encajar
en el plano.
Caminos Eulerianos y la Fórmula de Euler – p. 14/24
Teorema de Euler
Sea G = (V, E) una gráfica aplanable y
conexa.
Sea C el número de caras de algún encaje
de G.
Entonces se cumple que
|V | − |E| + C = 2.
Caminos Eulerianos y la Fórmula de Euler – p. 15/24
Teorema de Kuratowski
Teorema de Euler ⇒ K5 , K3,3 no son gráficas
aplanables.
Teorema de Kuratowski: Una gráfica es
aplanable si y sólo si no contiene una
subgráfica homeomorfa a K5 o K3,3 .
Caminos Eulerianos y la Fórmula de Euler – p. 16/24
Poliedros regulares
Teorema (Pitágoras y Platón): Sólo existen
cinco poliedros regulares.
tetraedro cubo octaedro
dodecaedro icosaedro
Caminos Eulerianos y la Fórmula de Euler – p. 17/24
Creación de otras superficies I
Cilindro y banda de Möbius
Caminos Eulerianos y la Fórmula de Euler – p. 18/24
Creación de otras superficies II
Esfera, toro y botella de Klein
Caminos Eulerianos y la Fórmula de Euler – p. 19/24
Teorema de Poincaré
Consideremos un encaje simple de una
gráfica en una superficie S con |V | vértices,
|E| aristas y C caras.
Si S es una esfera con g asas, entonces
|V | − |E| + C = 2 − 2g.
Si S es una esfera con h bandas de Möbius,
entonces
|V | − |E| + C = 2 − h.
Caminos Eulerianos y la Fórmula de Euler – p. 20/24
Coloración de mapas
Dos países adyacentes deben tener colores
diferentes.
Conjetura: Se requieren a lo más 4 colores.
Teorema de los cuatro colores: Toda gráfica
aplanable se puede colorear con a lo más 4
colores.
Caminos Eulerianos y la Fórmula de Euler – p. 21/24
Teorema de Heawood
Sea Sg la esfera con g asas. Entonces
√
7 + 1 + 48g
χ(Sg ) ≤ .
2
Ringel y Youngs demostraron que se cumple
la igualdad para casi todas las superficies
cerradas.
La única excepción es la botella de Klein.
Caminos Eulerianos y la Fórmula de Euler – p. 22/24
Coloración Tierra Luna
1 1
3 4 2 3 4 2
7 7
8 8
6 6
5 5
Una partición de K8 en dos gráficas planas
Caminos Eulerianos y la Fórmula de Euler – p. 23/24
Al menos nueve colores
Esta gráfica fue propuesta por Sulanke:
K8
Y a lo mucho doce colores (usando Euler).
Caminos Eulerianos y la Fórmula de Euler – p. 24/24
