GRAFOS: Terminología

7.2 Terminología

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.
Página anterior
Página siguiente