Teoria de grafos

Teoría de Grafos.
El origen de la teoría de grafos se remonta al siglo XVIII con el problema de los puentes de Königsberg, el cual consistía en encontrar un camino que recorriera los siete puentes del río Pregel, en la ciudad de Königsberg, de modo que se recorrieran todos los puentes pasando una sola vez por cada uno de ellos. El trabajo de Leonhard Euler sobre el problema titulado “La soluciónde un problema relativo a la geometría de la posición” en 1736, es considerado el primer resultado de la teoría de grafos. Este ejemplo ilustra la profunda relación entre la teoría de grafos y la topología. Luego, en 1847, Gustav Kirchhoff 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 circuitoseléctricos, conocidas como leyes de Kirchhoff, considerado la primera aplicación de la teoría de grafos a un problema de ingeniería. En 1852 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. Este problema, que no fueresuelto hasta un siglo después 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.

La idea detrás de todo esto son las redes. Un ejemplo es pensar que nuestros amigos y conocidos son puntos o nodos, y se los une a todos ellos con unalínea. Y a su vez, cada uno de ellos tiene su propio grupo de conocidos, y al mismo tiempo esos conocidos tienen sus conocidos, y los conocidos de los conocidos de los conocidos, etc.
Esta serie de puntos unidos por líneas, reciben en matemática el nombre de grafos y esta teoría estudia sus propiedades. Un problema plantea cuantos grafos se necesitan para que una persona del mundo, estéconectada con cualquier otra persona del mundo. Luego de analizarlos se llegó a la respuesta de un máximo de seis grafos, es decir una persona puede llegar a estar conectada con otra persona mediante seis individuos de por medio.

Además de estas redes interpersonales hay otras que se pueden relacionar con la teoría de grafos. Una en particular es la del Internet, teniendo así una relación con lainformática. En este caso con cada página web indicamos un punto, y se forma un grafo con otra, cuando esta está enlazada con la misma. La pregunta que se formula es de cuántas páginas uno debe recorrer para llegar a cualquier otra. La teoría de grafos tiene un papel muy importante en la comprensión de cómo funciona Internet y las compañías que dan servicio de Internet la utilizan para mejorar susprestaciones.

Supongamos ahora que en una red se encuentran todos los actores que han trabajado alguna vez en una película, serían los nodos. Los nodos se unen si los actores trabajaron en la misma película. Hay un sitio web llamado Oracle de Bacon incluye información miles de películas y de los actores que han trabajado en ellas. Se basa en relacionar a cualquier actor con Kevin Bacon. Se ingresa elnombre en un buscador y aparece el resultado.
Por ejemplo al buscar “Carlos Gardel” el resultado nos indica que sólo hacen falta 3 pasos para conectar a Bacon con Gardel.
La teoría de grafos sirve para representar y analizar cualquier tipo de redes. Por ejemplo redes de caminos interurbanos, donde los nodos son ciudades y las conexiones entre estos puntos son las rutas entre ciudades. Lo mismoentre las redes de vuelo con sus rutas aéreas, redes de transistores, y la lista sigue.
La Teoría de Grafos juega un papel importante en la fundamentación matemática de las Ciencias de la Computación. Los grafos constituyen una herramienta básica para modelizar fenómenos discretos y son fundamentales para la comprensión de las estructuras de datos y el análisis de algoritmos.
Existen...