Tipos de Grafos

Tipos de Grafos

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 a 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. (ej-7.1)

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.(ej-7.2)

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.

En la gráfica de la figura 8.2.1,

es una trayectoria de longitud 4 del vértice 1 al vértice 2.

Una gráfica conexa es una gráfica en la que se puede ir de cualquier vértice a cualquier otro vértice por una trayectoria. A continuación se da la definición formal.

Una gráfica G es conexa si dados cualesquiera dos vértices v y w en G, existe una trayectoria de v a w.

La gráfica G de la figura 8.2.1 es conexa ya que, dados cualesquiera dos vértices v y w en G, existe una trayectoria de v a w.

La gráfica G de la figura 8.2.2 no es conexa ya que, por ejemplo, no hay trayectoria del vértice v2 al vértice v5.