UNIDAD 3

Tarea 3

Graficas

.- Resumen del capítulo 7 Graficas del libro Estructura de Datos de Osvaldo Cairo y Silvia Guardati

 Las gráficas son estructuras de datos no lineales en donde cada componente puede tener uno o más predecesores y sucesores. En una gráfica se distinguen dos elementos: los nodos, mejor conocidos como vértices y los arcos, llamados aristas, que conectan un vértice a otro. Los vértices almacenan información y las aristas representan relaciones entre dicha información.

Definición de graficas

Una gráfica G consta de dos conjuntos: V (G) y A (G). El primero lo integran elementos llamados nodos o vértices, el segundo arcos o aristas. Por lo cual podemos representar una gráfica G de la siguiente manera.

                                   

Conceptos básicos de gráficas

·         Grado de un vértice: se escribe como grado (V), consta del número de aristas que conforman el vértice.  Si v =0 representa que no tiene aristas y se define como nodo aislado

·         Lazo o bucle: Es la arista que conecta consigo mismo a V. se define como a= (u, u).

·         Camino: representado por P de longitud n se define como la secuencia de n vértices que se debe seguir para llegar al vértice V1 –origen- al vértice n –destino-.

·         Camino cerrado:  P es cerrado si el primero y el ultimo vértices son iguales

·         Camino simple:  cuando todos sus nodos son distintos, con excepción del primero y el ultimo, que pueden ser iguales

·         Ciclo: es un camino simple cerrado de longitud 3 o mayor. Un ciclo de longitud k se llama k-ciclo

·         Gráfica conexa: cuando existe un camino entre cualesquiera dos de sus nodos

·         Gráfica árbol: es una gráfica conexa sin ciclos

·         Gráfica completa: si cada vértice v de G es adyacente a todos los demás V de G.

·         Gráfica Etiquetada: cuando sus aristas tienen asignado un valor, es decir, cada arista a tiene un valor numérico no negativo c(a), llamado costo, peso o longitud de a, entonces G tiene peso o esta etiquetado.

·         Multigráfica: cuando al menos dos de sus vértices están conectados entre sí por medio de dos aristas. Estas aristas también se conocen por aristas múltiples o paralelas.

·         Subgráfica: se denomina Subgráfica de G, donde cada arista de A´ es incidente de V´

Las gráficas dirigidas se caracterizan porque sus aristas tienen asociada una dirección: es decir, son pares ordenados. Los vértices se utilizan para representar información, mientras que las aristas representan una relación con dirección o jerarquía entre aquellos.

Una gráfica dirigida G, también llamada digráfica se caracteriza porque cada arista a tiene una dirección asignada; es decir, cada arista está asociada a un par ordenado (u.v) de vértices G.

Representación de gráficas dirigidas

Las digráficas son estructura de datos abstractas. Para su representación se requiere usar otras estructuras de datos. Para la elección de la más adecuada depende del uso que se le vaya  a dar a la información almacenada en los vértices y en las aristas. Las representaciones más usadas para este tipo de gráficas son las matrices y las listas de adyacencia.

Matriz de adyacencia: es una matriz booleana de orden n, donde n indica el número de vértices de G. los renglones y columnas de la matriz representan a los vértices y su contenido a no de arcos entre ellos.

Lista de adyacencia

Es una lista ordenada de todos los vértices adyacentes de a. Por lo cual esta lista puede representar una gráfica dirigida, estará formada por tantas listas como vértices tenga G. Para que puedan guardarse los vértices de G se puede utilizar otra lista o un arreglo.

Obtención de caminos dentro de una digráfica

Buscamos en una estructura de datos el ajuste a las características especiales a nuestros problemas, se busca también que sobre dicha estructura se puedan realizar operaciones que faciliten el manejo de la información almacenada en ella. Los algoritmos más usados para este fin son: Dijkstra, Floyd y Warshall. Los tres algoritmos utilizan una matriz de adyacencia etiquetada donde:  

                M [i, j]= 0 Si i=j

                M [i, j]= ∞ si no existe un camino de i a j, donde i ≠ j

                M [i, j]=  costo de ir del vértice i al vértice j, si existe a (i, j).

Algoritmo Dijkstra

Encuentra el camino más corto de un vértice elegido a cualquier otro vértice de la digráfica, donde la longitud de un camino es la suma de los pesos de las aristas que lo forman. Las aristas deben poseer un valor de peso no negativo

Los siguientes pasos deben considerarse cuando se desea aplicar un algoritmo Dijkstra:

S es un arreglo formado por los vértices de los cuales ya se conocen la distancia mínima entre ellos y el origen. Esto se almacena al nodo origen

