Terminología en grafos

Publicado en Estructura de datos

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 aciclíco 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.

Fuente: Apunte de Estructura de Datos del Instituto tecnológico de la Paz