Grafos

Un grafo G consiste en un conjunto de vértices V y un conjunto de arcos o aristas E que unen estos vértices. Si todo arco puede ser recorrido en ambos sentidos, el grafo es no dirigido. Para el caso de grafos dirigidos, cada arco tiene una dirección, generalmente representado por su nodo origen y su nodo destino.

Definiciones

Camino: secuencia de vértices v1, v2, v3, ... , vn.

Longitud de camino: número de arcos.

Camino simple: todos sus vértices, excepto tal vez el primero y el último son distintos.

Vértice adyacente: un nodo o vértice v es adyacente al nodo w si existe un arco de w a v.

Arista adyacente: dos aristas de un grafo son llamadas adyacentes si tienen un vértice en común.

Ciclo simple: es un camino simple de longitud por lo menos de uno que empieza y termina en el mismo vértice.

Aristas paralelas: aristas con el mismo vértice inicial y terminal.
Grafo cíclico: contiene por lo menos un ciclo.
Grafo acíclico: no contiene ciclos.
Grafo conexo: para cada par de nodos (v,w) existe un camino de v a w y de w a v.
Grafo fuertemente conexo: para cada par de nodos (v,w) existen por lo menos dos caminos disjuntos de v a w y de w a v, de manera que no exista un vértice tal que al sacarlo el grafo resultante sea disconexo.
Grafo completo: para cada par de nodos (v,w) existe una arista de v a w y de w a v.
Grafo unilateralmente conexo: para cada par de nodos (v,w) de g hay un camino de v a w o un camino de w a v (esto tiene sentido sólo en el contexto de un grafo dirigido).
Grafo pesado o etiquetado: sus aristas contienen datos. Una etiqueta puede ser un nombre, costo o un valor de cualquier tipo de dato. También a este grafo se lo denomina red de actividades, y el número asociado al arco se le denomina factor de peso.
Longitud de camino con pesos: suma de los pesos de las aristas en el camino.
Grado de salida de un nodo: es el número de arcos o aristas que empiezan en él.
Grado de entrada de un nodo: es el número de arcos o aristas que terminan en él.
Nodo fuente: tiene grado de salida positivo y un grado de entrada nulo.
Nodo sumidero: tiene grado de salida nulo y un grado de entrada positivo.

En la mayoría de los casos los grafos son dispersos: cuanto mucho una arista entre un vértice y otro

E $\leq$ #V $^{2}$ , más aún: #E = O(#V).

Caso contrario se denominan densos.

Representación de los grafos

Representación por incidencia

Lista de incidencia

El grafo está representado por un arreglo de aristas, identificadas por un par de vértices, que son los que conecta esa arista.

Matriz de incidencia

El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (conectado o no conectado).

Representación por adyacencia

Listas de adyacencia

El grafo está representado por un arreglo de listas de adyacencia. Para un vértice i, la lista de adyacencia está formada por todos los vértices adyacentes a i. Puede construirse en tiempo lineal, y las inserciones pueden hacerse al principio de cada lista, con lo que se asegura tiempo constante.

Matriz de adyacencia

Una matriz de adyacencia es una matriz M de dimensión n*n, en donde n es el número de vértices que almacena valores booleanos, donde M[i,j] es verdadero (o contiene un peso) si y solo si existe un arco que vaya del vértice i al vértice j. La inicialización llevaría un tiempo del O ( #(V $^{2}$ )).