HISTORIA

El llamado problema de "los siete puentes de Knigsberg" fue lo que dio origen a la teora de grafos. Cabe sealar que Knigsberg era Prusia oriental en el siglo XVIII y actualmente, Kaliningrado, provincia Rusa. Durante mucho tiempo se intent resolver el siguiente problema:

En la ciudad de Knigsberg hay una isla y el ro Pregel que la rodea se divide en dos brazos (como aparece en la imagen). La distintas zonas de tierra estn unidos mediante siete puentes (color rojo). Es posible dar un paseo por la ciudad, empezando por cualquiera de las cuatro partes de tierra firme, cruzando cada puente una y slo una vez y volver nuevamente al punto de partida?

Despus de un tiempo, en 1736, Leonhard Euler dio respuesta a este problema, dando origen a la teora de grafos. l represent por un punto cada sector de tierra y por una lnea cada puente, uniendo los distintos puntos con tantas lneas como puentes haya entre dichos sectores, creando de esta forma, al primer grafo de la historia.

La representacin de Euler fue similar a la siguiente imagen:

Euler se dio cuenta que la cantidad de lneas de cada punto tendra que ser par, para as poder entrar y salir de dicho punto, ocupando tan solo una vez cada puente.

En el problema de Knigsberg, Euler demostr que era imposible recorrer la ciudad de la forma pedida, ya que el nmero de lneas que llegan a cada punto es impar y sto implica que no es posible recorrerlos pasando una sola vez por cada uno de los puentes, es decir, no haba solucin para ese problema.

GRAFOS NO DIRIGIDOS ESTTICOS

Antes de explicar grafos no dirigidos estticos haremos hincapi en algunos conceptos

MATRIZ DE ADYACENCIA

Lamatriz de adyacenciaes unamatrizcuadradaque se utiliza como una forma de representarrelaciones binarias (0-1).

1. Se crea unamatriz cero, cuyas columnas y filas representan losnodosdel grafo.2. Por cada arista que une a dos nodos, se suma1al valor que hay actualmente en la ubicacin correspondiente de la matriz.Si tal arista es unbucley el grafo esno dirigido, entonces se suma2en vez de 1.

Matriz adyacente

GRAFOS NO DIRIGIDOS

Sea G un grafo no dirigido donde G =(V,E) donde V corresponde al conjunto de vrtices y E el conjunto de aristas del grafo, un grafo no dirigido se diferencia de un grafo dirigido porque cada arista en E es un par no ordenado de vrtices.Cuando no importa la direccin de una arista, el grafo se denomina no dirigido lo muestra la figura Una aplicacin de los grafos no dirigidos, es la red de computadoras de una empresa, en donde los vrtices estn representados en las terminales de los computadores y las aristas son el cableado o en su defecto la coneccin inhalambrica.En ese sentido la informacin de la red se da en ambos sentidos al enviar y recibir informacin de cada terminal.

ACDB

V={a,b,c,d}E={(a,c);(c,a);(a,b);(b,a);(b,c);(c,b);(b,d);(d,b);(c,d);(d,c)}

En general el trmino grafo hace referencia a un grafo no dirigido, a menos que se especifique lo contrario.

Cuando nos referimos a grafos no dirigidos estticos estticos estos se relacionan con tablas de adyacencia, se trabaja como si fuera una matriz cuadrada donde se relaciona cada nodo con otro.

TIPOS DE ABSTRACTO DE DATOS (TAD) DE GRAFOS NO DIRIGIDOS ESTTICOS

Cuando hablamos de un tipo abstracto de datos nos referimos a unmodelo matemticocompuesto por una coleccin deoperacionesdefinidas sobre un conjunto de datospara el modelo de un problema real. En este caso nos referiremos a grafos.ya teniendo los conceptos mas antes expuestos un TAD de grafos no dirigidos estticos viene a ser una representacin abstracta de grafos cuyas aristas q se relacionan con los vrtices carecen de sentido u orientacin y que estas se relacionan con tablas de adyacencia, se trabaja como si fuera una matriz cuadrada donde se relaciona cada nodo con otro