REPRESENTACION SECUENCIAL DE GRAFOS

INDICE _

INTRODUCCIÓN

GRAFOS

 CONCEPTO

 TERMINOLOGÍA

REPRESENTACION SECUENCIAL DE GRAFOS

 MATRIZ DE ADYACENCIA

 MATRIZ DE CAMINOS 2

3

3

4

8

8

9

INTRODUCCION _

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.(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, 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).

GRAFOS _

Un grafo está formado por un conjunto de nodos(o vértices) y un conjunto de arcos. Cada arco en un grafo se especifica por un par de nodos.

El conjunto de nodos es {A, B, C, D, F, G, H} y el conjunto de arcos {(A, B), (A, D), (A,

C), (C, D), (C, F), (E, G), (A, A)} para el siguiente grafo

Si los pares de nodos en los arcos dirigidos, el grafo se denomina grafo directo, dirigido o dígrafo.

TERMINOLOGIA.-

• Grafos dirigidos son un grafo en el cual toda arista es dirigida se denomina “Digrafo” o bien “grafo dirigido”, es decir, que todo arco tiene un origen y un destino.

• Grafos no dirigidos: Un grafo en el cual no todas las aristas son dirigidas se denomina “grafos no dirigidos”. El gafo no dirigido es aquel que no tiene sentido su arista.

• Un grafo mixto, es aquel que contiene tantos arcos como aristas dirigidos como no dirigidas.

• Se llama camino, a una secuencia de aristas (V1, V2……V3) de la manera que el vértice final de cada uno sirve de vértice al siguiente.

• El camino elemental o trayectoria: es un camino que pasa por una serie de vértices una sola vez. Es decir, es aquel que no pasa 2 veces por un mismo vértice, salvo que el vértice que se repite sea el inicio y el final.

El camino (c, d, e, c)

• El camino simple: o sendero, es un camino que pasa por una serie de aristas una sola vez, todo camino elemental es un camino simple pero la inversa puede no cumplirse.

• Un lazo o bucle en un grafo es un enlace cuyos puntos finales son el mismo nodo. Un grafo se dice simple si no tiene lazos y existe como mucho un enlace entre cada par de nodos (no

...