HISTORIA DE LA TEORIA DE GRAFOS

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 relaciones binarias,una red de carreteras,la red de enlaces ferroviarios o aéreos o la red eléctrica de una ciudad. 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,es decir,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 el punto 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. Su estudio 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 no dirigido,puesto que una misma carretera puede ser recorrida en ambos sentidos.No obstante,podemos dar unas definiciones generales para ambos tipos.

Cibergrafia

http://teoriagrafosgerson.blogspot.com.co/2008/08/historia-de-la-teoria-de-grafos.html