Tópicos I Unidad I Algoritmos sobre grafos elementales, Conectividad y Grafos ponderados Semana 4 Árboles, montículos y grafos.

  • Published on
    02-Feb-2016

  • View
    261

  • Download
    0

Embed Size (px)

Transcript

  • Tpicos IAlgoritmos sobre grafos elementales, Conectividad y Grafos ponderadosSemana 4rboles, montculos y grafos

  • Objetivos GeneralesEntender el manejo, uso de algoritmos y estructuras de datos avanzados, haciendo nfasis en los algoritmos de internet, seguridad y redes.

  • Objetivo EspecficoImplementar algoritmos utilizando estructura de datos avanzadas.

  • Objetivo InstruccionalImplementar algoritmos fundamentales para la solucin de problemas basados en la teora de grafos.

  • GlosarioGrafo: Un grafo es una coleccin de vrtices y aristas. Los vrtices son objetos simples que pueden tener un nombre y otras propiedades; una arista es una conexin entre dos vrtices.

    Camino: Un camino entre los vrtices x e y de un grafo es una lista de vrtices en la que dos elementos sucesivos estn conectados por aristas del grafo.

  • GlosarioGrafo conexo: Un grafo es conexo si hay un camino desde cada nodo hacia otro nodo del grafo.

    Grafo no conexo: Esta constituido por componentes conexos.

    Camino simple: Es un camino en el que no se repite ningn vrtice.

    Ciclo: es un camino simple con la caracterstica de que el primero y el ultimo vrtices son el mismo.

  • GlosarioGrafo completo: Son los grafos con todas las aristas posibles.

    Grafo disperso: Tienen relativamente pocas aristas.

    Grafo denso: Les falta muy pocas aristas de todas las posibles.

  • RepresentacinMatriz de adyacencia:

    Se construye un array de V*V valores booleanos en el que a[x][y] es igual a 1 si existe una arista desde el vrtice x al y, y a 0 en el caso contrario.Es de destacar que en realidad cada arista se representa con dos bits: una arista que enlace x e y se representa con valores verdaderos tanto en a[x][y] como en a[y][x].La matriz de adyacencia solo es satisfactoria si los grafos a procesar son densos.

    ABCDEFGA1110011B1100000C1010000D0001110E0001111F1001110G1000101

  • RepresentacinLista de adyacencia:

    La lista de adyacencia se adapta mejor a lo casos en los que los grafos a procesar no son densos.FAAAABCGEFDDFGEE

    ABCDEFG

  • Recorridos en un grafoEn una gran cantidad de problemas con grafos, es necesario visitar sistemticamente los vrtices y aristas del grafo.

    La bsqueda en PROFUNDIDAD y en AMPLITUD, son dos tcnicas importantes de recorrido del grafo.

  • Bsqueda en Profundidad (BEP)Se comienza en el vrtice inicial (vrtice con ndice 1) que se marca como vrtice activo. Hasta que todos los vrtices hayan sido visitados, en cada paso se avanza al vecino con el menor ndice siempre que se pueda, pasando este a ser el vrtice activo. Cuando todos los vecinos al vrtice activo hayan sido visitados, se retrocede al vrtice X desde el que se alcanz el vrtice activo y se prosigue siendo ahora X el vrtice activo.

  • Bsqueda en ProfundidadLa estructura utilizada para guardar los nodos a visitar en este tipo de bsqueda es una pila o stack (de procedimiento recursivo).

  • Bsqueda en Amplitud (BEA)Se comienza en el vrtice inicial (vrtice con ndice 1) y se marca como vrtice activo, a diferencia con la BEP ahora se visitan en orden creciente de ndice todos los vecinos del vrtice activo antes de pasar al siguiente. Hasta que todos los vrtices hayan sido visitados, en cada paso se van visitando en orden creciente de ndice todos los vecinos del vrtice activo. Cuando se han visitado todos los vecinos del vrtice activo, se toma como nuevo vrtice activo el primer vrtice X visitado despus del actual vrtice activo.

  • Bsqueda en AmplitudEn la bsqueda en amplitud se utiliza una cola para guardar tales nodos a visitar.

  • Usos de los RecorridosAmbos recorridos se pueden usar para resolver los siguientes problemas:Probar que G es conectado.Obtener un rbol de expansin de G.Obtener los componentes conectados de G.Obtener un camino entre dos vrtices dados de G, o indicar que no existe tal camino.El recorrido BEP se usa para:Obtener un ciclo en G, o indicar que G no tiene ciclos.El recorrido BEA se usa para:Obtener para cada vrtice v de G, el nmero mnimo de aristas de cualquier camino entre s y v.

  • LaberintosLa bsqueda en profundidad fue expuesta formalmente como un mtodo para recorrer laberintos.El grafo se construye colocando un vrtice en cada punto en el que existe mas de un camino a tomar y a conectar a continuacin los vrtices de acuerdo con esos caminos.La bsqueda en profundidad es apropiada para la bsqueda de un elemento en el laberinto por una sola persona, dado que el siguiente lugar a visitar esta siempre prximo; la bsqueda es amplitud es mas apropiada par un grupo de personas que buscan el mismo elemento desplazndose en todas las direcciones a la vez

  • ProblemticaSe examinara una generalizacin de la conectividad denominada biconectividad, cuyo inters reside en conocer si hay mas de un medio de pasar de un vrtice de un grafo a otro.

    Grafo biconexo: Un grafo es biconexo, si solo si, existen al menos dos caminos diferentes que conecten cada par de vrtices. De esta forma si se suprime un vrtice y todas las aristas que inciden en el, el grafo permanece conexo.Si para algunas aplicaciones es importante que un grafo sea conexo, es tambin importante que permanezca conexo

  • ProblemticaUna versin particular del problema de la conectividad, que con frecuencia concierne a la situacin dinmica en las que las aristas se aaden al grafo una a una, intercalando preguntas sobre si dos vrtices determinados pertenecen (o no) a la misma componente conexa.

    El problema se denomina a veces como unin-pertenencia.

  • Componentes conexasDe un grafo no dirigidoSe pude saber si es conexoSi no lo es se pueden conocer sus Componentes ConexasConjunto W, de vrtices del grafoEn el cual hay camino desde cualquier V1 a cualquier V2 Donde V1 y V2 pertenecen a W

    CONEXONo CONEXOComponentes conexas: entre ellas son conexas

  • BiconectividadA veces es til disear mas de una ruta entre puntos de un grafo, aunque solo sea para identificar posibles fallos en los puntos de conexin (vrtices). Esto nos permitira tener recorridos alternativos por ejemplo para llegar de una ciudad a otra.

  • Puntos de articulacinEn un grafo no dirigido conexo:Existen vrtices que si se eliminanDesconectan al GrafoLo dividen en componentes conexasEstos vrtices clave son puntos de articulacinSi un grafo no tiene Punto de ArticulacinEs biconexoLa conectividad de un grafoEs el numero de nodos que se necesitan eliminar para dejar a un grafo desconectadoUn punto de articulacin en un grafo conexo es un vrtice que si se suprime romper el grafo en dos o mas piezas.

  • EjemploPuntos de ArticulacinPuntos de articulacin

  • rbol de expansinDefinicin: Un rbol T es un rbol de expansin de un grafo G si T es un subgrafo que contiene a todos los vrtices de G.

  • rbol de expansinPara poder calcular los Puntos de Articulacin de un grafoHay que obtener el rbol de expansinEste se obtieneA partir del Recorrido en Profundidad

    Ejemplo:

    Arco en Retroceso: Cuando se quiere visitar un nodo que ya ha sido visitado y no es el padre

  • Como representar el rbol de expansinUn rbol en expansinNo es un rbol binarioCada Vrtice puede tener 0, 1 o n hijos

    Si no tomamos en cuenta los arcos en retroceso, la representacin depende del GrafoMatriz de Adyacencia -> Usar un arreglo Lista de Adyacencia -> Una lista

    La representacin mostrar quien es el padre de cada nodo

  • rbol de expansin con matriz de adyacenciaLos vrtices del grafoSe encuentran en un arregloCada ndice del arregloRepresenta un vrticeEj: A 0, B 1, etc.Al representar el rbol de expansinEl padre(ndice) de cada nodo puede almacenarse en un arregloQue tambin represente a los vrtices

    0400520A1B2C3D4E5Ftypedef struct TVertices{Generico V[MAX];int Padres[MAX];int nvertices;}Vertices;

  • rbol de expansin con lista de adyacenciaLos vrtices del grafoSe encuentran en una listaCada nodo representa un vrticeAl representar el rbol de expansinDe cada nodo de esta lista solo nos interesa conocer al padreSe puede aadir un dato al nodo vrticeUn enlace con el padreADCBEFtypedef struct Vertice{ Generico Informacion; Vertice *padre; Lista *LArcos;}Vertice;

  • Unin - PertenenciaEn algunas aplicaciones se desea simplemente conocer si un vrtice x esta o no conectado a un vrtice y de un grafo, sin que sea importante el camino que los conecta.

    Los grafos se corresponden de forma natural con los conjuntos (colecciones de objetos): los vrtices representan a los objetos y las aristas significan esta en el mismo conjunto que.

    ABCGDEF{A F D E} {B C G}Conjuntos clases de equivalenciaCada componente conexa corresponde a una clase de equivalencia diferente

  • Unin - PertenenciaEl aadir una arista se corresponde con la combinacin de las clases de equivalencia representadas por los vrtices a conectar.

    El inters se centra en la pregunta fundamental x es equivalente a y est x en el mismo conjunto que y?. Esto se corresponde claramente con la pregunta fundamental de los grafos est el vrtice x conectado al vrtice y?

    Dado un conjunto de aristas, se puede construir una representacin por lista de adyacencia que corresponda al grafo y utilizar la bsqueda en profundidad para asignar a cada vrtice el ndice de su correspondiente conexa y responder a las preguntas antes planteada con tal solo dos accesos a arrays y una comparacin

  • Unin - PertenenciaPor correspondencia con el problema de los conjuntos, la adicin de una nueva arista se denomina una operacin de unin, y las preguntas se denominan operaciones de pertenencia.

    El objetivo es escribir una funcin que pueda verificar si dos vrtices x e y pertenecen al mismo conjunto (o, en representacin de grafos, a la misma componente conexa) y, en caso de que sea as, que pueda unirlos en el mismo conjunto (colocando una arista entre ellos y el grafo).

    En lugar de construir una lista de adyacencia directa o cualquier otra representacin de los grafos, es mas eficaz utilizar una estructura interna orientada especficamente a la realizacin de las operaciones unin y pertenencia.

  • Unin - PertenenciaEsta estructura interna es un bosque de arboles, uno por cada componente conexa.

    Se necesita poder encontrar si dos vrtices pertenecen al mismo rbol y combinar dos arboles en uno.

  • Unin - PertenenciaPara ilustrar como trabaja este algoritmo, vamos a ver el bosque construido por los siguientes vrtices (A-B-C-D-E-F-G-H-I-J-K-L-M) cuando se le insertan estas aristas en el siguiente orden: AG - AB - AC - LM - JM - JL - JK - ED - FD - HI - FE - AF - GE - GC - GH - JG - LG. Inicialmente todos los nodos estn en rboles separados (cada vrtice es un rbol). ABCDEFGHIJKLM

  • Unin - PertenenciaLuego la arista AG crea un rbol de dos nodos con A como raz (esta decisin es arbitraria, porque tranquilamente podramos haber puesto G como raz). Las aristas AB y AC agregan B y C al rbol de la misma forma.

  • Unin - PertenenciaProceso culminado

  • Unin - PertenenciaEs necesario recalcar que, al contrario que en los rboles de bsqueda primero en profundidad, la nica relacin entre estos rboles de unin y el grafo original con las aristas dadas es que dividen a los vrtices en grupos de la misma forma. Por ejemplo, no hay ninguna correspondencia entre los caminos que conectan nodos en los rboles y los caminos que conectan nodos en el grafo.

    Para representar estos rboles es apropiado usar la representacin enlace padre" porque siempre se viaja hacia arriba en los rboles, nunca hacia abajo. Especficamente, mantenemos un array padre que contiene, para cada vrtice, el ndice de su padre (0 si es la raz de algn rbol), como se especifica en la prxima declaracin de la clase:

  • Unin - Pertenenciaclass EQ{private:int *dad;public:EQ(int size);Int find(int x, int y, int doit);};

    El constructor reserva el espacio para el array dad y setea todos sus valores inicialmente a cero (se omite el cdigo). Se usa un solo procedimiento find para implementar ambos, la unin y la bsqueda. Si el tercer argumento es 0 se hace una bsqueda, si no es 0, se hace una unin. Para encontrar al padre del vrtice j, simplemente se hace j = dad[j], y para encontrar la raz del rbol al que pertenece j se repite esta operacin hasta que se llega a 0.

  • Unin - PertenenciaEsto nos lleva a la siguiente implementacin del procedimiento:

    Int EQ::find(int x, int y, int doit){int i=x, j=y;while (dad[i] >0) i = dad[i];while (dad[j] > 0) j=dad[j];if (doit && (i != j)) dad[j]=i;return (i != j);}

    La funcin find retorna 0 si los dos vrtices dados estn en el mismo componente. Si no lo estn y el flag doit esta seteado, son puestos en el mismo componente. El mtodo es simple. Usar el array dad para llegar a la raz del rbol que contiene cada vrtice, luego chequear si las races son las mismas. Para mezclar el rbol con raz j con el rbol de raz i simplemente se setea dad[j] = i.

  • Unin - PertenenciaContenido de la estructura de datos union-pertenencia durante el proceso

  • Unin - PertenenciaEl algoritmo descrito anteriormente tiene un mal desempeo para su peor caso porque los rboles formados pueden ser degenerados.

    Por ejemplo, tomando en orden las aristas AB BC CD DE EF FG GH HI IJ YZ se produce una larga cadena con Z apuntando a Y, Y apuntando a X, etc. Este tipo de estructura toma un tiempo proporcional a V2 para construirse y tiene un tiempo proporcional a V para una prueba promedio de equivalencia.

  • Unin - PertenenciaVarios mtodos han sido sugeridos para lidiar con esta dificultad. Un mtodo natural es tratar de hacer lo correcto para mezclar dos rboles, en lugar de hacer arbitrariamente dad[ j ] = i. Cuando un rbol con raz en i va a ser mezclado con otro con raz en j, uno de los nodos debe mantenerse como raz y el otro (y todos sus descendientes) deben ir un nivel ms abajo en el rbol.

    Para minimizar la distancia a la raz de la mayora de los nodos tiene sentido elegir como raz el nodo con ms descendientes.

  • Unin - PertenenciaEsta idea, llamada equilibrado de peso, es fcilmente implementable manteniendo el tamao de cada rbol (cantidad de descendientes de la raz) en el array dad para cada nodo raz, codificado como un nmero no positivo de tal modo que el nodo raz pueda ser detectado cuando se viaja hacia arriba en el rbol con find.

  • Unin - PertenenciaIdealmente se deseara que cada nodo apuntara directamente a la raz de su rbol. Sin importar que estrategia se use, para lograr este objetivo se necesita examinar al menos todos los nodos en uno de los dos rboles a mezclar y esto puede ser demasiado comparado con los pocos nodos en el camino a la raz que find generalmente examina. Sin embargo podemos aproximarnos a este ideal haciendo que todos los nodos que s se examinan apunten a la raz. Este mtodo, conocido como compresin de caminos, se implementa fcilmente haciendo otra pasada por cada rbol, despus de que la raz fue encontrada, y seteando la entrada dad de cada vrtice encontrado a lo largo del camino para que apunte a la raz.

  • Unin - PertenenciaLa combinacin de compresin de caminos y equilibrado de peso nos aseguran que los algoritmos van a correr muy rpido. La siguiente implementacin muestra que el cdigo extra necesario es un pequeo precio a pagar para protegernos de los casos degenerados.

    int EQ::find(int x, int y, int doit){int t, i=x, j=y;while (dad[i] > 0)i=dad[i];while (dad[j] > 0)j=dad[j];while (dad[x]>0) { t=x...

Recommended

View more >