Grafos

GRAFOS
Un grafo en el ámbito de las ciencias de la computación es una estructura de datos, en concreto un tipo abstracto de datos (TAD), que consiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos. El concepto de grafo TAD desciende directamente del concepto matemático de grafo.
Informalmente se define como G = (V,E), siendo los elementos de V los vértices, y los elementos de E, las aristas (edges en inglés). Formalmente, un grafo, G, se define como un par ordenado, G = (V, E), donde V es un conjunto finito y E es un conjunto que consta de dos elementos de V.




Existen diferentes implementaciones del tipo grafo: con una matriz de adyacencias (forma acotada) y con listas y multilistas de adyacencia(no acotadas).
• Matriz de adyacencias: se asocia cada fila y cada columna a cada nodo del grafo, siendo los elementos de la matriz la relación entre los mismos, tomando los valores de 1 si existe la arista y 0 en caso contrario.

• Lista de adyacencias: se asocia a cada nodo del grafo una lista que contenga todos aquellos nodos que sean adyacentes a él.


TERMINOLOGÍA DE GRAFOS
Laterminología que manejaremos regularmente para el uso de grafos es la siguiente:
• CAMINO. Es una secuencia de vértices V1, V2, V3, ... , Vn, tal que cada uno de estos V1->V2, V2->V3, V1->V3.
• LONGITUD DE CAMINO. Es el número de arcos en ese camino.
• CAMINO SIMPLE. Es cuando todos sus vértices, excepto tal vez el primero y el último son distintos.
• CICLO SIMPLE. Es un camino simple delongitud por lo menos de uno que empieza y termina en el mismo vértice.
• ARISTAS PARALELAS. Es cuando hay más de una arista con un vértice inicial y uno terminal dados.
• GRAFO CICLICO. Se dice que un grafo es cíclico cuando contiene por lo menos un ciclo.
• GRAFO ACICLICO. Se dice que un grafo es aciclíco cuando no contiene ciclos.
• GRAFO CONEXO. Un grafo G es conexo, si y solo si existeun camino simple en cualesquiera dos nodos de G.
• GRAFO COMPLETO ó FUERTEMENTE CONEXO.Un grafo dirigido G es completo si para cada par de nodos (V,W) existe un camino de V a W y de W a V (forzosamente tendrán que cumplirse ambas condiciones), es decir que cada nodo G es adyacente a todos los demás nodos de G.
• GRAFO UNILATERALMENTE CONEXO.Un grafo G es unilateralmente conexo si para cadapar de nodos (V,W) de G hay un camino de V a W o un camino de W a V.
• GRAFO PESADO ó ETIQUETADO. Un grafo es pesado cuando sus aristas contienen datos (etiquetas). Una etiqueta puede ser un nombre, costo ó un valor de cualquier tipo de dato. También a este grafo se le denomina red de actividades, y el número asociado al arco se le denomina factor de peso.
• VERTICE ADYACENTE. Un nodo o vérticeV es adyacente al nodo W si existe un arco de m a n.
• GRADO DE SALIDA.El grado de salida de un nodo V de un grafo G, es el número de arcos o aristas que empiezan en V.
• GRADO DE ENTRADA.El grado de entrada de un nodo V de un grafo G, es el número de aristas que terminan en V.
• NODO FUENTE.Se le llama así a los nodos que tienen grado de salida positivo y un grado de entrada nulo.
• NODOSUMIDERO.Se le llama sumidero al nodo que tiene grado de salida nulo y un grado de entrada positivo
OPERACIONES BASICAS SOBRE GRAFOS

Operaciones básicas de los grafos
En los grafos, como en todas las estructuras de datos, las dos operaciones básicas son insertar y borrar. En este caso, cada una de ellas se desdobla en dos, para insertar/eliminar vértices e insertar/eliminar aristas.Insertar vértice
La operación de inserción de un nuevo vértice es una operación muy sencilla, únicamente consiste en añadir una nueva entrada en la tabla de vértices (estructura de datos que almacena los vértices) para el nuevo nodo. A partir de ese momento el grafo tendrá un vértice más, inicialmente aislado, ya que ningúna arista llegará a él.
Insertar arista
Esta operación es también muy...