Lab. Algoritmos computacionales: Grafos

Un grafo es una estructura de datos, específicamente es un tipo abstracto de datos (TAD), que consiste en un grupo de nodos a los cuales también le podemos llamar vértices y un grupo de aristas que establecen relaciones entre las vértices. El concepto de grafo TAD tiene su origen directamente del concepto matemático de grafo.

Se define como G = (V, E), siendo los elementos de V los vértices, y los elementos de E las aristas. Un grafo, G, es definido como un par ordenado, G = (V, E), donde V es un conjunto n finito de vértices u, v, w que pertenecen a V y E es un conjunto m de aristas que consta de dos elementos de V.

Representación visual de grafos.

Le llamamos orden del grafo G a su número de vértices, | V |.
El grado de un vértice o nodo V es igual al número de vértices E que encontramos en él.
Un bucle es una arista que conecta un vértice consigo mismo, es decir, una arista donde el nodo inicial y el nodo final coinciden.

El complemento o inverso de un grafo G = (V,E) es un grafo G' =(V,E'), con el mismo conjunto de vértices y tal que dos vértices de G' son adyacentes si solo si no son adyacentes en G. Para conseguir el complemento de un grafo, debemos completar todas las aristas que faltan para hacerlo completo, y quitar todas las aristas del grafo G original.

Imagen que representa un grafo de Petersen (izquierda) y grafo complemento (derecha).

Tipos de grafos

Un grafo es plano cuando se puede dibujar en dos dimensiones, cuando ninguna arista cruza con otra.

Grafo no dirigido

Un grafo no dirigido o grafo propiamente dicho es un grafo G = (V,E) donde:

es un conjunto de pares no ordenados de elementos de V.

Un par no ordenado es un conjunto de la forma

{a,b}

, de manera que

{a,b} = {b,a}

Representación visual de un grafo no dirigido.

Para grafos simples no dirigidos se define la densidad de grafo de la siguiente forma:

D = 2 | E | / | V | ( | V | - 1 )

El número máximo de aristas es ½ |V| |V−1|, de tal manera que la densidad máxima es 1 para un grafo completo y la densidad mínima es de 0.

Grafo dirigido

Un grafo dirigido o digrafo es un grafo

G = (V,E)

donde:

es un grupo de pares ordenados de elementos de V.

Dada una arista (a,b), a es su nodo inicial y b su nodo final. Con esto llegamos a que los grafos dirigidos no contienen bucles.

Representación visual de un grafo dirigido.

Pseudografo

Un pseudografo dirigido es un grafo

G = (V,E)

donde:

es un conjunto de pares ordenados y etiquetados de elementos de V.

Es decir, un pseudografo es un grafo no dirigido que acepta bucles en E.

Representación visual de pseudografo.

Pseudografo dirigido

Un pseudografo dirigido es un grafo

G = (V,E)

donde:

es un conjunto de pares ordenados y etiquetados de elementos de V.

Es decir, un pseudografo dirigido es un grafo dirigido que acepta bucles en E.

Formas de representación

Existen distintas formas de poner en funcionamiento del tipo grafo: con una matriz de adyacencias (forma acotada) y con listas y multilistas de adyacencia (no acotadas).

Matriz de adyacencias: se liga cada fila y cada columna a cada nodo del grafo, siendo los elementos de la matriz la relación entre los mismos, se toma los valores de 1 si existe la arista y 0 en caso contrario.

Representación de una matriz de adyacencias.

Lista de adyacencias: se liga a cada nodo del grafo una lista que tenga todos aquellos nodos que sean adyacentes a él.

Representación de una lista de adyacencias.

Grafo bipartito

Un Grafo bipartito se denomina a un grafo cuyos vértices se pueden separar en dos conjuntos disjuntos

V 1

V 2

y las aristas siempre unen vértices de un conjunto con vértices de otro:

Los dos conjuntos U y V se pueden pensar como un coloreo del grafo teniendo dos colores, si pintamos los vértices en U de azul y los vértices de V con verde obtendremos un grafo de dos colores donde cada arista tiene un vértice azul y el otro verde. Sin embargo, si un gráfico no tiene la propiedad de que se puede colorear con dos colores no es bipartito.