Un grafo

GRAFOS

Un grafo es un conjunto de puntos (vértices) en el espacio consta de dos cosas:

• Un conjunto N cuyos elementos se llaman nodos, puntos o vértices.

• Un conjunto S de parejas no ordenadas de nodos diferentes, llamadas segmentos, aristas o arcos.

En un computador además de permitir organizar información, resultan estructuras útiles para resolver ciertos tipos de problema.

Un grafo G es una pareja G=(V,A), donde V es un conjunto finito (i.e vértices) y A es un subconjunto del conjunto de parejas no ordenadas de V (i.e arcos). Por ejemplo G=({a,b,c},{{a,c},{c,b}})

En muchas aplicaciones de los grafos las aristas llevan asociada información adicional. En ese caso

hablaremos de grafos etiquetados. Si esa información es numérica y tiene el significado del coste

necesario para recorrer esa arista, entonces usaremos el nombre de grafo ponderado o red.

Red: Grafo en el que cada arista lleva asociado un coste (de aquí en adelante lo llamaremos longitud)

Terminología

Dos vértices i y j son adyacentes si existe una arista que los conecte (es decir, si 〈i, j〉 ∈ A)

El grado de un vértice en un grafo no dirigido es igual al número de vértices adyacentes a él (número de aristas donde el vértice aparece como el primer o segundo componente de la arista). Por ejemplo, en la figura 1 el vértice 1 tiene grado 2, y el vértice 3 tiene grado 4.

En un grafo dirigido se distingue entre grado interior de un vértice (número de aristas que llegan a él, es decir aristas donde el vértice aparece como segundo componente) y grado exterior (número de aristas que salen de él, aristas donde el vértice aparece como primer componente).

Un camino entre dos vértices i y j es cualquier secuencia de vértices, v1 , … , vk , … , vp que cumpla que v1 = i, vp = j y exista una arista entre cada par de vértices contiguos: ∀ k : 〈vk , vk +1〉 ∈ A

Un camino simple es aquel donde no hay vértices repetidos en la secuencia, salvo el primero y el último (que pueden ser iguales o distintos). Un ciclo es un camino simple donde el vértice inicial y el final son el mismo (i = j).

Un grafo se dice que es a cíclico si todos sus posibles caminos son simples (no existen ciclos). Por ejemplo el grafo de la figura 1 sería a cíclico si eliminásemos los vértices 〈1,2〉 y 〈2,4〉 (se entiende que automáticamente desaparecen 〈2,1〉 y 〈4,2〉).

Se dice que un grafo está conectado si existe como mínimo un camino entre cualquier par de vértices distintos. Por ejemplo, el grafo de la figura 1 está conectado, pero el de la figura 2 no (no hay camino que vaya de 3 a 1, etc.)

Un grafo esta completamente conectado si para cada vértice existen aristas que lo conecten con los n-1 vértices restantes. Este tipo de grafo tiene el número máximo posible de aristas, n•(n-1)/2. Por lo tanto m ∈ O(n2)

Si un grafo contiene ciclos, el número de posibles caminos es infinito. Si queremos enumerar el número de posibles caminos simples, el peor caso es un grafo completamente conectado, y entonces el número de posibles caminos simples es de n!

Se define longitud/coste de un camino como suma de las longitudes de las aristas que recorre el camino (recordar que en un grafo que no sea red las aristas tienen longitud unidad).

Se puede definir entonces la longitud de un camino por medio de la función longitud entre dos vértices, definida anteriormente: (no confundir ambas funciones, aunque tengan el mismo nombre sus parámetros son distintos)

Para un grafo conectado, se define ruta óptima entre los vértices i y j como el camino de longitud mínima entre los vértices i y j.

Se denominará distancia entre los vértices i y j a la longitud de su ruta óptima.

Las operaciones básicas sobre grafos

...