Grafos

#spanish #tutorial #computerscience #español

Si acabas de encontrar esta publicación, antes de continuar te recomiendo que le des un vistazo a los demás artículos de la serie.

Los grafos son estructuras de datos no lineales, utilizadas para representar datos adyacentes. Se representa como el conjunto de vértices o nodos y de aristas o arcos. Esta estructura de datos es el principal foco de estudio de la Teoría de Grafos.

Teoría de Grafos. Rama de las matemáticas y las ciencias de la computación que estudia las propiedades de los grafos.

Un grafo G es un par ordenado G=(V,E), donde:

V es un conjunto de vértices o nodos V={v₁, v₂, ... , v_n}, y
E es un conjunto de aristas o arcos E={ {v₁, v₂}, {v₂, v₄}, ... , {v_m, v_n} }, que relacionan los nodos.

Un grafo no contempla las restricciones que existen para los árboles, es decir, no existe un máximo de nodos que pueden apuntar al mismo nodo, se los puede ver como una generalización de la estructura del tipo árbol.

Existen muchas analogías en el mundo real, la red de rutas de un país, la red de enlaces aéreos, red eléctrica, etc. En una red de rutas, los nudos o intersecciones representan los vértices del grafo y las rutas de unión los arcos, de modo que cada arco puede ser asociado a un dato específico tal como la distancia, el consumo de combustible, etc.

Los árboles son una especialización de un grafo, en el cual no existen ciclos, es decir, un árbol es un grafo conexo acíclico.

Operaciones elementales sobre Grafos

Insertar
Eliminar
Buscar
Recorrer

Definiciones sobre Grafos

Se denomina grafo nulo o vacío a aquel grafo que no tiene vértices ni arcos.
El orden del grafo G es igual al número de vértices, |V|.
Un grafo vacío es de orden cero.
El grado de un vértice se define como el número de vértices adyacentes que tiene el vértice.
En grafos dirigidos el grado de entrada de un vértice o nodo V es igual al número de arcos que lo tienen como extremo, es decir, igual al número de vértices adyacentes que tiene el vértice. Mientras que el grado de salida es el número de vértices adyacentes a un vértice dado.

Ejemplo de Grados en un Grafo Dirigido

Ejemplo de Grados en un Grafo No Dirigido

Dos o más arcos son paralelas si relacionan el mismo par de vértices.
Se dice que dos vértices son adyacentes si existe un arco entre ambos vértices. Si el arco es {K, L}, entonces, K es adyacente a L, y L es adyacente a K.
Un camino es una secuencia ordenada de vértices {v₀, v₁, v₂, ..., v_n}, también se conoce como el camino desde v₀ hasta v_n.
Un camino simple no tiene vértices repetidos excepto para el primer y último vértice.
Si en un camino simple, el primer y último vértice son iguales se conoce como un ciclo o bucle, es decir, un arco que relaciona al mismo nodo.

Ejemplo de Grafo con Bucle

Clasificación de Grafos

Los grafos pueden clasificarse acorde a sus propiedades, según su estructura, dirección y conectividad.

Sencillo y Múltiple

Un grafo G se denomina sencillo si se cumplen las siguientes condiciones:

No tiene bucles, no existe un arco tal que {v_i, v_i}.
No existe más que un arco para unir dos nodos, es decir, no existe más que un arco {v_i, v_j} para cualquier par de vértices v_i, v_j.

Un grafo que no es sencillo se denomina grafo múltiple.

Dirigido y No Dirigido

La teoría de grafos considera los siguientes tipos de grafos según su dirección:

Dirigidos, los vértices apuntan unos a otros; los arcos están dirigidos o tienen dirección, si existe un arco {v_i, v_j}, entonces se dice que existe un camino de v_i a v_j, pero esto no implica que existe un camino de v_j a v_i.

Ejemplo de Grafo Dirigido

No Dirigidos, los vértices están relacionados, pero no se apuntan unos a otros, si existe un arco {v_i, v_j}, entonces se dice que existe un camino de v_i a v_j y de v_j a v_i para cualquier par de vértices v_i, v_j.

Ejemplo de Grafo No Dirigido

Conexo y No Conexo

Finalmente, según la conectividad de los grafos, estos pueden ser:

Conexo o conectado, si existe siempre un camino que une cualquier par de vértices, todos sus vértices están conectados por un camino. Se dice que un grafo es fuertemente conexo cuando es un grafo dirigido tal que para cualquier par de nodos existe un camino que los une.

Ejemplo de Grafo Conexo

Ejemplo de Grafo Fuertemente Conexo

No Conexo o desconectado, existen vértices que no están unidos por un camino.

Ejemplo de Grafo No Conexo

Completos, Dispersos y Densos

Según el número de arcos que contiene, un grafo es completo si cuenta con todos los arcos posibles, es decir, todos los nodos están conectados con todos, es disperso si tiene relativamente pocos arcos y denso si le faltan pocos para ser completo.

Grafos Ponderados

Tanto las arcos como los vértices pueden tener asociada una etiqueta. Si la etiqueta que se asocia es un número se le llama peso, costo o longitud.
Un grafo cuyas arcos o vértices tienen pesos asociados recibe el nombre de grafo etiquetado o también conocido como grafo con pesos o ponderado.
Un grafo donde las aristas no tienen costos o pesos asociados se conoce como grafo sin pesos. También podría considerarse a un grafo sin pesos
como un grafo con pesos donde cada arista tiene un peso igual a 1.

La longitud de un camino en un grafo con pesos es la suma de los pesos de todas las aristas que componen el camino.
Por ejemplo, la siguiente figura ilustra la longitud del camino (1, 4, 7) donde (1-4) = 5,1 y (4-7) = 3,7, por lo tanto (1, 4, 7) = 8,8.