Teoría de  grafos

La teoría de grafos  ha servido de inspiración para las ciencias sociales, en especial para desarrollar un concepto de red social que sustituye los nodos por los actores sociales y verifica la posición, centralidad e importancia de cada actor dentro de la red. 

En una red de comunicación, no es necesario que toda persona pueda comunicarse directamente con otra, puesto que una persona pueden actuar de posta para un mensaje entre otras personas.

Leonard Euler, uno de los grandes matemáticos de la historia, vivía en Königsburg, y los colegas de él se divertían discutiendo un problema: cómo hacer una caminata por la ciudad cruzando cada uno de sus siete puentes una y sólo una vez, y volver al punto de partida.

Euler  decía que era un problema del grafo y que no importaba si los nodos eran islas o bandas o qué. Y se puso a pensar en la generalidad de esos curiosos objetos, que ahora llamamos grafos, de los cuales había producido un ejemplo, y en el problema de encontrar un camino que pasaba por cada arista y volvía al nodo de partida.

Euler resolvió ese primer problema con que fundó la teoría de grafos y concluyó  que no era posible realizar el recorrido sin repetir ninguno de los puentes porque el número de puentes era impar.

Practicamente cualquier problema puede respresentarse mediante un grafo.

Por ejemplo, el problema del vendedor viajero consiste en encontrar la ruta más corta en la que agente viajero pueda visitar en cada ciudad a sus clientes una vez, comenzando y terminando en la misma ciudad.

Para que el vendedor pueda cumplir su cometido, lo primero que  debería tener en cuenta es que el número de ciudades a visitar debe ser par, al igual que el ejemplo de los puentes de Konigsburg. Para poder visualizar mejor el recorrido a realizar deberiamos hacer un diagrama con el circuito y marcar las ciudades como puntos. Para pasar una sola vez por cada ciudad, en cada punto del diagrama que se busca debería haber dos líneas, una seria el camino de donde viene a esa ciudad y la otra el camino por donde sale de la misma. Basándonos en esto,deberían haber tantas líneas como puntos o sea tantas rutas o caminos como ciudades a visitar.