INTEGRANTES DEL EQUIPO

EMMANUEL MARTINEZ HERNANDEZ
JESUS TORRES SANCHEZ
ERICK J. DOMINGUEZ

4.2.2. 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 sencilla. Cuando se inserte una nueva arista en el grafo, habrá que añadir un nuevo nodo a la lista de adyacencia (lista que almacena los nodos a los que un vértice puede acceder mediante una arista) del nodo origen, así si se añade la arista (A,C), se deberá incluir en la lista de adyacencia de A el vértice C como nuevo destino.

Eliminar vértice

Esta operación es inversa a la inserción de vértice. En este caso el procedimiento a realizar es la eliminación de la tabla de vértices del vértice en sí. A continuación habrá que eliminar las aristas que tuviesen al vértice borrado como origen o destino.

Eliminar arista

Mediante esta operación se borra un arco del grafo. Para llevar a cabo esta acción es necesario eliminar de la lista de adyacencia del nodo origen el nodo correspondiente al nodo destino.

Otras operaciones

Las operaciones adicionales que puede incluir un grafo son muy variadas. Además de las clásicas de búsqueda de un elemento o recorrido del grafo, también podemos encontrarnos con ejecución de algoritmos que busquen caminos más cortos entre dos vértices, o recorridos del grafo que ejecuten alguna operación sobre todos los vértices visitados, por citar algunas operaciones de las más usuales.

4.2.1. TERMINOLOGIA DE GRAFOS

Terminología Grafos

La terminologí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-&gtV2, V2-&gtV3, V1-&gtV3.

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 de longitud 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 a cíclico cuando no contiene ciclos.

GRAFO CONEXO. Un grafo G es conexo, si y solo si existe un 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 cada par 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értice V 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.

NODO SUMIDERO. Se le llama sumidero al nodo que tiene grado de salida nulo y un grado de entrada positivo.