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.

...