6.1.2 Tipos de grafos
Podemos clasificar los grafos en dos grupos: dirigidos y no dirigidos. En un grafo no dirigido el par de vértices que representa un arco no está ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que y representan dos arcos diferentes.
Ejemplo:
G1 = (V1, A1)V1 = {1, 2, 3, 4} A1 = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}G2 = (V2, A2)V2 = {1, 2, 3, 4, 5, 6} A2 = {(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)}G3 = (V3, A3)V3 = {1, 2, 3} A3 = { <1, 2>, <2, 1>, <2, 3> }
Gráficamente estas tres estructuras de vértices y arcos se pueden representar de la siguiente manera:
Hay también 6 tipos principales de grafos;
Grafo simple:
Se dice que el grafo G = (V, E) es un grafo simple de grado n si todos sus vértices tienen grado n.
Grafo completo:
Un grafo es completo si cada par de vértices está unido por una arista. Se denota por Kn al grafo completo de n vértices.
Ejemplos
Grafo bipartido:
.Un grafo es bipartido completo si V=V1? V2 y dos vértices de V están unidos por una arista de E si y solo si un vértice está en V1 y el otro en V2. Se denota por Kr,sal grafo bipartido completo donde V1 tiene r vértices y V2 tiene s vértices
Grafos planos:
Un grafo plano es aquel que puede ser dibujado en el plano sin que ninguna arista se interseque.
Grafos conexos.
Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b
Grafo ponderado:
Un grafo es ponderado si presenta los pesos de cada arista y se puede determinar la longitud de una ruta, la cual es la suma de todos los pesos de las aristas.