Teoria de grafos

Origen

El Porque de la Teoría de Grafos (puentes de Königsberg)

El primer artículo científico relativo a grafos fue escrito por el matemático suizo Leonhard Euler en 1736. Euler se basó en su artículo en el problema de los puentes de konigsberg.
La ciudad de Kaliningrado, originalmente Königsberg, es famosa por sus siete puentes que unen ambas márgenes del río Pregel con dos de sus islas.Dos de los puentes unen la isla mayor con la margen oriental y otros dos con la margen occidental. La isla menor está conectada a cada margen por un puente y el séptimo puente une ambas islas. El problema planteaba lo siguiente: ¿es posible, partiendo de un lugar arbitrario, regresar al lugar de partida cruzando cada puente una sola vez?
Abstrayendo este problema y planteándolo con la (entoncesaún básica) teoría de grafos, Euler consigue demostrar que el grafo asociado al esquema de puentes de Königsberg no tiene solución, es decir, no es posible regresar al vértice de partida sin pasar por alguna arista dos veces.
De hecho, Euler resuelve el problema más general: ¿qué condiciones debe satisfacer un grafo para garantizar que se puede regresar al vértice de partida sin pasar por la mismaarista más de una vez?

¿Qué es?
Si queremos definir un grafo podríamos empezar por definir lo que representa. Un grafo representa una estructura de datos. Gráficamente se le puede definir como un conjunto de vértices relacionados entre sí por una serie de arcos. Un conjunto estructurado por medio de relaciones binarias.
Los grafos tienen muchas funciones ya que estos se aplican confrecuencia en la investigación operativa y en el modelamiento de diversos problemas. Dependiendo de lo que requiera la persona para representar. Como el grafo mantiene una relación entre todos sus elementos, es de gran ayuda para simplificar procedimientos y graficarlos, estableciendo así diferentes variables como: tiempo, longitud, cantidad, etc.
Al poder establecer relaciones entre diferentes elementosun grafo representa en realidad un sistema. Ya que por definición, un sistema es un conjunto de elementos interactuando entre sí para lograr un objetivo concreto, el grafo busca graficar el funcionamiento de este sistema.

¿Cómo es?
Los grafos son representaciones gráficas, como representan sistemas, al existir diferentes tipos de sistemas, también existen muchos tipos de grafos. Como porejemplo.
Conexo: Se dice que un grafo es conexo cuando entre dos vértices existe una cadena que los une.
Grafico fuertemente Conexo: Sucede cuando entre dos vértices hay un camino para ir de uno a otro y viceversa.
Dirigido: Se dice que un grafo es dirigido cuando los arcos son flechas, mejor dicho tienen una dirección la cual se tiene que seguir.
No dirigido: Se dice que un grafo no es dirigidocuando los arcos son líneas las cuales no indican dirección alguna.
Arboles: Es un grafo simétrico conexo, sin ningún ciclo donde se puede ver claramente la estructura de un procedimiento.

Todos ellos ayudan a comprender cómo es que funciona un sistema. Por ejemplo, un grafo dirigido nos podría ayudar a ver la secuencia de pasos que hay que seguir para terminar un proyecto, ya que se sigue unorden y es necesario pasar por un elemento antes de continuar el camino. Un árbol nos podría dar a entender también las actividades que se tienen que llevar a cabo para poder desarrollar la actividad principal.

Fueron muchas las personas que se dedicaron a investigar e idear los grafos. Entre los más representativos podemos encontrar a Leonard Euler (el pionero y mencionado anteriormente). Asítambién como Euler, Meigu Guan investigó durante 1962 el problema del cartero chino. Consistía en que un cartero debía repartir la correspondencia siendo la oficina de correo el inicio y el fin del recorrido, se requería buscar una ruta óptima.
[pic]

Edsger diijsktra es otro claro ejemplo de los descubrimientos, el planteó el algoritmo del camino mínimo en 1959. El se baso en encontrar los...