6.1.2 Tipos de grafos (Simples, completos, bipartidos, planos, conexos, ponderados)

Grafo simple

Es aquel que acepta una sola arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos.

Un grafo simple G es una estructura maten ática que consta de un par

Ordenado de conjuntos (V, E), siendo V 6= ∅. Los elementos de V se llaman

Vértices y los elementos de E se llaman aristas. Notemos que en un grafo

Simple, una arista es un par {x, y} no ordenado de vértices diferentes.

Un ejemplo de un grafo G = (V, E) viene dado por los conjuntos

V = {1, 2, 3, 4}

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

Llamaremos orden al cardinal del conjunto de vértices V y tamaño al

Cardinal del conjunto de aristas E. Por lo tanto, G es un grafo de orden 4 y

tamaño 5. Son aquellos grafos que no tienen lazos ni aristas paralelas.

Grafo completo

Un grafo simple es completo si existen aristas uniendo todos los pares

posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que

los une.

El conjunto de los grafos completos es denominado usualmente K, siendo

el grafo completo de n vértices.

Un Kn, es decir, grafo completo de n vértices tiene exactamente n(n-1)/2

aristas.

La representación gráfica de los Kn como los vértices de un polígono regular

da cuenta de su peculiar estructura.

Grafo bipartido

Un grafo G es bipartito si puede expresarse como G = {V1 + V2, A} (es decir,la unión de dos grupos de vértices), bajo las siguientes condiciones:

• V1 y V2 son distintos y tienen más de un elemento cada uno.

• Una arista en A une un vértice de V1 con uno de V2.

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

Grafo plano

Un grafo G es plano si admite una representación en el plano de tal forma que las aristas no se cortan, salvo en sus extremos. A dicha representación se le denomina grafo plano. En teoría de grafos, un grafo plano (o planar según referencias) es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce (una definición más formal puede ser que este grafo pueda ser "incrustado" en un plano).

Grafos conexos

Un grafo es conexo (más formalmente fuertemente conexo) si todos sus vértices están conectados por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b. Es posible determinar si un grafo es fuertemente conexo coleccionando la información de los grados de sus vértices al tiempo que se acumulan las diferentes rutas que salen de un vértice o llegan a él. En términos matemáticos la propiedad de un grafo de ser fuertemente conexo permite establecer en base a él una relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en "componentes fuertemente conexos", es decir, porciones del grafo, que son fuertemente conexas cuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones en teoría de grafos.

Grafos ponderados

Un grafo G es un grafo etiquetado si sus aristas y/o vértices tienen asignado alguna identificación. En particular, G es un grafo ponderado si a cada arista e de G se le asigna un número no negativow(e) denominado peso o longitud de e. El peso (o longitud de un camino en un grafo ponderado G se define como la suma de los pesos de las aristas del camino. Un importante problema en teoría de grafos es encontrar el camino más corto (liviano), esto es, el camino con el peso (longitud) mínimo entre dos vértices dados.

Vídeo explicativo:https://www.youtube.com/watch?v=2cOThq8KiqA