El origen de la teoría de grafos

1.INTRODUCCIÓN

El origen de la teoría de grafos suele situarse en el problema de “los siete puentes de Könisberg”, propuesto por elmatemático alemán Euler.“¿Se puede trazar un paseo circular que pasa por los 7 puentes sin repetir ninguno?”Realmente, la forma y dimensión de las islas y las orillas no tienen importancia, el problema se puede formular utilizando el siguiente gráfico, donde los vértices son las islas y orillas del río y las aristas los puentes.

Los grafos son modelos matemáticos que reproducen numerosas situaciones reales como: una red decarreteras, la red de enlaces ferroviarios o aéreos, la red eléctrica de una ciudad, circuitos electrónicos,diagramas de flujo de los algoritmos, redes de ordenadores, etc.Gráficamente el grafo se representa como un conjunto de puntos (vértices o nodos) unidos a través de líneas(arcos o aristas). Así por ejemplo las diferentes estructuras de flujo de un lenguaje de programación de altonivel podrían representarse de la siguiente manera:

Los grafos son estructuras de datos no lineales que tienen una naturaleza generalmente dinámica. Definimosun grafo como un conjunto finito de vértices unidos por un conjunto de arcos. Luego, el grafo G se representa por

G = (V, E)

, donde V es el

conjunto de vértices o nodos

y E el conjunto de

arcos o aristas

.Como cada uno de los arcos del conjunto E es un par de vértices del conjunto V de la forma [v1, v2] donde v1,v2

∈

V. Si este par se considera ordenado, entonces hablaremos de

GRAFOS DIRIGIDOS o DIGRAFOS

. Enotro caso, si el par NO se considera ordenado, estaremos hablando de

GRAFOS NO DIRIGIDOS

.

Si el grafo es No dirigido se cumple que si [v1, v2]

∈

E, entonces implica que [v2, v1]

∈

...