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.