GRAFOS 4 1

GRAFOS
Un grafo dirigido G consiste en un conjunto de
vértices V y un conjunto de arcos o aristas A. Los
vertices se denominan también nodos o puntos. Un
arco, es un par ordenado de vértices(V,W)donde V
es el vértice inicial y W es el vértice terminal del
arco. Un arco se expresa como: V-->W y se
representa de la siguiente manera:
V

W

Los vértice de un grafo pueden usarse para representarobjetos. Los
arcos se
utilizan para representar relaciones entre estos objetos.
Las aplicaciones más importantes de los grafos son las siguientes:
• Rutas entre ciudades.
• Determinar tiempos máximos ymínimos en un proceso.
• Flujo y control en un programa.

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>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 últimoson
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érticeinicial 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.
• GRAFOCONEXO. 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.Ungrafo 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...