Teoría de Grafos
Es una ciencia matemática que estudia los Grafos. Estas son estructuras matemáticas para modelar relaciones por pares entre objetos. Un grafo se compone de vértices, nodos o puntos que están conectados por aristas, arcos, bordes o líneas. Existen varios tipos de grafos y muchos problemas propuestos para esta ciencia. En esta entrada solo hablaremos un poco de cómo empezaron el estudio de esta ciencia.
Historia
Se mostrará una secuencia cronológica para contar esta historia y se enfoncará sobre el problema del Camino más corto:
1736
Los Siete Puentes de Königsberg
El problema de los Siete Puentes de Königsberg es considerado como el primer artículo de la historia en la teoría de grafo, publicado por Leonhard Euler. Sí, el mismo de los algorítmos. Esta también hace parte de los principios de la Topología. El artículo puede encontrarse originalmente en latín con este enlace.
El problema es de lo más interesante. En la ciudad de Königsberg en Prusia (ahora Kaliningrado, Rusia) era una isla con algunos puentes, el problema era idear una caminata por la ciudad que cruzara cada uno de esos puentes una vez y solo una vez. Euler demostró que el problema no tiene solución.
1847
Se publica la primera aplicación de la teoría de grafos, las leyes de Kirchhoff en análisis de redes eléctricas. Estas leyes de los circuitos se utiliza para calcular el voltaje y la corriente en los circuitos eléctricos.
1852
Se propone uno de los problemas más famosos. El problema de los cuatro colores. El cual enuncia: “¿Es cierto que cualquier mapa dibujado en el plano puede tener sus regiones coloreadas con cuatro colores, de modo que dos regiones vecinas tengan ¿Colores diferentes?“. Planteado por Francis Guthrie y su primer registro es en una carta de De Morgan a Hamilton el mismo año. Además fue el primer gran teorema que se probó usando una computadora, aunque su prueba no fue aceptada por todos los matemáticos porque la prueba asistida por computadora era inviable para que un humano la revisara a mano.
Paises pintados con solo cuatro colores sin repetir colores en paises vecinos
1857
Arthur Cayley resolvió el problema de la enumeración de isómeros (ej: alcohol etílico) por medio de grafos. Para ello representó cada compuesto, en este caso hidrocarburos saturados CnH2n+2, mediante un grafo árbol donde los nodos representan átomos y los arcos la existencia de enlaces químicos.
1878
El término grafo es acuñado por Silvester en un artículo publicado en Nature. Donde traza una analogía entre invariantes cuánticos y co-variantes.
1936
Se publica el primer libro de Teoría de Grafos, escrito por el matemático judío húngaro Dénes König.
1953
Se introduce por primera vez el cálculo de APSP por Shimbel. Quien descubrió que puede ser resuelto por una serie lineal de multiplicaciones en matrices. APSP son las siglas en inglés de All pairs Shortest Path, traduce “Caminos más cortos entre todos los pares“.
1956
Se describe el primer modelo para resolver problema del camino más corto, el cual es uno de los problemas más populares de esta ciencia. Lester Ford Jr publica su algoritmo para calcular el SSSP que en inglés dice: Single Source Shortest Path, traduce “Camino más corta de una sola fuente“. Este posee una complejidad algorítmica de 
Edsger Wybe Dijkstra
1959
Aparece el algoritmo Dijkstra. Uno de los algoritmos más populares del problema de SSSP en un grafo ponderado. Posee una complejidad algorítmica de 
1962
Se describe el algoritmo de Floyd-Warshall para el problema de APSP. Este algoritmo representa la solución en una matriz de distancias, es un claro ejemplo de programación dinámica y posee una complejidad algorítmica de 
1967
El primer algoritmo para cálculos de APSP en grafos dinámicos se publica por Peter S. Loubal con una complejidad algorítmica de
1969
Se publica el libro de Frank Harary. Es considerado como el texto definitivo del tema en la época y permitió a matemáticos, químicos, ingenieros eléctricos y científicos sociales hablar entre ellos.
1977 – 1981
Donald Bruce Johnson
Se publica el algoritmo de Johnson el cual calcula el APSP para grafos ponderados con arcos negativos, es muy parecido al algoritmo de Floyd-Warshall. Publicado por el científico de la computación Donald Bruce Johnson y posee una complejidad algorítmica de 
1984
Se implementa el algoritmo de Dijkstra con una cola de prioridad implementada por un montículo de Fibonacci. Se debe a Fredman & Tarjan y corre con una complejidad de 
1991
Ausiello continuó con el análisis de grafos dinámicos con un algoritmo para grafos enteros de arco no mayores a un valor constante 
 Grafo A |
 Grafo A después de una inserción de arco |
|---|
1996
El famoso algoritmo de Ramalingam y Reps fue publicado, también para grafos dinámicos y posee una complejidad de 
1999
El algoritmo de Thorup sale a la luz con un algoritmo de complejidad
2004
Giuseppe Francesco Italiano
El italiano científico de la computación Giuseppe F. Italiano publica un algoritmo para grafos dinámicos con una complejidad algorítmica de 
2014
Se propone un nuevo algoritmo para grafos dirigidos por Khopkar con una complejidad algorítmica de
2017
Slobbe propone un algoritmo más eficiente que los anteriores para grafos dinámicos en escenarios de peor caso. Los resultados de sus pruebas comparan su algoritmo con métodos como los de Khopkar y Ramlingam y resulta ser mucho más rápido. Su complejidad también es de
Post Info
Este artículo solo muestra un resumen, existen muchísimas investigaciones de caminos cortos, sin embargo introduje los más importante, sobre todo los que estoy estudiando actualmente. Gracias por leer.
Comentarios