Para hablar del comienzo de la teoría de grafos, nos tenemos que remontar a la ciudad prusiana de Königsberg, actualmente conocida como Kaliningrado (Rusia) y al problema de los puentes que atraviesan la ciudad. A su paso por ella tenemos el río Pregel y en el siglo dieciocho había siete puentes que conectaban las distintas partes de la ciudad con la isla en medio de ella. Se dice que los habitantes se planteaban la cuestión si era posible comenzar en determinado lugar y cruzar todos sus puentes, pasando una sola vez por cada uno de ellos y volver a la misma zona de inicio de donde habían partido.
Este problema fue resuelto en 1736 por Leonhard Euler, que probó matemáticamente que no se
podía hallar una solución al mismo. Este resultado se conoce como el nacimiento
de la teoría de grafos.
En esta misma ciudad nació Gustav Kirchoff en 1824, el cual se sirvió de la teoría de grafos para enunciar las leyes que hoy en día llevan su nombre, y que permiten calcular voltajes y corrientes en circuitos eléctricos.
Relacionado también con la electricidad, Otakar Boruvka utilizó en 1926 la Teoría de Grafos para calcular el diseño de una red eléctrica eficiente para electrificar la región de Moravia. Su resultado sobre árboles generadores es uno de los primeros algoritmos en Teoría de Grafos. Este algoritmo fue la semilla que dio lugar posteriormente al algoritmo de Kruskal.
No sólo se empezaron a hallar aplicaciones en la física sino también en la química. Arthur Cayley utilizó los grafos para estudiar distintos isómeros, compuestos químicos con la misma formulación, en particular para la siguiente familia de hidrocarburos, CnH2n+2.
De hecho, el nombre de Grafo es acuñado por James Joseph Sylvester en un artículo de 1878 en el que estudia la relación entre el álgebra y los diagramas moleculares. Sylvester fue alumno de Auguste De Morgan, al igual que Francis Guthrie, quien le planteó a De Morgan en 1852 el problema de los cuatro colores.
En esta misma ciudad nació Gustav Kirchoff en 1824, el cual se sirvió de la teoría de grafos para enunciar las leyes que hoy en día llevan su nombre, y que permiten calcular voltajes y corrientes en circuitos eléctricos.
Relacionado también con la electricidad, Otakar Boruvka utilizó en 1926 la Teoría de Grafos para calcular el diseño de una red eléctrica eficiente para electrificar la región de Moravia. Su resultado sobre árboles generadores es uno de los primeros algoritmos en Teoría de Grafos. Este algoritmo fue la semilla que dio lugar posteriormente al algoritmo de Kruskal.
No sólo se empezaron a hallar aplicaciones en la física sino también en la química. Arthur Cayley utilizó los grafos para estudiar distintos isómeros, compuestos químicos con la misma formulación, en particular para la siguiente familia de hidrocarburos, CnH2n+2.
De hecho, el nombre de Grafo es acuñado por James Joseph Sylvester en un artículo de 1878 en el que estudia la relación entre el álgebra y los diagramas moleculares. Sylvester fue alumno de Auguste De Morgan, al igual que Francis Guthrie, quien le planteó a De Morgan en 1852 el problema de los cuatro colores.
¿Es posible pintar cualquier mapa únicamente con
4 colores de manera que regiones colindantes no estén pintadas del mismo
color?
Este teorema fue probado finalmente por Kenneth Appel y Wolfgang Haken en 1976, con la ayuda de un ordenador, en el que probaron que no se podía conseguir con ninguna de las 1936 configuraciones a las que Heesch había reducido con anterioridad el problema. Sin embargo, estos no son los únicos mapas en los que ha sido importante la Teoría de Grafos.
En 1931, el ingeniero y diseñador Harry Beck se ayudó de un grafo sobre una cuadrícula octogonal para proyectar el mapa del metro de Londres, en el que se han ido inspirando los mapas posteriores.
Lo más importante del mapa era considerar que todas las comunicaciones se establecían o bien líneas de cuarenta y cinco grados o bien de noventa grados, y además cómo la idea dibujar con una línea azul el río Támesis a su paso por Londres, lo que permitía más fácilmente ubicar a la gente.
Así que como veis los grafos están por todas partes.
Este teorema fue probado finalmente por Kenneth Appel y Wolfgang Haken en 1976, con la ayuda de un ordenador, en el que probaron que no se podía conseguir con ninguna de las 1936 configuraciones a las que Heesch había reducido con anterioridad el problema. Sin embargo, estos no son los únicos mapas en los que ha sido importante la Teoría de Grafos.
En 1931, el ingeniero y diseñador Harry Beck se ayudó de un grafo sobre una cuadrícula octogonal para proyectar el mapa del metro de Londres, en el que se han ido inspirando los mapas posteriores.
Lo más importante del mapa era considerar que todas las comunicaciones se establecían o bien líneas de cuarenta y cinco grados o bien de noventa grados, y además cómo la idea dibujar con una línea azul el río Támesis a su paso por Londres, lo que permitía más fácilmente ubicar a la gente.
Así que como veis los grafos están por todas partes.
Comentarios
Publicar un comentario