Un grafo es una composición de un conjunto de objetos conocidos como nodos que se relacionan con otros nodos a través de un conjunto de conexiones conocidas como aristas.
Grafos
En primera instancia debemos entender que es un grafo. Un grafo es una composición de un conjunto de objetos conocidos como nodos que se relacionan con otros nodos a través de un conjunto de conexiones conocidas como aristas. Los grafos permiten estudiar las relaciones que existen entre unidades que interactúan con otras.
Un grafo G = (V, A) es un par formado por un conjunto de vértices o nodos, V, y un conjunto de arcos o aristas, A. Cada arco es el par (u, w), siendo u, w dos vértices relacionados. Existen dos tipos de grafos, los grafos dirigidos y los grafos no dirigidos:
Grafo dirigido
Un Grafo Dirigido G consiste en un conjunto V de vértices y un conjunto E al conjunto de aristas del grafo.
V = {a, b, c, e}
E = {(a, c), (a, b), (a, e), (b, e), (c, e)}
Un enlace o arista es un par ordenado de vértices (v, w), donde v es la cola y w corresponde a la cabeza del enlace. Los vértices de un grafo dirigido pueden usarse para representar objetos y los enlaces, relaciones entre los objetos, ejemplo de ello que los vértices pueden representar ciudades y los enlaces vuelos entre ciudades.
Grafo no dirigido
Sea G un grafo no dirigido, donde G = (V, E) y V corresponde al conjunto de vértices y E al conjunto de aristas del grafo. Se diferencia de un Grafo dirigido debido a que cada arista en E es un par no ordenado de vértices. Si (v, w) es una arista no dirigida -> (v, w) = (w, v).
V = {a, b, c, e}
E = {(a, c), (c, a), (a, b), (b, a), (a, e), (e, a), (c, e), (e, c), (b, e), (e, b)}
Grado de un grafo
El grado de un grafo es la suma de los grados de todos sus vértices. El grado de un vértice de un Digrafo o Grafo Dirigido se divide en grado de entrada o grado de salida. El grado de entrada de un vértice es el número de arcos entrantes del vértice, y el grado de salida de un vértice es el número de arcos salientes del mismo. Por otro lado, el grado de un vértice de un Grafo No Dirigido es la suma de las aristas de dicho vértice.
Camino
Si el grafo es pesado, la longitud del camino es la suma de los pesos de las aristas que conectan los vértices. Sin embargo, si el grafo no es pesado, lo longitud del caminos es la suma de las aristas que conectan a dichos vértices.
Matriz de adyacencia
La forma más sencilla de representación es mediante una matriz, de tantas filas / columnas como nodos, que permite modelar fácilmente. En los grafos no dirigidos la matriz de adyacencia siempre es simétrica.
Si el grafo es un grafo no pesado, es una matriz de 1’s y 0´s, que indican con un 1 si dos vértices son adyacentes, de lo contrario mostrara un 0. En un grafo valorado, cada elemento representa el peso de la arista y no solo 1’s y 0’s, por ello se le denomina matriz de pesos.
Listas de Adyacencia
Las listas de adyacencia son una estructura multi enlazada formada por una tabla directorio en la que cada elemento representa un vértice del grafo, del cuál emerge una lista enlazada con todos sus vértices adyacentes. Es decir, cada lista representa los arcos con el vértice origen del nodo de la lista directorio, por eso se llama lista de adyacencia.
Grafo Conexo
Si existe un camino entre cualquier par de vértices y el grafo es no dirigido, entonces el grafo es No Dirigido Conexo, pero, si el grafo es dirigido, entonces el grafo es Dirigido Fuertemente Conexo.
Componentes Conexas
Subconjuntos de vértices que mutuamente están conectados; es decir, las componentes conexas del mismo.
- Realizar un recorrido del grafo a partir de cualquier vértice w.
- Si en el recorrido se han marcado todos los vértices, entonces el grafo es conexo
- Si el grafo no es conexo, los vértices marcados forman una componente conexa
- Se toma un vértices no marcado, z, y se realiza de nuevo el recorrido del grafo a partir de z. Los nuevos vértices marcados forman una componente conexa.
- El algoritmo termina cuando todos los vértices han sido marcados (visitados).
Componentes Fuertemente Conexas
De no ser fuertemente conexo se pueden determinar componentes fuertemente conexas del grafo.
- Obtener el conjunto de vértices descendientes del vértices de partida. Recorrido en profundidad.
- Obtener el conjunto de ascendientes.
- Los vértices comunes del conjunto de descendientes y ascendientes es el conjunto de vértices que forman la componente fuertemente conexa a la que pertenece v. Si este conjunto es el conjunto de todos los vértices del grafo, entonces es fuertemente conexo.
- Si no es un grafo fuertemente conexo se selecciona un vértice cualquiera y se procede de la misma manera, es decir, se repite a partir del primer paso hasta obtener todas las componentes fuertes del grafo.
Aplicaciones
Los grafos se clasifican en dirigidos y no dirigidos y son modelos naturales de relaciones. Así, los grafos se usan para representar redes de alcantarillado, redes de comunicaciones, circuitos eléctricos, etc. Una vez modelados el problema mediante un grafo se pueden hacer estudios sobre diversas propiedades. Para ello se utilizan algoritmos concretos que resuelvan ciertos problemas. La teoría de grafos ha sido aplicada en el estudio de problemas que surgen en áreas diversas de las ciencias, como la química, la ingeniería eléctrica o la investigación operativa.