grafo dearrollo de software


GRAFOS


1. INTRODUCCIÓN.
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 decarreteras,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 conjuntode 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 vistade 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íadividirse 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 mismacarretera puede ser recorrida en ambos sentidos.No obstante,podemos dar unas definiciones generales para ambos tipos.
A continuación daremos definiciones de los dos tipos de grafos y de los conceptos que llevan asociados.
2. DEFINICIONES Y TERMINOLOGÍA FUNDAMENTAL.
Un grafo G es un conjunto en el que hay definida una relación binaria,es decir,G=(V,A) tal que V es un conjunto de objetos a losque denominaremos vértices o nodos y es una relación binaria a cuyos elementos denominaremos arcos o aristas.
Dados ,puede ocurrir que:
1. , en cuyo caso diremos que x e y están unidos mediante un arco,y
2. , en cuyo caso diremos que no lo están.
Si las aristas tienen asociada una dirección(las aristas (x,y) y (y,x) no son equivalentes) diremos que el grafo es dirigido,en otro caso((x,y)=(y,x)) diremos que el grafo es no dirigido.


Conceptos asociados a grafos:
Diremos que un grafo es completo si A=VxV,o sea,si para cualquier pareja de vértices existe una arista que los une(en ambos sentidos si el grafo es no dirigido).El número de aristas será:
grafos dirigidos:


grafos no dirigidos:


donde n=|V|

Un grafo dirigido es simétrico si para toda arista(x,y)perteneciente a A también aparece la arista (y,x)perteneciente a A;y es antisimétrico si dada una arista (x,y) perteneciente a A implica que (y,x) no pertenece a A.

Tanto a las aristas como a los vértices les puede ser asociada información.A esta información se le llama etiqueta.Si la etiqueta que se asocia es un número se le llama peso,costo o longitud.Un grafo cuyas aristas o vértices tienen pesosasociados recibe el nombre de grafo etiquetado o ponderado.

El número de elementos de V se denomina orden del grafo.Un grafo nulo es un grafo de orden cero.

Se dice que un vértice x es incidente a un vértice y si existe un arco que vaya de x a y ((x,y)pertenece a A),a x se le denomina origen del arco y a y extremo del mismo.De igual forma se dirá que y es adyacente a x.En el caso de que el...