Grafos

GRAFOS

Historia y problema de los puentes de Königsberg

Los siete 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 Königsberg. La ciudad de Kaliningrado, originalmente Königsberg, es famosa por sus siete puentes que unen ambas márgenes del ríoPregel 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 yplanteándolo con la (entonces aú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 departida sin pasar por la misma arista más de una vez?

El origen de la palabra grafo es griego y su significado etimológico es "trazar". Aparece con gran frecuencia como respuesta a problemas de la vida cotidiana,algunos ejemplos podrían ser los siguientes:un gráfico de una serie de tareas a realizar indicando su secuenciación (un organigrama),grafos matem´ticos que representan las relacionesbinarias,una red de carreteras,la red de enlaces ferroviarios o aéreos o la red eléctrica de una ciudad.(Véase la figura 1).En cada caso,es conveniente representar gráficamente el problema dibujando un grafo como un conjunto de puntos(vértices)con líneas conectándolos (arcos).

De aquí se podría deducir que un grafo es básicamente un objeto geométrico aunque en realidad sea un objeto combinatorio,esdecir,un conjunto de puntos y un conjunto de líneas tomado de entre el conjunto de líneas que une cada par de vértices.Por otro lado,y debido a su generalidad y a la gran diversidad de formas que pueden usarse,resulta complejo tratar con todas las ideas relacionadas con un grafo.
Para facilitar el estudio de este tipo de dato,a continuación se realizará un estudio de la teoría de grafos desde elpunto de vista de las ciencias de la computación. Considerando que dicha teoría es compleja y amplia,aquí sólo se realizará una introducción a la misma,describiéndose el grafo como un tipo de dato y mostrándose los problemas típicos y los algoritmos que permiten solucionarlos usando un ordenador.
Los grafos son estructuras de datos no lineales que tienen una naturaleza generalmente dinámica. Suestudio podría dividirse en dos grandes bloques:
* Grafos Dirigidos.
* Grafos no Dirigidos(pueden ser considerados un caso particular de los anteriores).
Un ejemplo de grafo dirigido lo constituye la red de aguas de una ciudad ya que cada tubería sólo admite que el agua la recorra en un único sentido. Por el contrario, la red de carreteras de un país representa en general un grafo nodirigido, puesto que una misma carretera puede ser recorrida en ambos sentidos. No obstante, podemos dar unas definiciones generales para ambos tipos

Esta definición da lugar a una representación gráfica, en donde cada vértice es un punto del plano, y cada arista es una línea que une a sus dos vértices.
Aristas
Son las líneas con las que se unen las aristas de un grafo y con la que se construyentambién caminos.
Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une.
Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos.
* Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.
*
* Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el...