El lunes pasado fue feriado y por eso no me pareció muy buena idea hinchar con la siguiente parte esta inroducción, pero hoy ya estamos con una semana completa de cosas para hacer y aunque parezca ridículo leer un poco de algo como la teoría de grafos, nos libera la cabeza de las preocupaciones diarias.
Ves todo más sencillo…
En serio …
Un grafo (o multigrafo), es una estructura muy importante utilizada en Informática y también en ciertos ramos de Matemáticas, como por ejemplo, en Investigación de Operaciones. Muchos problemas de difícil resolución, pueden ser expresados en forma de grafo y consecuentemente resuelto usando algoritmos de búsqueda y manipulación estándar.
- Entre las múltiples aplicaciones que tienen estas estructuras podemos mencionar:
- Modelar diversas situaciones reales, tales como: sistemas de aeropuertos, flujo de tráfico, etc.
Realizar planificaciones de actividades, tareas del computador, planificar operaciones en lenguaje de máquinas para minimizar tiempo de ejecución.
Simplemente, un grafo es una estructura de datos no lineal, que puede ser considerado como un conjunto de vértices (o nodos, dependiendo de la bibliografía) y arcos que conectan esos vértices. Matemáticamente tenemos G=(V, E). Si u y v son elementos de V, entonces un arco se puede representar por (u,v).
Los grafos también se pueden clasificar como:
- Grafo No Dirigido
- Grafo Dirigido (o Digrafo)
En el primer caso, los arcos no tienen una dirección y, por lo tanto, (u,v) y (v,u) representan el mismo arco. En un Grafo No Dirigido, dos vértices se dicen adyacentes si existe un arco que une a esos dos vértices. En el segundo caso, los arcos tienen una dirección definida, y así (u,v) y (v,u) entonces representan arcos diferentes. Un Grafo Dirigido (o digrafo) puede también ser fuertemente conectado si existe un camino desde cualquier vértice hacia otro cualquier vértice.
Ejemplos de grafos (dirigidos y no dirigidos):
- G1 = (V1, E1)
V1 = {1, 2, 3, 4} E1 = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)} - G2 = (V2, E2)
V2 = {1, 2, 3, 4, 5, 6} E2 = {(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)} - G3 = (V3, E3)
V3 = {1, 2, 3} E3 = {<1, 2>, <2, 1>, <2, 3>}
Gráficamente estas tres estructuras de vértices y arcos se pueden representar de la siguiente manera:
| Definiciones Básicas |
Un grafo puede ser direccional o no direccional.
Un grafo direccional G es un par (V, E):
- V es un conjunto finito de vértices y
- E es un conjunto de aristas que representa una relación binaria sobre V → E ⊆V x V.
En un grafo no direccional G = (V, E), el conjunto de aristas E consiste en pares no ordenados de vértices.
Una arista es un conjunto {u, v}, en que u, v ∈ V y u ≠ v, y que representamos como (u, v).
Si (u, v) es una arista en un grafo:
- dirigido, entonces (u, v) es incidente desde o sale del vértice u y es incidente a o entra al vértice v;
- no dirigido, entonces (u, v) es incidente sobre u y v.
v es adyacente a u; si el grafo es no dirigido, entonces la relación de adyacencia es simétrica.
Un camino (o ruta) es una secuencia de vértices v1,…,vn tal que (vi,vi+1 ) pertenece a E. La longitud de un camino es la cantidad de arcos que éste contiene.
Un camino de longitud k desde un vértice u a un vértice u’ en un grafo G = (V, E) es una secuencia v0, v1, …, vk de vértices tal que:
- u = v0,
- u’ = vk y
- (vi-1, vi) Î E para i = 1, 2, …, k.
Si hay un camino p desde u a u’, entonces u’ es alcanzable desde u vía p.
Un camino simple es aquel donde todos sus vértices son distintos. Sólo el primero y el último pueden coincidir. Un ciclo en un grafo dirigido es el camino de longitud mayor o igual que 1 donde w1 = wn. Se llamará ciclo simple si el camino es simple.
Si a={u,v} es una arista de G escribiremos sólo a=uv, y diremos que a une los vértices u y v o que u y v son extremos de a. Una arista a=uu se llama bucle. Una arista que aparece repetida en E se llama arista múltiple.
Un ciclo es un camino simple y cerrado.
Un grafo es conexo si desde cualquier vértice existe un camino hasta cualquier otro vértice del grafo.
Un grafo es conexo si para cada par de vértices u y v existe un camino de u a v. Si G es un grafo no conexo (o disconexo), cada uno de sus subgrafos conexos maximales se llama componente conexa de G.
Un digrafo D=(V,E) es fuertemente conexo si para todo par de vértices u y v existe un camino dirigido que va de u a v.
Dado un digrafo D, podemos considerar el grafo G no dirigido que se obtiene al sustituir cada arco (u,v) por la arista (u,v). Si este grafo es conexo, diremos que el digrafo D es débilmente conexo. Se dice que un grafo no dirigido es un árbol si es conexo y acíclico.
En algunos textos llaman grafo al que aquí se denomina grafo simple, permitiendo la presencia de aristas múltiples en los multigrafos y de bucles en los seudografos.
Dos vértices son adyacentes si son extremos de una misma arista. Dos aristas son adyacentes si tienen un extremo común. Un vértice y una arista son incidentes si el vértice es extremo de la arista. Un vértice es aislado si no tiene otros vértices adyacentes.
Un grafo completo es un grafo simple en el que todo par de vértices está unido por una arista. Se representa con Kn al grafo completo de n vértices.
Un grafo G=(V,E) se llama bipartito (o bipartido) si existe una partición de V, V=X U Y, tal que cada arista de G une un vértice de X con otro de Y. (Se designa por Kr,s al grafo bipartito completo en que |X|= r e |Y|= s, y hay una arista que conecta cada vértice de X con cada vértice de Y).
El número de vértices de un grafo G es su orden y el número de aristas su tamaño. Designaremos el orden con n y el tamaño con q y utilizaremos la notación de grafo (n,q).
Dos grafos G=(V,E) y G’=(V’,E’) son isomorfos si existe una biyección f:V → V’ que conserva la adyacencia. Es decir, ∀ u,v ∈ V, u y v son adyacentes en G ⇔ f(u) y f(v) son adyacentes en G’.
Un subgrafo de G=(V,E) es otro grafo H=(V’,E’) tal que V’ ⊆ V y E’⊆ E. Si V’ = V se dice que H es un subgrafo generador.
Se llama grado de un vértice v al número de aristas que lo tienen como extremo, (cada bucle se cuenta, por tanto, dos veces). Se designa por d(v).
Un grafo regular es un grafo simple cuyos vértices tienen todos los mismos grados.
A la sucesión de los grados de los vértices de G se le denomina sucesión de grados del grafo G. Una sucesión de enteros no negativos se dice sucesión gráfica si es la sucesión de grados de un grafo simple.
| Representaciones de Grafos |
Existen dos formas de mantener un grafo G en la memoria de una computadora, una se llama Representación secuencial de G, la cual se basa en la matriz de adyacencia.
La otra forma, es la llamada Representación enlazada de G y se basa en listas enlazadas de vecinos. Independientemente de la forma en que se mantenga un grafo G en la memoria de una computadora, el grafo G normalmente se introduce en la computadora por su definición formal: Un conjunto de nodos y un conjunto de aristas.
Matriz y Lista de Adyacencia
Dado un grafo G = (V, E), podemos representar un grafo a través de una matriz de dimensión V x V, donde el contenido podrá ser de números binarios (0;1) o de número enteros (-1;0;1).
Para ejemplificar, analicemos el grafo G:
La cardinalidad de vértices del grafo G es 6, por tanto, para su representación, deberemos tener una matriz de adyacencias 6×6. Utilizando valores binarios, podemos representarla de esta forma:
Conforme observamos, la matriz de adyacencias está formada siguiendo la siguiente regla: ma[i,j] = 1, si i es adyacente a j, y 0 en caso contrario. Como estamos trabajando con un dígrafo, debemos establecer cual es el origen y cual es el destino. En el ejemplo presentado, el origen está definido por la letra indicadora de línea. Por ejemplo, A está conectado con B, más no en sentido contrario, por eso ma[A,B] es 1 y ma[B,A] es 0.
Para resolver esto, podemos hacer una representación alternativa: ma[i,j] = -1 si i es origen de adyacencia con j, 1 si i es el destino de adyacencia con j, y es 0 para los demás vértices no envueltos en la adyacencia . Esto es sintetizado en la siguiente matriz:
Como ejemplo, observemos el elemento ma[A,B] , ma[A,C] e ma[A,D] que poseen valor -1. Esto indica que A es origem de arcos para C , D y E. También observemos ma[F,D] y ma[F,E] , con valor 1, indicando que F recibe los arcos de D y E.
A pesar de la metodología empleada, se observa que para una aplicación dada que necesite de alteración del grafo, sería inadecuada la representación a través de estructuras fijas, exigiendo, entonces, estructuras dinámicas.
Lista de Adyacencias
Para que sea pos ible remodelar un grafo en tiempo de ejecución, se torna necesaria la utilización dinámica de su representación. Por eso, la representación de adyacencias entre vértices puede ser hecha a través de listas lineales.
Su construcción es realizada por un vector dinámico con listas encadenadas formando un índice de vértices. De cada elemento de índice parte una lista encadenada describiendo los vértices adyacentes conectados.
Como ejemplo, para el grafo G presentado anteriormente, visualizaremos la siguiente representación:
La lista encadenada es formada por nodos que contienen el dato del vértice (letra) y el puntero para el vértice adyacente a loindicado en el índice (vector descriptor de vértices). Eventualmente los nodos pueden exigir otros campos, tales como marcas de visita al vértice, datos adicionales para procesamiento de la secuencia del grafo, etc.
Esta es la forma de representación más flexible para la representación de grafos. Obviamente que aplicaciones específicas permitirán el uso de otras formas de representación. Cabe aquí destacar que es posible la descripción de grafos a través de sus aristas, lo que puede demandar una matriz para su descripción.
La suma de las longitudes de todas las listas es |E|, si G es direccional, y 2|E| si G es no direccional — la cantidad de memoria necesaria es siempre O(max(V, E)) = O(V + E).
La matriz de adyacencias de G = (V, E) supone que los vértices están numerados 1, 2, …, |V| arbitrariamente, y consiste en una matriz A = (aij) de |V|´|V|, tal que:
Esta representación requiere Θ(V2) memoria, independientemente del número de aristas en G.
La matriz de adyacencia siempre es simétrica porque aij = aji . La lista de Adyacencia es una lista compuesta por vértices y una sublista conteniendo las aristas que salen de él.
En el caso de las listas de adyacencia el espacio ocupado es O(V + E), muy distinto del necesario en la matriz de adyacencia, que es de O(V2). La representación por listas de adyacencia, por tanto, será más adecuada para grafos dispersos.
Matriz y Lista de Incidencia
Este tipo de matriz representa un grafo a partir de sus aristas. Como exige muchas veces la utilización de una matriz mayor dado que el método de la matriz de adyacencias, no esta tan utilizada en cuanto a aquella. La matriz alojada deberá tener dimensiones V x E.
El principio de esta representación está en la regla: mi[i,j] = 1 si el vértice i incide con la arista j, y 0 en caso contrario . Ejemplificando a partir del grafo G anteriormente presentado, tendremos una matriz:
Recorridos de Grafos
En muchas aplicaciones es necesario visitar todos los vértices del grafo a partir de un nodo dado. Algunas aplicaciones son:
- Encontrar ciclos
- Encontrar componentes conexas
- Encontrar árboles cobertores
Hay dos enfoques básicos:
- Recorrido (o búsqueda) en amplitud (breadth-first search): Se visita a todos los vecinos directos del nodo inicial, luego a los
vecinos de los vecinos, etc. - Recorrido (o búsqueda) en profundidad (depth-first search): La idea es alejarse lo más posible del nodo inicial (sin repetir nodos),
luego devolverse un paso e intentar lo mismo por otro camino.
Recorridos en Amplitud
La Búsqueda en Amplitud (BFS) es uno de los algoritmos más simples para recorrer un grafo y es el modelo de muchos algoritmos sobre grafos.
Dado un grafo G = (V, E) y un vértice de partida s, BFS explora sistemáticamente las aristas de G para descubrir todos los vértices
alcanzables desde s:
- Calcula la distancia — mínimo número de aristas — de s a cada vértice alcanzable.
- Produce un árbol con raíz s que contiene todos los vértices alcanzables.
- Para cualquier vértice v alcanzable desde s, la ruta de s a v en el árbol contiene el mínimo número de aristas — es una ruta más
corta. - Funciona en grafos direccionales y no direccionales.
BFS expande la frontera entre vértices descubiertos y no descubiertos uniformemente en toda la amplitud de la frontera.
Descubre todos los vértices a distancia k antes de descubrir cualquier vértice a distancia k + 1.
BFS pinta cada vértice BLANCO, PLOMOo NEGRO, según su estado:
- Todos los vértices empiezan BLANCOs.
- Un vértice es descubierto la primera vez que es encontrado, y se pinta PLOMO.
- Cuando se ha descubierto todos los vértices adyacentes a un vértice PLOMO, éste se pinta NEGRO.
- Los vértices PLOMOs pueden tener vértices adyacentes BLANCOs — representan la frontera entre vértices descubiertos y no descubiertos.
BFS construye un árbol de amplitud:
Inicialmente, el árbol sólo contiene su raíz — el vértice s.
Cuando se descubre un vértice BLANCO v mientras se explora la lista de adyacencias de un vértice u, v y la arista (u, v) se agregan al árbol, y u se convierte en el predecesor o padre de v en el árbol.
En la siguiente versión de BFS:
El grafo se representa mediante listas de adyacencias.
Para cada vértice u, se almacena: el color en color[u], el predecesor en π[u], y la distancia desde s en d[u].
El conjunto de vértices PLOMOs se maneja en la cola Q.
El árbol de amplitud o grafo predecesor de G se define como
Las aristas en E π se llaman aristas de árbol.
El tiempo total de ejecución de BFS es O(V + E).
| Recorridos en Profundidad |
A medida que recorremos el grafo, iremos numerando correlativamente los nodos encontrados (1,2,…). Suponemos que todos estos números son cero inicialmente, y utilizamos un contador global n, también inicializado en cero.
- La Búsqueda en Profundidad (DFS) busca más adentro en el grafo mientras sea posible:
- Las aristas se exploran a partir del vértice v más recientemente descubierto.
- Cuando todas las aristas de v han sido exploradas, la búsqueda retrocede para explorar aristas que salen del vértice a partir del cual se descubrió v.
- Continuamos hasta que se ha descubierto todos los vértices alcanzables desde el vértice de partida.
- Si quedan vértices no descubiertos, se elige uno como nuevo vértice de partida y se repite la búsqueda.
DFS construye un subgrafo predecesor:
- Cuando descubre un vértice v durante la exploración de la lista de adyacencias de un vértice u, asigna u al predecesor p [v] de v.
- Este subgrafo o bosque de profundidad puede constar de varios árboles de profundidad , porque la búsqueda puede repetirse desde varios vértices de partida.
El subgrafo predecesor se define como como G π = (V, E π):
E π = {( π [v], v) : v ∈ V ∧ π[v] ≠ NIL}
las aristas en E π se llaman aristas de árbol.
DFS pinta cada vértice BLANCO, PLOMO o NEGRO:
- Todos los vértices empiezan BLANCOs.
- Cuando un vértice es descubierto, se pinta PLOMO.
- Cuando un vértice es terminado — se ha examinado toda la lista de adyacencias del vértice — se pinta NEGRO.
- Se garantiza que cada vértice forma parte de sólo un árbol de profundidad — éstos son disjuntos.
En la siguiente versión recursiva de DFS:
- G puede ser direccional o no direccional.
- A cada vértice u, se le asocia los tiempos
- d[u] al descubrirlo — cuando u se pinta PLOMO — y
- f[u] al terminar la exploración de a[u] — cuando u se pinta NEGRO.
El tiempo total de ejecución de DFS es Θ(V + E)
| Grafos con Peso |
Un grafo con peso (o grafo con costo) es un grafo G más una función de peso o costo:
f: E(G) → R
En general, salvo mención expresa en contrario, consideramos sólo grafos con pesos no negativos en las aristas.
Definición: Sea G un grafo con peso, y sea H un subgrafo de G. El costo total o peso total de H es:
w(H) = Σ w(e) e ∈ H
Creí que no entarba todo en una entrada pero fuí un poco necio … Lunes que viene segunda y última parte de grafos.
