Teoría de Grafos

En este apartado estudiaremos la Teoría de Grafos, empezaremos definiendo:

¿Qué es un grafo?

Un grafo G es una dupla G = (V, E), donde V es un conjunto finito y no vacío de elementos llamados vértices y E es el conjunto cuyos elementos se componen de subconjuntos de V de cardinalidad dos (2), llamados aristas.

Tipos de Grafos

1. 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.

 Ejemplo: 

Podemos representar el grafo etiquetado como:

G = (V, E)

V = {A, B, C}

E = {1, 2, 3}

 2. 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.

Tipo de grafo en el cual las aristas tienen una dirección definida, a diferencia del grafo generalizado, en el cual la dirección puede estar especificada o no

Ejemplo:

Podemos representar el grafo dirigido como:

G = (V, E)

V = {1, 2, 3, 4}

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

3. Grafo simple: Es un grafo que no tiene lazos ni aristas paralelas.

4. Grafo Multígrafo: Es un grafo que tiene aristas paralelas.

5. 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.

6. 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.

 

Espero les haya sido de ayuda la información brindada. Si tenéis alguna duda dejarla en los comentarios.