-
PUENTES DE KÖNIGSBERG
También llamado más específicamente problema de los siete puentes de Königsberg, es un célebre problema matemático resuelto por Leonhard Euler. Consistía en encontrar un camino que recorriera los siete puentes del río Pregel de modo que se recorrieran todos los puentes pasando una sola vez por cada uno de ellos. -
LEMA DEL APRETÓN DE MANOS
El Lema del apretón de manos determina 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. Fue demostrado por Euler. -
FORMULA DE EULER
Enuncia que si un grafo conexo, planar (es dibujado sobre un plano sin intersección de aristas), y siendo v 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
Utilizó la teoría de grafos para el análisis de redes eléctricas publicando sus leyes de los circuitos para calcular el voltaje y la corriente en los circuitos eléctricos, conocidas como leyes de Kirchhoff, considerado la primera aplicación de la teoría de grafos a un problema de ingeniería. -
CAMINOS HAMILTONIANOS
Hacia 1850 el matemático W. R. Hamilton patentó un juego que llamó Viaje por el Mundo. Consistía 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). Desde entonces, 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 planteó 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 ISOMEROS
Arthur Cayley estudió y resolvió 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 representó cada compuesto, en este caso hidrocarburos saturados CnH2n+2, mediante un grafo árbol donde los vértices representan átomos y las aristas la existencia de enlaces químicos. -
ALGORITMO DE HIERHOLZER
Proporciona 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 cuyo origen se remonta al año 1883. Considerando un grafo del que sabemos que todas las líneas en la misma componente y al menos dos vértices de ángulo impar. El algoritmo comienza en el vértice del ángulo 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 sobrante. -
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 adoptada 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 ERDOS
Nace el prolífico matemático hungaro, Paul Erdos, 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. -
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 plano. en la actualidad su trabajo se interpreta por medio de grafos, esto ha permitido que otros psicoanalistas utilicen los grafos como interpretación psicológica de un individuo y su ambiente, donde 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. Trabaja 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). -
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 sociomatrices 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. -
BEST-THEOREM
El teorema BEST muestra que el número de circuitos eulerianos en grafos dirigidos se puede calcular en tiempo polinómico, un problema que es #P 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 gráfico contuviera un circuito hamiltoniano. -
ALGORITMO DE DIJKSTRA
Se publica el algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto, dado un vértice origen, hacia el resto de los vértices en un grafo que tiene pesos en cada arista. -
ENUMERACIÓN DE GRAFOS
es decir, contando grafos de un tipo especificado. 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. -
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. Al tratar de resolverlo, los matemáticos definieron términos y conceptos teóricos fundamentales de los grafos. Además se necesito del auxilio de las computadoras para lograr la demostración, esto causó gran revuelo. -
TEOREMA DE BONDY-CHVÁTAL
Teorema publicado en 1976 debido a J. A. Bondy y a V. Chvátal, que generaliza los resultados anteriormente encontrados por G. A. Dirac (1952) y Ø. Ore (1960). Todos estos resultados afirman, básicamente, que un grafo es hamiltoniano si existen “suficientes aristas” -
ACTUALIDAD
Hoy en día a teoría de grafos sigue siendo ampliada, pues sus aplicaciones son cada vez más usadas en diferentes disciplina. Puede decirse que no solo es un tema que atañe a lo matemáticos, sino que también a psicólogos, economistas, programadores, computólogos, etc.
Hay que pensar cómo esta rica teoría impacta en nuestras vidas y tendremos de esta forma, la clara respuesta de su importancia.