grafos
DESCRIPTION
Estructura de datosTRANSCRIPT
Introducción a la Teoría de Grafos
Un poco de historia...La Teoría de Grafos tiene su origen en un acertijo popular sobre la posibilidad de dar un paseo pasando una sola vez por los siete puentes existentes en la ciudad de Königsberg, empezando en cualquier punto de misma y volviendo al punto de partida.Nadie fue capaz de dar una respuesta apropiada hasta que Euler, en 1736, ofreció una demostración matemática de la imposibilidad de llevar a cabo tal paseo.
Un poco de historia...
Mapa de la ciudad de Köninsberg
Un poco de historia...
Para estudiar un problema es mejor quitar lo accesorio que entorpece la compresión del mismo (figura 1) o, mejor aún, encontrar un modelo que abstraiga la información necesaria para su resolución. Es lo que hizo Euler (figura 2) y a la estructura formada por nodos y arcos se la denominó grafo.
Definiciones Un grafo es una
estructura G = <V,A> donde V es un conjunto finito de nodos y A VxV es un conjunto finito de arcos (pares no ordenados).
Un grafo dirigido es un grafo G = <V,A> en el que A es un conjunto finito de arcos orientados (pares ordenados).
Se denomina orden del grafo al número de nodos del mismo.
Definiciones Se denomina lazo a un
arco que conecta a un vértice consigo mismo.
Un grafo se denomina simple si
No tiene lazos Sólo existe un arco que
une dos vértices. Un grafo que no es
simple, se denomina múltiple.
Definiciones Un camino en un grafo es una secuencia
de nodos u1, u2 ,..., un, tal que (u1 ,u2 ),(u2 ,u3 ),... (un-1 ,un ) son arcos.
La longitud de un camino es el número de arcos que comprende.
Un ciclo simple es un camino de longitud por lo menos uno, que empieza y termina en el mismo nodo.
Un grafo es cíclico si contiene por lo menos un ciclo.
Definiciones Un grafo (no dirigido) se
llama conexo si para todo par de nodos existe un camino que los une.
Dado un grafo no dirigido G(V,A), un subgrafo de G es un grafo G’(V’,A’) tal que V'V y A'A.
Si A' consta de todos los arcos de A, que unen nodos de V', entonces G' es un subgrafo inducido de G.
Definiciones Un grafo no dirigido
conexo y acíclico se denomina árbol.
Todo árbol de orden n tiene n-1 arcos.
Si se agrega un arco cualquiera a un árbol, se origina un ciclo.
Definiciones Un grafo dirigido
etiquetado es aquél en el que arcos o nodos, llevan una etiqueta asociada.
Una etiqueta puede ser un nombre, un valor, un coste o cualquier tipo de dato.
Los grafos dirigidos etiquetados también se denominan ponderados o con peso
Definiciones La suma de los grados de
los vértices es igual al doble del número de aristas
La relación entre vértices dada por v está relacionado con w si hay un camino que los une es de equivalencia.
Las clases de equivalencia de esta relación se llaman las componentes conexas del grafo.
Definiciones Una arista de un grafo G
se dice de separación si G es conexo pero al suprimir la arista se divide en dos componentes conexos
Definiciones La suma de los grados de
los vértices es igual al doble del número de aristas
La relación entre vértices dada por v está relacionado con w si hay un camino que los une es de equivalencia.
Las clases de equivalencia de esta relación se llaman las componentes conexas del grafo.
Definiciones Un Circuito euleriano , es
un ciclo simple que recorre todos los arcos una sola vez, empezando y terminando en el mismo nodo.
Si un grafo está formado por dos subgrafos eulerianos unidos al menos por un vértice y sin aristas en común, entonces es euleriano
Definiciones Un grafo conexo
G=(V,A) es euleriano todo vértice tiene grado par.
Un grafo conexo tiene un camino abierto euleriano tiene exactamente dos vértices de grado impar.
Algoritmo de FLEURY Si G es un grafo euleriano siempre es posible
seguir la siguiente construcción de un circuito euleriano. Se empieza por un vértice arbitrario y se recorren las aristas arbitrariamente sometida a dos condiciones:
Se borran las aristas a medida que son atravesadas
Solo se recorre una arista de separación si no queda otra alternativa
Definiciones Un Circuito
hamiltoniano es un ciclo simple que recorre todos los nodos una sola vez, empezando y terminando en el mismo nodo.
A diferencia de los grafos eulerianos, no hay una caracterización de cuando un grafo tiene un ciclo o un camino hamiltoniano
Matriz de adyacencia La representación más
obvia de un grafo es una matriz de adyacencia A(u,v), tal que A(u,v)=1 si (u,v) A.
Requiere un espacio de almacenamiento O(n2), pero permite conocer la existencia de un arco en tiempo O(1) .
Dos nodos i,j están conectados por un camino de longitud k sii Ak (i,j)=1.
Listas de adyacencia Es una representación
formada por n listas de adyacencia (una por cada nodo), cada una de ellas con tantas componentes como nodos adyacentes tenga.
Requiere un espacio de almacenamiento O(n+a), pero se necesita un tiempo O(n) para determinar si existe un arco.
Doble vector Representación formada
por dos vectores, uno. El primero de ellos (V1), con tantas componentes como nodos. El segundo (V2) con tantas componentes como arcos.
Cada componente i de V1 señala la posición en V2 del primer nodo adyacente al nodo i . El resto de los adyacentes se colocan a continuación.
Recorrido de un grafo En un gran número de problemas es
necesario visitar los nodos de un grafo buscando uno que cumpla cierta condición.
Para ello, se emplean métodos específicos de eficiencia garantizada.
Aquí se verán dos de ellas, denominadas búsqueda en profundidad y búsqueda en amplitud.
Búsqueda en profundidad El algoritmo de
búsqueda en profundidad parte de un nodo, seleccionado como nodo de partida, marcándolo como visitado.
Después recorre cada vértice no visitado adyacente a u, usando recursivamente la misma función de búsqueda.
Búsqueda en profundidad
Búsqueda en amplitud El algoritmo de búsqueda
en amplitud parte de un nodo, seleccionado como nodo de partida, marcándolo como visitado.
Seguidamente, visita todos los vértices conectados al mismo.
El proceso de repite para cada uno de los vértices que han sido visitados.
Búsqueda en amplitud
Comparación de estrategias
Búsqueda en profundidad: Complejidad temporal: O(bm) Complejidad espacial: O(bm)
Búsqueda en amplitud Complejidad temporal: O(bd) Complejidad espacial: O(bd)
Siendo b el factor de ramificación, d la profundidad de búsqueda y m la máxima profundidad del árbol expandido.
Biconectividad
Un grafo G=(V,A) es biconexo si para cada par de vértices, existe al menos dos caminos que solo coinciden en sus extremos
Biconectividad
Un grafo G=(V,A) es biconexo si para cada par de vértices, existe al menos dos caminos que solo coinciden en sus extremos
Biconectividad
Un grafo G=(V,A) para el que existe un vértice que es paso obligado en el camino entre dos vértices no es biconexo y ese vértice se llama punto de aticulación
BiconectividadUn árbol de búsqueda en profundidad permite detectar un punto de articulación, cuando-La raíz principal tiene más de una rama-Existe un nodo del árbol que ninguno de sus descendientes tiene arcos de retorno hacia alguno de sus ancestros
Árbol expandido
Dado un grafo conexo G, un árbol expandido es un árbol que conecta todos los vértices de G. Su coste es la suma de los costes de sus arcos.Un mismo grafo no dirigido conexo puede tener más de un árbol expandido.
Árbol expandido mínimo Sea un grafo etiquetado G(V,A) conexo
cuyos pesos representan un coste. Se pretende hallar el árbol expandido en el que la suma de los pesos de todos sus arcos sea mínima; dicho árbol se conoce como árbol expandido de coste mínimo.
El método ávido (greedy , voraz) conduce a dos de los algoritmos más conocidos para obtenerlos: el algoritmo de Kruskal y el algoritmo de Prim.
Algoritmo de Kruskal El algoritmo de Kruskal
construye el árbol expandido de coste mínimo eligiendo los de menor coste y desechando los que forman un ciclo con los arcos ya existentes.
Como G es conexo, si tiene n>0 nodos, se tomarán exactamente n-1 arcos para formar T.
Complejidad: O(a log a)
Algoritmo de Kruskal
Ejemplo
Algoritmo de Prim El algoritmo de Prim
comienza con un árbol T que contiene al nodo inicial.
Después se añade a T el arco (u,v) de menor costo tal que T {(u,v)} sea también un árbol. Este proceso se realiza hasta que T contenga n-1 arcos.
Complejidad: O(n2)
Algoritmo de Prim
Ejemplo:
Búsqueda de caminos óptimos Por simplicidad, al hablar del
camino óptimo, nos referiremos al camino más corto entre dos nodos de un grafo.
En general, la forma de abordar el problema dependerá Del tipo de grafo De la pregunta exacta que se haga
.../
Búsqueda de caminos óptimos
El grafo puede ser dirigido o no. Los arcos pueden tener todos peso uno o
pesos de cualquier valor, incluso negativos. Se puede estar interesado en el camino más
corto desde un vértice dado a otro, desde un vértice a todos los demás o desde cada vértice a todos los demás.
Se puede estar interesado en encontrar un camino, todos los caminos o simplemente contar el número de caminos más cortos
Unas preguntas sencillas... Dado un grafo conexo G(V,A),
encontrar el camino, si existe, con menor número de arcos entre dos nodos dados u y v.
Dado un nodo u de un grafo conexo ponderado G(V,A) , encontrar el camino más corto a todos los demás.
Planteamiento del problema Sea G=<V,A> un grafo ponderado de
grado n. Supóngase que cada arco lleva
asociada una etiqueta (peso) no negativa.
El problema consiste en determinar el coste del camino más corto desde s a todos los demás vértices de V. ¿Pueden servir los métodos anteriores
para resolver este problema?
Una primera aproximación
Inicialmente, a todos los nudos se les da un valor muy alto (infinito).
Se da valor 0 al nudo inicial y dicho valor se propaga a los vecinos incrementado con el peso de los arcos que los enlazan.
Se repite el proceso para los nudos modificados, propagando su valor incrementado a nudos vecinos si es menor que el que tienen.
Algo de eso hay...,pero, por el momento, vamos a ver un método de fuerza bruta:
Método de propagación Supongamos que se
tiene una pila LIFO (last input first output) donde se guardan los nodos modificados.
A todos los nodos se les da valor infinito. Se da valor 0 al nudo origen A. Dicho nudo pasa a pila.
Pila: {A}
Método de propagación Paso 1: Se saca el nodo
último de la pila A y se propaga el coste a los vecinos. Los nodos B y C se guardan en la pila.
Pila: {B, C} Paso 2: Se saca el nodo
último de la pila (C) y se propaga el coste a los vecinos (D y E) Los nodos D y E se guardan en la pila.
Pila: {B, D, E}
Método de propagación Paso 3: Se saca el nodo
E y se propaga el coste al vecino cuyo valor es mayor que el calculado (F). El nudo F se guardan en la pila.
Pila: {B, D, F} Paso 4: Se repite el
proceso para F y D. El nudo F vuelve a la pila.
Pila: {B, F}
Método de propagación Paso 5: Se saca el núdo
último de la pila (F) y no puede propagar el coste a los vecinos.
Pila: {B} Paso 6: Igualmente
sucede con el nudo B. Como la pila queda
vacía, se acaba el proceso.
Determinar camino óptimo Los valores acumulados en los nodos
permiten determinar los caminos óptimos desde el nodo origen a cualquiera de los nodos del grafo.
Para ello, basta con recorrer el grafo en sentido inverso al empleado en el paso anterior, es decir, desde el nodo destino hasta el nodo origen (backtracking).
Camino entre A y F Paso 1: Se parte del
nodo destino F (nodo actual) y se elige al vecino cuyo valor difiere en el peso del arco (D).
Paso 2: Ahora el nodo actual es el nodo D. Se repite el proceso y se toma como siguiente al C.
Camino entre A y F Paso 3: El nuevo
nodo actual es C. Se repite el proceso y se elige el nodo A
Paso 4: Se tiene como nuevo nodo actual el A.
Como es el nodo origen, se acaba el proceso.
Algoritmo de Dijkstra Introduce algunas variantes para mejorar
el rendimiento, basadas en que un camino óptimo es combinación de caminos óptimos siempre que los costes de los arcos sean positivos.
Se establecen dos listas: la lista S de nodos resueltos y la lista V-S de nodos no tratados. Para cada nodo se tiene la estimación del coste de llegada desde el origen (similar a los valores acumulados anteriores) y un puntero a su predecesor.
Algoritmo de Dijkstra Inicialmente, los nodos están en V-S y
tienen valor D[i]=, salvo el origen que tiene valor D[o]=0. Los predecesores tienen valor nulo.
En cada iteración se toma el nodo de menor valor de la lista V-S y se pasa a la lista S.
Se examinan los nodos conectados a él de la lista V-S y, si el valor propagado es menor que el existente, se modifica y se actualiza el puntero de predecesor.
Se repite el proceso hasta que no quedan nodos en la lista V-S.
Algoritmo de Dijkstra
La complejidad de este algoritmo es O(n2).
Ejemplo Dijkstra
Ejemplo Dijkstra
Ejemplo DijkstraPara reconstruir el camino más corto del origen a cada vértice, se siguen los predecesores en orden inverso. Por ejemplo si se desea conocer el camino desde el origen al vértice 5, se tiene
Algoritmo de Floyd Este algoritmo utiliza una matriz A de
dimensión nxn en la que se calculan las longitudes de los caminos más cortos.
Inicialmente se hace A[i,j] = C[i,j] para cada i distinto de j, donde C es la matriz de pesos del grafo. Si no existe un arco que vaya de i a j se supone que C[i,j] = .
Cada elemento de la diagonal de la matriz A se hace igual a cero.
Algoritmo de Floyd En la k-ésima iteración se aplica la
fórmula: Ak [i,j] = min (Ak-1 [i,j], Ak-1[i,k] + Ak-1[k,j])
De esta forma, tras la k-ésima iteración, A[i,j] contendrá el valor de la longitud más pequeña del camino que va desde el nodo i hasta el nodo j sin pasar por un vértice con número mayor que k.
El proceso termina tras n iteraciones.
Algoritmo de Floyd
Para obtener Ak [i,j], se compara Ak-1[i,j], coste de ir de i a j sin pasar por el nodo k u otro con numeración mayor, con Ak-1[i,k] + Ak-1[k,j], coste de ir primero de i a k y después de k a j y se elige el menor.
Aclaración:
Algoritmo de Floyd
Complejidad O(n3)
Algoritmo de FloydPara hallar el camino óptimo entre dos nodos, se emplea el siguiente algoritmo:
Ejemplo Floyd
Aplicar el algoritmo de Floyd al grafo dirigido y hallar el camino óptimo entre cualquier pareja de nodos.
Algoritmo A*
El mejor camino entre dos nodos es el de distancia total mínima.
A mitad de camino, sólo se conoce la distancia recorrida.
Si se tuviera una estimación de “lo que queda ” por recorrer, se podría intentar progresar por el camino más prometedor, sin perder tiempo con el resto.
Hagamos ahora una pequeña reflexión sobre el algoritmo de Dijkstra aplicado a distancias:
Algoritmo A* Si la estimación que se hace es siempre
menor que la distancia real, el camino hallado en primer lugar entre los nodos origen y destino será el óptimo pues: Será el mejor frente al resto de candidatos y su
distancia es verdadera, no estimada. Los demás son peores y su verdadera distancia
sólo puede ser mayor o igual a la estimada. Si se toma como estimación el valor nulo,
el algoritmo resultante es el algoritmo de Dijkstra.
Algoritmo A*
Se tienen dos listas, la Abierta y la Cerrada. En la lista Abierta se guardan los nodos a los que se ha llegado desde el origen. En la Cerrada los que se consideran resueltos.
Para los nodos visitados, se conocen dos valores: la distancia desde el origen R y distancia estimada al destino E. La suma de ambas T es la que servirá para elegir.
Ahora, se puede seguir una estrategia similar a la del algoritmo de Dijkstra, con algunas matizaciones:
Algoritmo A* Inicialmente, se coloca el origen en la
lista Abierta y se le asignan valores R[o]=0, E=E[o].
En cada iteración se toma el nodo de menor valor T de la lista Abierta y se pasa a la lista Cerrada.
Se examinan los nodos conectados a él, menos su predecesor y se pasan a la Abierta, actualizando R, E y punteros, si no existen con anterioridad en Cerrada o en Abierta o, estando en Abierta, su valor es menor que el existente.
Ejemplo
En el ejemplo de la figura, se ha superpuesto una rejilla para estimar distancias. Supóngase que se quiere determinar el camino optimo entre A y F. Inicialmente, se toma el origen y se coloca en la lista Abierta.
Ejemplo
El nodo A pasa a lista cerrada y se pasan a la lista Abierta los conectados con el (B y C), asignándoles valores R, E y punteros al antecesor (A).
Ejemplo
Se selecciona el de menor valor T de la lista Abierta (C) y se pasa a lista cerrada. Los conectados con el (D y E) se pasan a Abierta, asignándoles valores R, E y punteros al antecesor (C).
Ejemplo
Se selecciona el de menor valor T de la lista Abierta (B) y se pasa a lista cerrada. Los conectados con el (D y E) no se pasan a Abierta, pues el valor T es mayor que los ya existentes.
Ejemplo
Se selecciona el de menor valor T de la lista Abierta (D) y se pasa a lista cerrada. Sólo se pasa el nodo F a Abierta, pues B está ya en cerrada.
Ejemplo
Se selecciona el de menor valor T de la lista Abierta (F) y se pasa a lista cerrada. Como es el nodo destino, se acaba el proceso.
Ejemplo
Ahora, se puede recuperar el camino óptimo retrocediendo desde el nodo F mediante los punteros.
Comentarios En el ejemplo anterior no se ha
podido apreciar demasiado la ventaja del método debido a la estimación empleada.
Cuanto mejor sea la estimación, mejor resultado se obtendrá.
En la práctica, sin embargo, no siempre es fácil hallar una estimación apropiada.
Grafos Especiales Grafo regular: Aquel con el mismo
grado en todos los vértices. Si ese grado es k lo llamaremos k-
regular.
Grafos Especiales Grafo bipartito: Es aquel con cuyos
vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto
Grafos Especiales Grafo completo: Aquel con una
arista entre cada par de vértices. Un grafo completo con n vértices
se denota Kn.
Grafos Especiales Un grafo bipartido regular se
denota Km,n donde m, n es el grado de cada conjunto disjunto de vértices.
Grafos Especiales Ciclo de n vertices es un grafo
simple, llamado C1, C2, C3 …
Grafos Especiales La Rueda Wn se
obtiene añadiendo un vertice adicional a un Cn y uniendo ese vertice con todos los demas.
Grafos Especiales El Qn o n-cubo, sirve para
representar las secuencias de n elementos binarios
Grafos Isomorfos Dados dos grafos G=(V,E) y G´=(V
´,E´), se denomina Isomorfismo entre G y G´ a cualquier aplicación biyectiva f:G G’ tal que si a, b V, entonces {a,b}E {f(a),f(b)}E´.
Grafos Isomorfos . Es decir, es una aplicación biyectiva
entre los vértices de V y los de V´ de modo que los vértices conectados siguen estándolo. En este caso, diremos que G y G´ son isomorfos.
Si G y G’ son isomorfos son matemáticamente iguales y solo varía la apariencia, o sea, que se mantienen las adyacencias, estructura, caminos, ciclos, nº de vértices, nº de aristas
Grafos Isomorfos
Grafos Isomorfos En otras palabras, dos grafos son
isomorfos si sus matrices de adyacencia son de igual tamaño y en algún orden de estas son iguales.
Grafos Planos Un grafo se dice plano si admite
una representación gráfica en el plano de modo que dos aristas pueden cortarse únicamente en un vértice.
Una representación gráfica de este tipo se llama un mapa.
Grafos Planos
Grafos Planos Un mapa divide al plano
en varias partes llamadas regiones.
Cada región de un mapa M está delimitada por un ciclo si el mapa es conexo.
También se cuenta como región la exterior a la figura.
Grafos Planos Se llama grado de una región a la
longitud del camino que la bordea. Dos regiones de un mapa se
consideran adyacentes si el circuito que las bordea tiene alguna arista en común.
Grafos Planos La suma de los grados de las
regiones de un mapa es igual al doble del número de aristas del grafo al que representa.
Grafos Planos Frontera doble Toda arco es
frontera simple de 2 regiones o doble de la misma región.
Grafos Planos Todo mapa conexo verifica regiones + vértices – arcos = 2
Grafos Planos Teorema (de los 4 colores).- El
número cromático de un grafo plano es siempre menor o igual que 4.
Grafos Planos Un grafo G se dice que es bipartido
si se puede colorear con 2 colores Un grafo es bipartito no
tiene circuitos de longitud impar.
Grafos Planos Teorema ( de Kuratowski) Un grafo G es plano no
contiene ningún subgrafo isomorfo a una subdivisión de K5 o K3,3.
Eso es todo por ahora...
¿Alguna pregunta?