-
Los siete puentes de Königsberg
El problema de los puentes de Königsberg surge como un desafío matemático en una ciudad prusiana dividida por el río Pregel. Siete puentes conectaban cuatro zonas urbanas, inspirando a sus habitantes a preguntarse si era posible recorrerlos todos una vez sin repetir ninguno. Euler no solo demostró la imposibilidad del recorrido, sino que sentó las bases de la teoría de grafos, transformando un enigma local en un hito de las matemáticas modernas. -
Lema del Apretón de Manos
Euler también demuestra el Lema del apretón de manos, que establece que la suma de los grados de un grafo simple (es decir, sin bucles) y no dirigido equivale al doble de su número de aristas. -
Fórmula de Euler
Euler Enuncia que si un grafo conexo, planar (es dibujable sobre un plano sin intersección de aristas) y simple, y el número de vértices, a el de aristas, y c la cantidad de caras (regiones conectadas por aristas, incluyendo la región externa e infinita), entonces: V - A + C = 2. -
Kirchhoff y Grafos
Gustav Kirchhoff utiliza la teoría de grafos para el análisis de redes eléctricas, publicando sus dos leyes para calcular voltaje y corriente en los circuitos eléctricos, conocidas como leyes de Kirchhoff, considerada la primera aplicación de la teoría de grafos a un problema de ingeniería. -
Caminos Hamiltonianos
W.R. Hamilton patenta un juego de tablero llamado "Tour del Mundo". Consiste en encontrar un recorrido que pasase por 20 ciudades situadas en los nodos del grafo del dodecaedro (que es equivalente a un recorrido por los 20 vértices del dodecaedro pasando una sola vez por cada vértice). Se llaman caminos hamiltonianos a los recorridos que visitan todos los vértices de un grafo una sola vez. -
El Problema de los Cuatro Colores
Francis Guthrie plantea el problema de los cuatro colores, el cual afirma que es posible, utilizando solamente cuatro colores, colorear cualquier mapa de países de tal forma que dos países vecinos nunca tengan el mismo color. -
Cayley y los Isómeros
Arthur Cayley estudia y resuelve el problema de enumeración de los isómeros, compuestos químicos con idéntica composición (fórmula) pero diferente estructura molecular. Para ello representa cada compuesto, en este caso hidrocarburos saturados CH(2n+2), mediante un grafo árbol donde los vértices representan átomos y las aristas la existencia de enlaces químicos. -
Grafos Bipartitos
Los matemáticos Jordan, Sylvester y Petersen desarrollan el concepto de grafos bipartitos, fundamentales para modelar relaciones entre conjuntos distintos de entidades. -
Algoritmo de Hierholzer
Se propone un método diferente a la hora de recorrer los ciclos eulerianos de una forma más eficiente que los algoritmos de Fleury. -
Algoritmo de Fleury
El algoritmo de Fleury es un algoritmo elegante pero ineficiente para encontrar recorridos eulerianos. Busca un camino que siga todas las líneas en la misma componente y al menos dos vértices de grado impar. El algoritmo comienza en el vértice del grado impar. En cada paso se elige el siguiente lado que queda unido al punto anterior por una sola línea. Finalmente, nos movemos al lado que queda en el vértice siguiente. -
Adopción del Término "Grafo"
El término "grafo" proviene de la expresión inglesa graphic notation (notación gráfica), usada por primera vez por Edward Frankland y posteriormente adaptada por Alexander Crum Brown. Hacía referencia a la representación gráfica de los enlaces entre los átomos de una molécula. -
Kazimierz Kuratowski
Nace el matemático polaco Kazimierz Kuratowski, quien demostró el teorema de Kuratowski, que es una caracterización de los grafos planares. -
Paul Erdős
Nace el prolífico matemático húngaro Paul Erdős, que con sus colaboradores trabajó en problemas sobre combinatoria, teoría de grafos, teoría de números, análisis clásico, teoría de aproximación, teoría de conjuntos y probabilidad. -
Teorema de Kuratowski
Kazimierz Kuratowski publica su teorema fundamental sobre la caracterización de grafos planares, estableciendo que un grafo es planar si y solo si no contiene subgrafos homeomorfos a K₅ o K₃,₃. -
Primer Libro
El primer libro sobre teoría de grafos fue escrito por Dénes König y publicado en 1936. -
Kurt Lewin
El psicólogo Kurt Lewin propuso que el espacio interior de un individuo puede ser interpretado por un mapa planar, en la cual cada región se puede interpretar usando de grafos, esto ha permitido que otros psicólogos utilicen los grafos como interpretación matemática del individuo y de sus procesos. En los grafos sociométricos las personas vendrían siendo vértices y sus relaciones personales las líneas o aristas. -
Fan Chung
Nace la matemática taiwanesa Fan Chung. Trabajó principalmente en las áreas de teoría de grafos espectrales, teoría de grafos extremos y grafos aleatorios, en particular en la generalización del modelo de Erdős-Rényi para grafos con distribución general de grados (incluyendo grafos de ley de potencia) en el estudio de grandes redes de información. -
Problema del Flujo Máximo
El problema del flujo máximo es formulado por primera vez, luego desarrollado por Ford y Fulkerson en los años 50, con aplicaciones cruciales en logística y transporte. -
Cliques o Camarillas
A fines de los años 1940 e inicios de los años 1950, junto con los primeros estudios formales de cliques o camarillas en sociometrías y de centralidad en sociogramas, se introdujo la teoría de grafos como herramienta clave para la sociometría y el análisis de redes sociales. -
Teorema BEST
El teorema BEST establece que el número de recorridos eulerianos en grafos dirigidos se puede calcular en tiempo polinómico, un problema que es NP-completo para grafos no dirigidos. El teorema BEST se debe a van Aardenne-Ehrenfest y de Bruijn. -
Dirac y Circuitos Hamiltonianos
Dio una condición suficiente para que un grafo contenga un circuito hamiltoniano. -
Algoritmo de Dijkstra
Edsger W. Dijkstra desarrolla su famoso algoritmo para encontrar el camino más corto entre nodos en un grafo, revolucionando el campo de la optimización de rutas. -
Teoría de Erdős-Rényi
Paul Erdős y Alfréd Rényi introducen la teoría de grafos aleatorios, fundamental para entender redes complejas y sus propiedades estadísticas. -
Algoritmo de Dijkstra
Se publica el algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, que resuelve el problema del camino más corto, dado un vértice origen, hacia el resto de los vértices en un grafo que tiene peso en cada arista. -
Problema P vs NP
Richard Karp demuestra que 21 problemas combinatorios (muchos basados en grafos) son NP-completos, contribuyendo significativamente a la teoría de la complejidad computacional. -
Enumeración de Grafos
Desarrollo de técnicas para contar grafos de un tipo específico. Fue coautor de un libro sobre el tema (Harary y Palmer 1973). La principal dificultad es que dos grafos que son isomorfos no deben contarse dos veces, por lo tanto, uno tiene que aplicar la teoría de Pólya de contar bajo la acción grupal. Harary era un experto en esto. -
Teorema de Bondy-Chvátal
Teorema publicado en 1976, publicado J. A. Bondy y V. Chvátal, que generaliza los resultados anteriormente encontrados por G. A. Dirac (1952) y O. Ore (1960). Todos estos resultados afirman básicamente que un grafo es hamiltoniano si existen "suficientes aristas". -
El Problema de los Cuatro Colores: Solución
El problema fue resuelto por Kenneth Appel y Wolfgang Haken en 1976, puede ser considerado como el nacimiento de la teoría de grafos moderna, tanto por sus resultados como por sus conceptos teóricos fundamentales de los grafos. Además se necesitó del auxilio de las computadoras para lograr la demostración, esto causó gran revuelo. -
Coloración de Grafos
László Lovász desarrolla el teorema del número cromático para grafos perfectos, aportando herramientas fundamentales para problemas de coloración. -
PageRank
Larry Page y Sergey Brin desarrollan el algoritmo PageRank para Google, basado en teoría de grafos, revolucionando los motores de búsqueda en internet. -
Análisis de Redes Sociales
Se desarrollan modelos matemáticos basados en grafos para analizar redes sociales y su comportamiento, popularizados por los trabajos de Albert-László Barabási sobre redes de escala libre. -
Inteligencia Artificial y Grafos
El auge de los grafos de conocimiento (knowledge graphs) y bases de datos orientadas a grafos (como Neo4j), transforman la IA y la gestión de datos complejos. -
Algoritmos de Grafos en Aprendizaje Profundo
Desarrollo de redes neuronales de grafos (GNN) que permiten aplicar técnicas de aprendizaje profundo a estructuras de grafos, revolucionando campos como la química computacional, el descubrimiento de fármacos y la recomendación de productos. -
Computación Cuántica y Grafos
Algoritmos cuánticos para problemas de grafos, como el algoritmo de Grover para búsqueda y la optimización combinatoria, abren nuevas fronteras en la resolución de problemas previamente intratables. -
Actualidad
Hoy en día la teoría de grafos sigue siendo ampliada, pues sus aplicaciones son cada vez más vastas en diferentes disciplinas. Puede decirse que no solo es un tema que atañe a la matemática, sino que también a psicología, economistas, programadores, computación, etc. Hay que pensar como esta rica teoría impacta en nuestras vidas y tendencias de cada forma, la clara respuesta es su importancia.