Estructura de Datos

GRAFOS

¿QUÉ ES UN GRAFO?

Un grafo G es un conjunto no vacío V (de vértices) y un conjunto A (de
aristas) extraído de la colección de subconjuntos de dos elementos de V. Una arista de G es,
pues, un subconjunto {a, b}, con a, b ∈ V , a = b.

Los grafos se pueden clasificar en dos grupos:

Dirigidos y no Dirigidos, de los cuales enfocaremos e los términos más adelante.

CLASES DE GRAFOS:

A continuación enumeraremos algunas clases de grafos que aparecerán continuamente en
lo que sigue; conviene recordar sus nombres y características.
Diremos que un grafo es un Ln, un grafo lineal con n v´ertices (n ≥ 2) si tiene n vértices
(dos de grado 1 y el resto, si los hay, de grado 2) y es isomorfo a:

Otra clase de grafos muy relevante son los llamados grafos circulares con n vértices

(todos de grado 2), para n ≥ 3, que denotaremos por Cn:

Si un grafo con n vértices tiene todas las (n/2) posibles aristas, diremos que estamos ante el grafo completo con n vértices, Kn:

GRAFOS DIRIGIDOS:

Un grafo dirigido es simétrico si para toda arista (x,y)perteneciente a A también aparece la arista (y,x)perteneciente a A;y es antisimétrico si dada una arista (x,y) perteneciente a A implica que (y,x) no pertenece a A.

En un grafo no dirigido el par de vértices que representa un arco no está ordenado

Tanto a las aristas como a los vértices les puede ser asociada información.A esta información se le llama etiqueta.Si la etiqueta que se asocia es un número se le llama peso,costo o longitud.Un grafo cuyas aristas o vértices tienen pesos asociados recibe el nombre de grafo etiquetado o ponderado.

El número de elementos de V se denomina orden del grafo.Un grafo nulo es un grafo de orden cero.

Se dice que un vértice x es incidente a un vértice y si existe un arco que vaya de x a y ((x,y)pertenece a A),a x se le denomina origen del arco y a y extremo del mismo.De igual forma se dirá que y es adyacente a x.En el caso de que el grafo sea no dirigido si x es adyacente(resp. incidente) a y entonces y también es adyacente (resp. incidente) a x.

Se dice que dos arcos son adyacentes cuando tienen un vértice común que es a la vez origen de uno y extremo del otro.

Se denomina camino (algunos autores lo llaman cadena si se trata de un grafo no dirigido)en un grafo dirigido a una sucesión de arcos adyacentes:

C={(v1,v2),(v2,v3),...,(vn-1,vn), para todo vi perteneciente a V}

Esos son solo algunos de las clases de grafos que existen.

LONGITUD DEL CAMINO:

Es el número de arcos que comprende y en el caso en el que el grafo sea ponderado se calculará como la suma de los pesos de las aristas que lo constituyen.

CLASES DE GRAFOS

Un camino se dice simple cuando todos sus arcos son distintos y se dice elemental cuando no utiliza un mismo vértice dos veces.Por tanto todo camino elemental es simple y el recíproco no es cierto.

Un camino se dice Euleriano si es simple y además contiene a todos los arcos del grafo.

Un circuito(o ciclo para grafos no dirigidos)es un camino en el que coinciden los vértices inicial y final.Un circuito se dice simple cuando todos los arcos que lo forman son distintos y se dice elemental cuando todos los vértices por los que pasa son distintos.La longitud de un circuito es el número de arcos que lo componen.Un bucle es un circuito de longitud 1(están permitidos los arcos de la forma(i,i) y notemos que un grafo antisimétrico carecería de ellos).

Un circuito elemental que incluye a todos los vértices de un grafo lo llamaremos circuito Hamiltoniano.

Un grafo se denomina simple si no tiene bucles y no existe más que un camino para unir dos nodos.

Diremos que un grafo no dirigido es bipartido si el conjunto de sus vértices puede ser dividido en dos subconjuntos(disjuntos) de tal forma que cualquiera de las aristas que componen el grafo tiene cada uno de sus extremos en un subconjunto distinto.Un grafo no dirigido será bipartido si y sólo si no contiene ciclos con un número de aristas par.

Matriz de Adyacente:

Lista de Adyacente:

En esta estructura de datos la idea es asociar a cada vertice i del grafo una lista que contenga todos aquellos vértices j que sean adyacentes a él. De esta forma sólo reservará memoria para los arcos adyacentes a i y no para todos los posibles arcos que pudieran tener como origen i. El grafo, por tanto, se representa por medio de un vector de n componentes (si |V|=n) donde cada componente va a ser una lista de adyacencia correspondiente a cada uno de los vertices del grafo. Cada elemento de la lista consta de un campo indicando el vértice adyacente. En caso de que el grafo sea etiquetado, habrá que añadir un segundo campo para mostrar el valor de la etiqueta.