Que son los Grafos en gestión de datos
Conceptos y Definiciones
Un grafo es una pareja G = (V, A), donde V es un conjunto de puntos, llamados vértices, y A es un conjunto de pares de vértices, llamadas aristas. Para simplificar, notaremos la arista {a, b} como ab.
Los grafos son colecciones de objetos llamados vértices o nodos, conectados por líneas denominadas aristas o arcos. Un grafo es utilizado, en la matemática y en las ciencias de la computación, para representar relaciones entre diferentes elementos. Esas relaciones pueden mantener o no jerarquía. En caso que se presente la necesidad de soportar una relación jerárquica, el grafo debe incluir en sus arcos un sentido de dirección de la relación.
En la concepción matemática, la importancia de un grafo radica en establecer relaciones entre los vértices y las aristas. En las ciencias de la computación es muy relevante la figura de los vértices, es por ello que la terminología utilizada para denotar los vértices es nodos, esto es porque se los considera como un conjunto de datos que pueden ser de distinto tipo.
Se considera la característica de "grado" (positivo o negativo) de un vértice v y se indica como (v), a la cantidad de aristas que llegan o salen de él; para el caso de grafos no orientados, el grado de un vértice es simplemente la cantidad de aristas que tocan este vértice.
Caminos, pasos y ciclos
Un camino entre dos nodos a y b, se produce cuando existe una vinculación directa o indirecta entre ambos, esto es cuando puedo vincular mediante uno o mas arcos a dichos nodos entre sí. Dado que en este concepto no está vinculado con la dirección de los arcos, puede existir camino tanto en grafos dirigidos como en grafos no dirigidos.
Un paso entre dos nodos a y b, se produce cuando existe un camino entre ambos, pero con un sentido preestablecido, esto es que partiendo del nodo a y siguiendo el sentido de los arcos se llega al nodo b. Como en este caso es relevante el sentido, solo se evalúan pasos en los grafos dirigidos.
Un ciclo es un camino, es decir una sucesión de aristas adyacentes, donde no se recorre dos veces la misma arista, y donde se regresa al punto inicial. Un ciclo hamiltoniano tiene además que recorrer todos los vértices exactamente una vez (excepto el vértice del que parte y al cual llega). Se habla también de camino hamiltoniano si no se impone regresar al punto de partida.
Hoy en día, no se conocen métodos generales para hallar un ciclo hamiltoniano en tiempo polinómico, siendo la búsqueda por fuerza bruta de todos los posibles caminos u otros métodos excesivamente costosos. Existen, sin embargo, métodos para descartar la existencia de ciclos o caminos hamiltonianos en grafos pequeños.
La longitud de paso es la cantidad de arcos involucrados.
Grafos Simples
Un grafo es simple si a lo sumo sólo 1 arista une 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 que no es simple se denomina complejo.
Grafos Conexos
Un grafo es conexo si cada par de vértices está conectado por un camino. Un grafo es fuertemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos. Es posible determinar si un grafo es conexo usando un algoritmo Búsqueda en anchura (BFS) o Búsqueda en profundidad (DFS).
Grafos Completos
Un grafo simple es completo si existen aristas uniendo todos los pares posibles de vértices.
Un Kn, es decir, grafo completo de n vértices tiene exactamente aristas.
Grafos Bipartitos
Un grafo G es bipartito si puede expresarse como G = {V1 U V2, A} (es decir, la unión de dos grupos de vértices), bajo las siguientes condiciones:
- V1 y V2 son disjuntos y no vacíos.
- Cada arista de A une un vértice de V1 con uno de V2.
- No existen aristas uniendo dos elementos de V1; análogamente para V2
Grafos ponderados
En muchos casos, es preciso atribuir a cada arista un número específico, llamado valuación, ponderación o coste según el contexto, y se obtiene así un grafo valuado. Formalmente, es un grafo con una función v: A → R+.
Clasificación de Grafos
Segun la presencia de direccion:
- Grafos Dirigidos: son aquellos en los cuales los arcos que vinculan a los vértices tienen una dirección definida, la cual marca una jerarquía en la relación modelizada.
- Grafos No dirigidos: son aquellos donde los arcos no tienen una dirección definida que marque propiedad en la relación modelizada.
Segun las restricciones de sus relaciones:
- Grafos Restrictos: son aquellos en los cuales la relación modelizada no debe cumplir las propiedades de reflexivididad, simetría y transitividad.
- Grafos Irrestrictos: son aquellos que pueden modelizar cualquier relación independientemente de las propiedades que cumpla o no.
Representación Computacional de Grafos
Dinamica
Una representación es dinámica, cuando el espacio consumido para representar computacionalmente al grafo, concuerda exactamente con la cantidad de nodos y vértices a representar, esto es que no se consideran todas las posibilidades de relación posibles, sino que solo se representa lo que ocurre en este momento.
Lista de adyacencias:
se asocia a cada nodo del grafo una lista que contenga todos aquellos nodos que sean adyacentes a él.
En este caso el espacio ocupado es O(V + A), muy distinto del necesario en la matriz de adyacencia, que era de O(V2). La representación por listas de adyacencia, por tanto, será más adecuada para grafos dispersos. Hay que tener en cuenta un aspecto importante y es que la implementación con listas enlazadas determina fuertemente el tratamiento del grafo posterior. Los nodos se van añadiendo a las listas según se leen las aristas, por lo que nos encontramos que un mismo grafo con un orden distinto de las aristas en la entrada producirá listas de adyacencia diferentes y por ello el orden en que los nodos se procesen variará. Una consecuencia de esto es que si un problema tiene varias soluciones la primera que se encuentre dependerá de la entrada dada. Estructura de Graal
Es igual que las listas de adyacencia nada mas que en vez de guardar el nodo en la lista, se guarda un puntero al nodo.
Representación de Pfaltz Las estructuras de datos que utiliza Pfaltz son básicamente dos listas, una de nodos, y otra de arcos.
Pfaltz trabaja con una representación dinámica de nodos y arcos enlazados mediante punteros, ocupando espacio en memoria a medida que realmente se necesita (cuando se crea un nuevo nodo o un nuevo arco), y liberándolo cuando se efectúa una baja.
Para un problema medianamente complejo donde se pueden llegar a tener cientos de nodos, la representación de Pfaltz es más eficiente que el uso de matrices. Una matriz sería extremadamente grande teniendo en cuenta que siempre se reserva espacio para las relaciones, independientemente de la cantidad de arcos realmente existentes.
Estaticas
Una representación computacional se denomina estática, cuando el espacio consumido para representar computacionalmente al grafo es invariable y fijo respecto a la cantidad de nodos y vértices a representar, esto es que son consideradas todas las ocurrencias de relaciones que puedan producirse entre todos los nodos, reservando el espacio para dicha ocurrencia potencial.
De esta forma la representación se mantiene fija y estática en el tiempo independientemente de las altas y bajas de arcos o vértices que se produzcan en el grafo representado computacionalmente.
Matriz de adyacencias:
se asocia cada fila y cada columna a cada nodo del grafo, siendo los elementos de la matriz la relación entre los mismos, tomando como valores la cantidad de aristas que los unen y 0 en caso contrario.
La matriz de adyacencia de un grafo no dirigido es simétrica. En cambio la matriz de adyacencia de un dígrafo no es simétrica. Es una matriz binaria. El número de unos que aparecen en una fila es igual al grado de salida del correspondiente vértice y el número de unos que aparecen en una determinada columna es igual al grado de entrada del correspondiente vértice.
Matriz de incidencias:
se asocia cada fila con un nodo y cada columna con una arista del grafo, siendo los elementos de la matriz la relación un 1 si dicho nodo es incidente con dicha arista y un 0 en caso contrario.
La matriz de incidencia sólo contiene ceros y unos (matriz binaria). Como cada arista incide exactamente en dos vértices, cada columna tiene exactamente dos unos. El número de unos que aparece en cada fila es igual al grado del vértice correspondiente. Una fila compuesta sólo por ceros corresponde a un vértice aislado.
Algoritmos de busqueda en grafos (problema del caballo)
Búsqueda en anchura.
Es un algoritmo para recorrer o buscar elementos en un grafo (usado frecuentemente sobre árboles). Intuitivamente, se comienza en la raíz (eligiendo algún nodo como elemento raíz en el caso de un grafo) y se exploran todos los vecinos de este nodo. A continuación para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el árbol.
Formalmente, BFS es un algoritmo de búsqueda sin información, que expande y examina todos los nodos de un árbol sistemáticamente para buscar una solución. El algoritmo no usa ninguna estrategia heurística.
Procedimiento
- Dado un vértice fuente s, Breadth-first search sistemáticamente explora los vértices de G para “descubrir” todos los vértices alcanzables desde s.
- Calcula la distancia (menor número de vértices) desde s a todos los vértices alcanzables.
- Después produce un árbol BF con raíz en s y que contiene a todos los vértices alcanzables.
- El camino desde s a cada vértice en este recorrido contiene el mínimo número de vértices. Es el camino más corto medido en número de vértices.
- Su nombre se debe a que expande uniformemente la frontera entre lo descubierto y lo no descubierto. Llega a los nodos de distancia k, sólo tras haber llegado a todos los nodos a distancia k-1.
El tiempo de ejecución es O(|V|+|E|). Nótese que cada nodo es puesto a la cola una vez y su lista de adyacencia es recorrida una vez también.
Búsqueda en profundidad
Es un algoritmo que permite recorrer todos los nodos de un grafo o árbol de manera ordenada, pero no uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan más nodos que visitar en dicho camino, regresa (Backtracking), de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado.
El tiempo de ejecución es O(|V|+|E|)