3.5. APLICACIONES DE LOS GRAFOS
91
de cada vértice sea un número par. Como en el grafo asociado al problema de los puentes no
se cumple esa condición, entonces no existe un circuito de Euler.
Euler también mostró que el recíproco es válido para cierto tipo de grafos. Diremos que
un grafo es conexo si uno puede “viajar” entre dos vértices cualesquiera. Euler mostró que si
la valencia de cada uno de los vértices de un grafo conexo es par, entonces en el grafo existe
un circuito de Euler.
Consideremos ahora la siguiente situación.
D
D
!
4
A
!
C
3
7
!
A
5
C
6
B
!
1
2
B
El digrafo correspondiente lo hemos dibujado a la derecha. En este caso si existe un
circuito Euleriano. Por ejemplo,
1
2
3
4
5
6
7
A → B → C → D → A → B → C → A.
En la vida diaria surgen problemas donde se requiere construir circuitos Eulerianos. Considere, por ejemplo, el problema de conseguir una ruta para un cartero da tal manera que el
cartero recorra cada calle una sola vez (este problema se conoce como el problema del cartero
chino).
3.5.2.
El problema “Agua, Luz y Teléfono