D es un arreglo formado por la distancia del vértice origen a cada uno d los otros. Es decir D almacena la menor distancia, o costo, entre el origen y el vértice. A este camino se le conoce como especial.

M es una matriz de distancias de n x n elementos, tal que M [i, j] almacena la distancia o costo entre los vértices i y j, si entre ambos existe una arista, en caso contrario M [i, j] será un valor muy grande (∞).

Algoritmo de Floyd

Encuentra el camino más corto entre todos los vértices de la digráfica. El algoritmo de Floyd permitirá encontrar el camino más corto entre cada par ordenado u y v.

La matriz de distancia sirve como punto de partida para este algoritmo. Se realizan k iteraciones sobre la matriz buscando el camino más corto; por lo tanto, en la k-ésima iteración, M [I, J] tendra el camino de menor costo para llegar de i a j, pasando por un numero de vértices menor de k, el cual se calculará según la siguiente forma:

Algoritmo de Warshall

Esta estructura encuentra, solo si es posible, un camino entre cada uno de los vértices de la gráfica dirigida, esto es, que la solución encontrada no presenta la distancia entre los vértices, solo te mostrara si hay caminos o no entre ellos.

Se  basa en un concepto de cerradura transitiva de la matriz de adyacencia. Sea la gráfica dirigida G (V, A) y su matriz de adyacencia M donde M [i, j]=1 si hay un arco de i a j y 0 si no lo hay. La cerradura transitiva de M es la matriz de C. Para generar la matriz de C se establece que existe un camino del vértice i a j que no pasa por un número de vértices mayor que k si:

·         ya existe un camino de  i a j que no pasa por un número de vértices mayor que -1.

·         Hay un camino de i a k  que no pasa por un numero de vértices mayor que k-1

Hay un camino de k a j que no pasa por un número de vértices mayor que k-1

Ejemplo:

Gráficas no Dirigidas

La característica principal es que sus aristas son pares no ordenados de vértices, es decir, que si existe un camino del vértice i a la j, será exactamente el mismo camino del vértice j a i.

Estas gráficas se utilizan para poder modelar relaciones simétricas entre objetos diferentes, que son representados por medio de los vértices, mientras que las aristas se utilizan para indicar la relación existente entre ellos.

Ejemplo:

Construcción del árbol abarcador del costo mínimo

Este tipo de árbol se define como un árbol libre que conecta todos los vértices de V. El costo del árbol abarcador resulta de la suma de las aristas incluidas en el. Por lo que, un árbol abarcador de costo mínimo de forma a partir de las aristas de menor costo. Este tipo de arboles posee una propiedad que sirve como base para todos los algoritmos utilizados para su construcción.

Algoritmos de Prim

Permite encontrar el árbol abarcador de costo mínimo en una gráfica. Para que esto pueda llevarse a cabo, se utilizan dos conjuntos de V, conjunto de todos los vértices, y U conjunto auxiliar iniciado con el primer vértice.

Antes de representar algún algoritmo, resulta conveniente explicar los elementos que se usarán en él:

·         V es el conjunto de vértices de G: V (1,2,……n). se usan los números enteros de 1 en adelante para identificar los vértices.

·         U es un subconjunto propio del conjunto V, siendo su valor inicial el del primer vértice.

Para muestra de implementación: U= {1}

·         L es una lista de aristas que se va formando con las aristas de menor costo que se van seleccionando. Inicialmente L está vacía L=Ø

               

Algoritmo de Kruskal

Este algoritmo es igual al Prim, permiten encontrar el árbol abarcador de menor costo de una gráfica. La construcción de un árbol abarcador mínimo  se lleva a cabo llevando la arista de menor costo y agregándola al árbol abarcador.

Espacio-Estado.

Consiste en la selección de una forma de representar los estados de un determinado problema. Las estructuras de datos que se utilizan mayormente para describir los estados son: arreglos unidimensionales, arreglos bidimensionales, listas ligadas, árboles y gráficas.

En el planteamiento del problema en espacio-estado, una solución se obtiene mediante la aplicación de operadores desde el estado inicial hasta alcanzar el estado final o meta.

Métodos de búsqueda en espacio-estado

Los métodos de búsqueda se caracterizan por el orden en que se expanden sus nodos: los dos básicos muy conocidos son:

Breadth-first o búsqueda de lo ancho: se expanden los nodos por el orden en que han sido generados

Depth-first

 o búsqueda en la profundidad: se expanden los nodos que han sido generados recientemente.

Estos métodos de búsqueda elementales son para encontrar las trayectorias, pero son exhaustivos porque expanden demasiados nodos.