Tipos de Grafos

Tipos de Grafos

La primera impresión que podemos tener a la hora de trabajar con grafos, es que los podemos construir de la forma que nos plazca, sólo tienen como límite nuestra propia imaginación. Por ello es necesario, tratar de organizar los grafos y clasificarlos en diferentes tipos, dependiendo de las características que posean.

En primera instancia, supongamos que podemos nombrar las aristas de un grafo, es decir, representar las aristas de un grafo mediante un símbolo en específico, en lugar de un par no ordenado. Sí hacemos esto, el grafo de la figura 1.5, lo podemos convertir en un grafo como el de la figura 1.7.

Ejemplo: 1.2.2.1 Podemos representar el grafo de la figura 1.7 como:

G = (V, E); 

V = {1, 2, 3, 4} 

E = {a, b, c, d, e} 

A simple vista, puede resultar más conveniente para la comprensión de un grafo, el uso de etiquetas en las aristas. De aquí nace el primer tipo de grafo.

Grafo Etiquetado. Un grafo G = (V, E) es llamado etiquetado cuando sus aristas contienen datos (etiquetas). Una etiqueta puede ser un nombre, costo ´o un valor de cualquier tipo de dato. También a este grafo se le denomina red de actividades.

Los grafos etiquetados serán de especial interés para nosotros en los siguientes capítulos. Pero, hasta ahorita, no nos ha importado el orden, es decir que, por ejemplo en el grafo de la figura 1.7, a = (1,2), pero perfectamente podríamos escribir que a = (2,1), ya que no nos interesa la dirección en la que se dirigen las aristas. Pero, ¿qué pasaría si la dirección si nos importara? Pues de aquí, resulta otro tipo de grafo, donde el orden si nos va importar. Generalmente, cuando el orden, o la dirección de los vértices nos importen, vamos a reemplazar las aristas por flechas, que indiquen la dirección que se debe respetar de vértice a vértice.

Grafo Dirigido o Dígrafo. Un grafo G = (V, E) es llamado dirigido, cuando consta de un conjunto V de vértices y un conjunto E de aristas, que son pares ordenados de elementos de V.

De manera inmediata, se puede decir que el orden sí importa en los grafos dirigidos, por lo cual podemos definir el conjunto E como un conjunto estrictamente de pares ordenados. En un grafo dirigido (x, y) 6= (y, x), por lo que el grafo se puede definir de una única manera.

Ejemplo: 1.2.2.2 El grafo de la figura 1.8, lo podemos representar de una única manera como sigue:

G = (V, E);

V = {1, 2, 3,4}

E = {(1,1), (1,2), (1,3), (2,4), (3,2)}

Además de ´estas, hoy otros tipos de grafos a considerar.

Se dice que dos aristas son paralelas, si comparten los mismos vértices.

Grafo Simple. Es un grafo que no tiene lazos ni aristas paralelas.

Un grafo que no es simple, se le llama multígrafo.

Ejemplo: 1.2.2.3 En la figura 1.9, puede observar que el grafo (a) es simple, ya que no contiene lazos ni aristas paralelas, en cambio el grafo (b), contiene aristas paralelas, por lo cual es un multígrafo.

Grafo completo.  Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices debe tener una arista que los une.

Si un grafo no es completo, simplemente lo llamaremos no completo. Lógico, ¿no?

Ejemplo: 1.2.2.4 En la figura 1.10, puede observar que el grafo (a) es completo, debido a que todos los pares de vértices están conectados entre sí. Por otra parte, el grafo (b) no es completo.

Grafo bipartito. Un grafo G es bipartito cuando sus vértices son la unión de dos grupos de vértices y cumple las siguientes condiciones:

a. Los conjuntos de vértices son disjuntos y no vacíos Es decir V = V1 ∪ V2; y además V1 ∩V2 = ∅.

b. Cada arista de E une un vértice del primer conjunto con uno del segundo conjunto.

c. No existen aristas uniendo dos elementos de V1; análogamente para V2.

Ejemplo: 1.2.2.5 Observe el grafo de la figura 1.11. Sean V1 = {A, B, C, D, F} y V2 = {1, 3, 3,4}. Entonces, dicho grafo cumple con las condiciones para ser un grafo bipartito.

Hasta ahorita hemos visto diferentes tipos de grafos, en términos de las características que cumplen, pero es necesario ver otras definiciones importantes relacionadas a los grafos.