Historia de la teoría de grafos
El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de Königsberg es considerado el primer resultado de la teoría de grafos. Pero a la vez se lo considera uno de los primeros resultados topológicos en geometría.
Descripción general del problema
Leonhard Euler llegó a Prusia en 1741, a la edad de 34 años. Durante esos años trabajó en la Academia Prusiana de las Ciencias, donde desarrolló una prolífica carrera como investigador. Fue contemporáneo de varios otros famosos matemáticos y pensadores procedentes de aquella ciudad, tales como Immanuel Kant, Johann Georg Hamann y Christian Goldbach, por lo que Königsberg fue en ese tiempo un importante epicentro científico. Es en este ambiente y por estos años que surge la formulación del problema, propagándose a modo de juego y de trivia matemática entre los intelectuales de la época, la resolución de esté dio origen a la teoría de grafos.
Pero, hagamos un poco de historia: Su nombre se debe a Königsberg, el antiguo nombre que recibía la ciudad rusa de Kaliningrado, que durante el siglo XVIII formaba parte de Prusia Oriental, como uno de los ducados del Reino de Prusia.
Esta ciudad es atravesada por el río Pregolya, el cual se bifurca para rodear con sus brazos a la isla Kneiphof, dividiendo el terreno en cuatro regiones distintas, las que entonces estaban unidas mediante siete puentes llamados Puente del herrero, Puente conector, Puente verde, Puente del mercado, Puente de madera, Puente alto y Puente de la miel.
La respuesta es negativa, es decir, no existe una ruta con estas características.
El problema puede resolverse aplicando un método de fuerza bruta, lo que implica probar todos los posibles recorridos existentes.
Sin embargo, Euler en 1736 en su publicación «Solutio problematis ad geometriam situs pertinentis» demuestra una solución generalizada del problema, que puede aplicarse a cualquier territorio en que ciertos accesos estén restringidos a ciertas conexiones, tales como los puentes de Königsberg.
Para dicha demostración, Euler recurre a una abstracción del mapa, enfocándose exclusivamente en las regiones terrestres y las conexiones entre ellas. Cada puente lo representó mediante una línea que unía a dos puntos, cada uno de los cuales representaba una región diferente. Así el problema se reduce a decidir si existe o no un camino que comience por uno de los puntos azules, transite por todas las líneas una única vez, y regrese al mismo punto de partida.
Euler determinó, en el contexto del problema, que los puntos intermedios de un recorrido posible necesariamente han de estar conectados a un número par de líneas. En efecto, si llegamos a un punto desde alguna línea, entonces el único modo de salir de ese punto es por una línea diferente. Esto significa que tanto el punto inicial como el final serían los únicos que podrían estar conectados con un a número impar de líneas. Sin embargo, el requisito adicional del problema dice que el punto inicial debe ser igual al final, por lo que no podría existir más de un único punto conectado con un número impar de líneas.
En realidad, en estos recorridos, llamados eulerianos, no pueden existir puntos con un número impar de líneas coincidentes. Solo en el caso de los caminos eulerianos, donde se acepta que el punto inicial y el final sea distinto, puede darse que únicamente éstos tengan un número impar de líneas coincidentes. Euler sólo caracterizo formalmente los caminos eulerianos; mientras que la caracterización formal de los ciclos eulerianos la hizo Carl Hierholzer más tarde, en 1873, lo que no impide que la demostración de Euler sea general y correcta.
En particular, como en este diagrama los cuatro puntos poseen un número impar de líneas incidentes (tres de ellos inciden en tres líneas, y el restante incide en cinco), entonces se concluye que es imposible definir un camino con las características buscadas.
Esta abstracción del problema ideada por Euler dio pie a la primera noción de grafo, que es un tipo de estructura de datos, utilizada ampliamente en matemática discreta y en ciencias de la computación. A los puntos se les llaman vértices y a las líneas aristas. Al número de aristas incidentes a un vértice se le llama el grado de dicho vértice. Específicamente, un diagrama como el de la abstracción del mapa de Königsberg representa un multígrafo no dirigido sin bucles. Aclaremos estos dos conceptos:
v Un multígrafo no dirigido es aquel en el cual la dirección no importa
v Bucle de un grafo, es una arista que conecta a un vértice con sí mismo (es como un rulo, de allí su nombre)
Una, la cuestión fundamental a destacar es que la publicación de Euler es la primera que hace alusión a una geometría en que sólo interesan las propiedades estructurales de los objetos, y no sus medidas, como tradicionalmente se hace. Su diferencia con la geometría euclidiana radica en que la teoría de grafos carece de métrica, pues la conceptualización de "distancia" se obvia para hacer generalizaciones sobre las figuras o grafos. Es así como la línea recta y la curva son equivalentes, una figura compuesta por segmentos rectilíneos es equivalente a la misma figura compuesta por segmentos de arco, todos los triángulos son equivalentes (equilátero, escaleno e isósceles) ya que la teoría de grafos, sólo se ocupa de una propiedad común de los mismos: la triangularidad. Euler llama a esta nueva manera de ver los objetos geométricos «geometriam situs», término que hoy se traduce como topología, área actual de la matemática cuyo origen directo puede situarse en la resolución de este problema
Ahora sí; TEORIA DE GRAFOS
Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas los cuales pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).
v Puede haber varias aristas entre dos vértice
v El vértice de partida y el de llegada puede ser el mismo
v Las aristas pueden o no llevar flechas
Orden de un Grafo: es el número de vértices que posee en Grafo
Grado de un vértice: es el número de aristas que inciden sobre el vértice o nodo
Ejemplos de Grafos
v Grafos simples : no poseen aristas orientadas, ni bucles, pero además, entre un mismo par de vértices no se admiten dos o más aristas
vPseudografo: se permiten aristas múltiples y bucles
v Multígrafos dirigidos
vPseudografos dirigidos
Algunas de las aplicaciones más usuales son:
Sistemas de Aeropuertos
Flujo de tráfico
Contactos
¿Cómo podemos organizar el horario de proyección de las películas de un festival de cine de tal modo que aquellos interesados en distintos tipo de películas puedan asistir a todas ellas sin que las películas dentro del mismo tipo no se “amontonen”? ¿Cuántos sudokus hay? ¿Cuántas maneras hay de colorear los países de mapa mundial?
Muchos de estos problemas se pueden representar mediante un grafo, ya que como dijimos, la forma del grafo no es importante, así como la longitud de sus aristas. En los programas informáticos los grafos se representan mediante matrices, de esta manera es mucho más fácil su manipulación y más sencillo el efectuar operaciones sobre ellos.
Los problemas relativos a la organización de horarios en festivales de cine, la construcción de sudokus o coloración de mapas del mundo se pueden intentar representar por grafos que tiene los vértices coloreados. En cada caso o problema los "colores" representan o simbolizan algo distinto y no necesariamente son literalmente colores.
