jhon

Introducción a teoría de Grafos
Conceptos Fundamentales de Grafos
Partiremos nuestro estudio un par de ejemplos que sugerirán una definición para lo que es un
grafo y motivaran el tipo de aplicaciones para los que se utilizan. El primero que veremos se
suele citar como el que dio inicio a la teoría de grafos.
Ejemplo: Los Puentes de Konigsberg. La ciudad de Konigsberg (hoy conocida comoKaliningrado) estaba localizada en el este de Prusia. La ciudad tenía una isla que formaba el
río Pregel al cruzarla, y antes de dejar la ciudad el río se bifurcaba dando paso a dos causes
distintos. Las regiones formadas por el río estaban unidas con siete puentes. Un diagrama
simplificado de la ciudad puede verse en la figura 1.

Figura 1: Diagrama de la ciudad de Konigsberg

Los habitantesde Konigsberg se preguntaban si existía alguna forma de salir de casa, recorrer
la ciudad pasando por todos los puentes una vez por cada uno, y regresar a casa. En la figura
2 se ha hecho una representación simplificada de la ciudad. Cada punto representa una de las
regiones, y cada trazo a un puente. El problema puede reducirse entonces al de dibujar la
figura 2 sin levantar el lápiz y sinrepetir ningún trazo, partiendo desde uno de los puntos y
volviendo al inicial.

Figura 2: Representación Simplificada de la ciudad de Konigsberg

Con esta reformulación no es difícil argumentar que la respuesta al problema de los puentes es
no. Lo primero es notar que para dibujar la figura 2 debemos para cada punto que no es el
inicial, “entrar” por un trazo y “salir” por otro trazo(distinto). Si notamos en la figura el punto D

por ejemplo, tiene tres trazos “incidiendo” en ´el, por lo que después de que se pase por D una
vez (se “entre y salga” de D), la próxima vez que se llegue a D no se podría salir. Lo mismo
pasa con los puntos A y C. El punto B es un poco diferente, dado que tiene 5 trazos, se podría
“entrar y salir” dos veces, cuando se llegue por tercera vez a B yano se podría salir.
El problema entonces surge porque los puntos tienen una cantidad impar de trazos. Dado que
el problema exige que el punto inicial sea igual al punto final, se puede concluir, por la misma
razón, que tampoco es posible partir de ninguno de estos puntos ya que el trazo por el que se
sale inicialmente de un punto debe ser distinto al con el que se llega finalmente.
El problemaentonces tiene que ver con la paridad de los trazos de cada punto. Basta con que
uno de los puntos tenga una cantidad impar de trazos para que la figura no se pueda dibujar
siguiendo las reglas pedidas. Finalmente es imposible recorrer la ciudad completa de
K¨onigsberg pasando por todos los puentes y volver a casa. El primero que dio esta respuesta
fue el matemático suizo L. Euler(1707–1783)en el año 1735.
Ejemplo: El ejemplo anterior era un poco radical porque todos sus puntos tenían una cantidad
impar de trazos. La figura 3 tampoco se puede dibujar sin repetir trazos y volviendo al punto de
partida.

Figura 3: Figura que tampoco se puede dibujar cumpliendo las reglas.

La razón es la misma que antes, existen puntos con cantidad impar de trazos, en este caso los
puntos D y Etienen ambos tres trazos. Basta con que uno de los puntos de la figura tenga una
cantidad impar de trazos para que esta no se pueda dibujar siguiendo las restricciones. ¿Qué
pasa si una figura tiene todos sus puntos con una cantidad par de trazos? En este caso nuestra
argumentación inicial no sería aplicable si quisiéramos mostrar que no se puede dibujar. El
resultado interesante que veremosmás adelante, no diría que para que una figura se pueda
dibujar siguiendo las restricciones, simplemente basta con que todos sus puntos tengan una
cantidad par de trazos. De allí se concluirá que una figura se puede dibujar sin repetir trazos y
volviendo al punto de partida, si y solo si cada punto tiene una cantidad par de trazos.
Los anteriores ejemplo motivan nuestra definición de grafo....