1. GRAFOS 1.1.Introduccin Un grafo es un objeto matemtico que se utiliza para representar circuitos, redes, etc. Los grafos son muy utilizados en computacin, ya que permiten resolver problemas muy complejos. Aplicacin

Imaginemos que disponemos de una serie de ciudades y de carreteras que las unen. De cada ciudad saldrn varias carreteras, por lo que para ir de una ciudad a otra se podrn tomar diversos caminos. Cada carretera tendr un coste asociado (por ejemplo, la longitud de la misma). Gracias a la representacin por grafos podremos elegir el camino ms corto que conecta dos ciudades, determinar si es posible llegar de una ciudad a otra, si desde cualquier ciudad existe un camino que llegue a cualquier otra, etc. Representacin de grafos

Una caracterstica especial en los grafos es que podemos representarlos utilizando dos estructuras de datos distintas. En los algoritmos que se aplican sobre ellos adoptarn tiempos distintos dependiendo de la forma de representacin elegida. En particular, los tiempos de ejecucin variarn en funcin del nmero de vrtices y el de aristas, por lo que la utilizacin de una representacin u otra depender si el grafo es denso o disperso.

Analiza: Entre las principales aplicaciones de los grafos tenemos:Circuitos electrnicos, Tarjetas impresas, Circuitos inteRedes de transporte, Autopistas, Vuelos, Redes de ordenadores, LANs, Internet, Web, Bases de datos, Diagramas entidad/relacin, entre otrosPiensa en otras

donde se utilice la estructura:

compaeros y con tu profesora..!!!

Un grafo es un objeto matemtico que se utiliza para representar circuitos, redes, etc. Los grafos son muy utilizados en computacin, ya que permiten resolver problemas muy

Imaginemos que disponemos de una serie de ciudades y de carreteras que las unen. De cada ciudad saldrn varias carreteras, por lo que para ir de una ciudad a otra se podrn tomar

caminos. Cada carretera tendr un coste asociado (por ejemplo, la longitud de la misma). Gracias a la representacin por grafos podremos elegir el camino ms corto que conecta dos ciudades, determinar si es posible llegar de una ciudad a otra, si desde alquier ciudad existe un camino que llegue a cualquier otra, etc.

Una caracterstica especial en los grafos es que podemos representarlos utilizando dos estructuras de datos distintas. En los algoritmos que se aplican sobre ellos adoptarn tiempos distintos dependiendo de la forma de representacin elegida. En particular, los tiempos de ejecucin variarn en funcin del nmero de vrtices y el de aristas, por lo que la utilizacin de una representacin u otra depender en gran medida de si el grafo es denso o disperso.

Entre las principales aplicaciones de los grafos tenemos:Circuitos electrnicos, Tarjetas impresas, Circuitos integrados, Redes de transporte, Autopistas, Vuelos, Redes de ordenadores, LANs, Internet, Web, Bases de datos, Diagramas entidad/relacin, entre otros

aplicaciones informticas de la vida real, en

donde se utilice la estructura: Grafo, comenta con tus

compaeros y con tu profesora..!!!

Un grafo es un objeto matemtico que se utiliza para representar circuitos, redes, etc. Los grafos son muy utilizados en computacin, ya que permiten resolver problemas muy

Imaginemos que disponemos de una serie de ciudades y de carreteras que las unen. De cada ciudad saldrn varias carreteras, por lo que para ir de una ciudad a otra se podrn tomar

caminos. Cada carretera tendr un coste asociado (por ejemplo, la longitud de la misma). Gracias a la representacin por grafos podremos elegir el camino ms corto que conecta dos ciudades, determinar si es posible llegar de una ciudad a otra, si desde

Una caracterstica especial en los grafos es que podemos representarlos utilizando dos estructuras de datos distintas. En los algoritmos que se aplican sobre ellos veremos que adoptarn tiempos distintos dependiendo de la forma de representacin elegida. En particular, los tiempos de ejecucin variarn en funcin del nmero de vrtices y el de

en gran medida de

Entre las principales aplicaciones de los grafos tenemos: grados,

Redes de transporte, Autopistas, Vuelos, Redes de ordenadores, LANs, Internet, Web, Bases de datos, Diagramas

aplicaciones informticas de la vida real, en

a con tus

Para nombrar los nodos utilizaremos letras maysculas, aunque en el cdigo deberemos hacer corresponder cada nodo con un entero entre 1 y V (nmero de vrtices) de cara a la manipulacin de los mismos. Conceptos Elementales

1. Vrtice ( Vertex ): Un punto o un nodo de un grafo. 2. Arco ( Edge ): Una lnea que une un vrtice con otro vrtice del mismo grafo, en

grafos no direccionados, o una fecha que une dos vrtices del mismo grafo, en grafos direccionados.

3. Cabeza ( Head ): En grafos direccionados, es el vrtice donde llega la flecha. 4. Cola ( Tail ): En grafos direccionados, es el vrtice desde donde sale la fecha. 5. Vrtices Adjacentes ( Adjancent Edges ): Son dos vrtices que estn unidos por un

arco. 6. Arcos Incidentes ( Incident Edges ): Son los arcos que inciden en un determinado

vrtice.

Clasificacin de los Grafos:

1. Segn el tipo y cantidad de arcos

o Grafo 0o Direccionado ( Undirected Graph ): Son grafos donde los arcos unen un par de vrtices desordenados. As, el par (v1,v2) y el (v2,v1) representa el mismo arco.

o Grafo ( Graph ): Es un sinnimo de grafo no direccionado. Los grafos no

direccionados, normalmente se los llama grafos a secas.

o Grafo Completo ( Completed Graph ): Es un grafo no direccionado donde existe un arco entre cada par de vrtices cualesquiera del mismo. El nmero mximo de arcos que puede tener un grafo de n vrtices es n * ( n - 1 ) / 2.

o Grafo Direccionado ( Directed Graph ): Son grafos donde los arcos unen un par de vrtices ordenados. As, el par [v1,v2] y [v2,v1] representan arcos distintos. En el caso del arco [v1,v2], v1 es la cola del arco y v2 en la cabeza. Los arcos de un grafo direccionado se representan con flechas.

o Digrafo ( Digraph ): Es un sinnimo de grafo direccionado.

o Digrafo Completo ( Completed Digraph ): Es un grafo direccionado donde existe un arco entre cada dos vertices cualesquiera del mismo, tanto el que va desde un vrtice al otro, como el que retorna. El nmero mximo de arcos que puede tener un digrafo de n vrtices es n * ( n - 1 ).

o Multigrafo ( Multigraph ): Se aceptan ms de un arco uniendo dos vertices. En trminos formales, no son grafos.

o Subgrafo ( Subgraph ): Un subgrafo de G es un grafo G', tal que V(G') est incluido en V(G) y E(G') est incluido en E(G).

2. Segn la conectividad

o Componentes Conectados ( Connected Component ): Tiene distinto significado segn se trate de grafos direccionados o no direccionados.

o Fuertemente Conectado ( Strongly Connected ): Tiene distinto significado segn se trate de grafos direccionados o no direccionados.

Conceptos vinculados al grado

Grado de un Vrtice ( Vertex Degree ): Es el nmero de arcos que inciden sobre el vrtice.

Grado Entrante de un Vrtice ( Vertex In Degree ): Es el nmero de arcos para los cuales el vrtice es la cabeza.

Grado Saliente de un Vrtice ( Vertex Out Degree ): Es el nmero de arcos para los cuales el vrtice es la cola.

Conceptos vinculados al paso

Paso ( Path ): El paso desde un vrtice vp a un vrtice vq, en un grafo G, es una secuencia de vrtices vp, vi1, vi2, ..., vin, vq, tal que (vp,vi1), (vi1,vi2), ..., (vin,vq) son arcos en E(G). Si G es un grafo direccionado, el paso consiste de [vp,vi1], [vi1,vi2], ..., [vin,vq], arcos en E(G).

Paso Simple ( Simple Path :) Es un paso, donde todos los vrtices, excepto, posiblemente, el primero y el ltimo, son distintos.

Paso Ciclo ( Cycle Path ): Es um paso simple, donde el primero y ltimo vrtice es el mismo vrtice.

Longitud del Paso ( Path Length ): El nmero de vrtices en un paso. Representacin de grafos:

1. Matriz de adyacencias

Son matrices cuadradas de tantas filas y columnas como vrtices tenga el grafo a representar. En las celdas de la matriz se indica si existe un arco entre los vrtices que determinan la celda. Un grafo G = (V;A) se representa como G: matriz[V; V ] de bolanos. La componente G [u; v] es 1 si (u; v) 2 A; sino G[u; v] = 0.

Memoria grafos densos

Tiempo de acceso: Lista adyacentes: Lista incidentes:

2. Listas de adyacencia

Partiendo de los nodos de cada vrtice, evoluciona una lista que informa los nodos que son adyacentes del inicial.

Un grafo G = (V;A) se representa como un vector de listas de vrtices indexado por

vrtices; es decir, G: vector[V ] de V . Cada componente G[v] es una lista de los vrtices emergentes y/o incidentes de/a v 2 V.

Memoria: grafos dispersos Tiempo de acceso: O(grado(G)). Lista adyacentes: O (grado(G)). (Lista incidentes:

O(grado(G)) con listas de incidencia.)

Recorridos o exploracin de grafos

A la hora de explorar un grafo, nos encontramos con dos mtodos distintos. Ambos conducen al mismo destino (la exploracin de todos los vrtices o hasta que se encuentra uno determinado), si bien el orden en que stos son "visitados" decide radicalmente el tiempo de ejecucin de un algoritmo, como se ver posteriormente. En primer lugar, una forma sencilla de recorrer los vrtices es mediante una funcin recursiva, lo que se denomina bsqueda en profundidad. La sustitucin de la recursin (cuya base es la estructura de datos pila) por una cola nos proporciona el segundo mtodo de bsqueda o recorrido, la bsqueda en amplitud o anchura.

Suponiendo que el orden en que estn almacenados los nodos en la estructura de datos correspondiente es A-B-C-D-E-F... (el orden alfabtico), tenemos que el orden que seguira el recorrido en profundidad sera el siguiente:

A-B-E-I-F-C-G-J-K-H-D

En un recorrido en anchura el orden sera, por contra:

A-B-C-D-E-G-H-I-J-K-F

Es destacable que el nodo D es el ltimo en explorarse en la bsqueda en profundidad pese a ser adyacente al nodo de origen (el A). Esto es debido a que primero se explora la rama del nodo C, que tambin conduce al nodo D. En estos ejemplos hay que tener en cuenta que es fundamental el orden en que los nodos estn almacenados en las estructuras de datos. Si, por ejemplo, el nodo D estuviera antes que el C, en la bsqueda en profundidad se tomara primero la rama del D (con lo que el ltimo en visitarse sera el C), y en la bsqueda en anchura se explorara antes el H que el G. Recorrido y Bsqueda Primero en Profundidad

Se implementa de forma recursiva, aunque tambin puede realizarse con una pila. Se utiliza un array val para almacenar el orden en que fueron explorados los vrtices. Para ello se incrementa una variable global id (inicializada a 0) cada vez que se visita un nuevo vrtice y se almacena id en la entrada del array val correspondiente al vrtice que se est explorando. Sus pasos a seguir seran:

Visitar vrtice inicial vi Visitar vrtice adyacente a vi ... proceder as hasta encontrar uno ya visitado... Volver atrs hasta llegar a un vrtice con adyacentes sin visitar El recorrido termina cuando volviendo atrs llegamos al vrtice inicial vi y no

quedan adyacentes por recorrer

Ejemplo de recorrido primero en profundidad:

Recorrido y Bsqueda Primero en Anchura

La diferencia fundamental respecto a la bsqueda en profundidad es el cambio de estructura de datos: una cola en lugar de una pila. Sus pasos a seguir son:

Visitar vrtice inicial vi Visitar todos los vrtices adyacentes a vi Al terminar, comenzar a visitar los adyacentes a los adyacentes a vi ... proceder as hasta que no queden vrtices por visitar

Ejemplo de recorrido primero en anchura:

Implementacin de Grafos: Algoritmo Prim

PROBLEMA: a) Descripcin del problema

Dado un grafo conectado y no dirigido, su rbol abarcador mnimo es un subgrafo en forma de rbol que mantiene la conectividad del grafo y tal que la suma de los pesos de las ramas seleccionadas es mnimo. El algoritmo de Prim resuelve este problema en tiempo polinmico mediante una estrategia voraz(esto es, seleccionar en cada paso lo que ms convenga). Las aplicaciones de los rboles abarcadores mnimos son mltiples: obtencin de redes elctricas o de comunicaciones eficientes, creacin de laberintos aleatorios, solucin aproximada de problema del viajante (TSP - Traveling Salesman Problem), etc.

b) Solucin al problema

Para lograr este objetivo, hemos utilizado un algoritmo voraz, que empezar seleccionando la arista de menor coste partiendo de un nodo inicial, es decir el camino de menor recorrido desde un nodo determinado. Luego repetir dicho proceso seleccionando una nueva arista hasta que todos los nodos sean visitados. Cada uno de estas nuevas aristas ser la de menor peso entre las que no estn repetidas y, por lo tanto, permitir el acceso a un nodo nuevo. El grafo creado para probar el funcionamiento del algoritmo es de cinco nodos y est representado por una matriz de memoria esttica. Dicha matriz se inicializa en su totalidad con un valor muy grande (Integer.MaxValue) para que los pesos conocidos de antemano sean menores a dicho valor y el algoritmo funcione correctamente. El algoritmo est implementado en el cuerpo del mtodo caminoMinimo, el cul ante una invocacin en la que se especifique como parmetro real el nodo de partida, devolver un vector de enteros cuyos valores se irn modificando a medida que se obtengan nuevos caminos de coste menor a los calculados en iteraciones anteriores. Por otra parte, para asegurarse de que un nodo no se repita, se har uso del mtodo estaRepetido, que recibe como parmetro el vector donde se va almacenando la solucin y un nmero a buscar dentro de dicho vector. La llamada a dicho mtodo retorna verdadero en caso de que el nodo ya forme parte del recorrido y falso en caso contrario.

IMPLEME TACI : Para la implementacin se ha considerado, empezar con el camino de menor coste repetir

seleccionar un nuevo camino hasta que est completa una red que conecte todos los nodos. package algoritmoprim; public class Camino { // Matriz bidimensional de enteros que representa el grafo. private int grafo[][]; public Camino(int caminos[][]) { grafo = caminos; }

/** * Mtodo que recorre un vector para comprobar si se encuentra en l un valor * recibido. * @param Vector de enteros donde va almacenando la solucin. * @param i Nmero a buscar dentro del vector. * @return Devuelve true si lo encuentra. */ private boolean estaRepetido(int vector[], int i) { for (int j = 0; j < vector.length; j++) { if (vector[j] == i) { return true; } } return false; } /** * Mtodo que recorre el grafo y almacena el camino mnimo en un vector. * @param inicio Valor que representa el nodo donde comienza el recorrido. * @return El camino minimo en un vector de enteros. */ public int[] caminoMinimo(int inicio) { int numNodos = grafo.length; int minimo[] = new int[numNodos]; // Inicializar el vector de mnimos a -1 (para el caso del nodo cero). for (int i = 0; i < minimo.length; i++) { minimo[i] = -1; } int longitudCamino = 0; int menor = 0; int actual = inicio; minimo[0] = inicio; while (longitudCamino < (numNodos - 1)) { // Encontrar el camino mnimo al siguiente nodo for (int i = 0; i < numNodos; i++) { if ( (grafo[actual][i] < grafo[actual][menor]) && (!estaRepetido(minimo, i))) { // Para evitar repetir nodos. menor = i; // Ahora, el nodo siguiente es el del camino mnimo anterior. } } longitudCamino++; actual = menor; minimo[longitudCamino] = actual; } return minimo; }

/** * Mtodo main de la clase Camino donde se crea el grafo utilizado para el * ejemplo. * @param args String Parametros de la clase */ public static void main(String args[]) { // Vector de soluciones: int solucion[]; // Crear un grafo de cinco vrtices representado por una matriz: int grafo[][] = new int[5][5]; // Inicializar la matriz representando el grafo: for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { grafo[i][j] = Integer.MAX_VALUE; } } // Rellenar el grafo con las siguientes aristas con sus respectivos pesos: grafo[0][1] = 30; grafo[1][0] = 30; grafo[0][2] = 15; grafo[2][0] = 15; grafo[0][3] = 80; grafo[3][0] = 80; grafo[1][2] = 10; grafo[2][1] = 10; grafo[1][3] = 60; grafo[3][1] = 60; grafo[1][4] = 45; grafo[4][1] = 45; grafo[2][3] = 50; grafo[3][2] = 50; grafo[2][4] = 25; grafo[4][2] = 25; grafo[4][3] = 40; grafo[3][4] = 40; // Instancia de la clase camino. Camino c = new Camino(grafo); // Encontrar el camino mnimo (empieza desde el nodo 0). solucion = c.caminoMinimo(0); // Mostrar el rbol mnimo abarcador. System.out.print("\nRBOL MNIMO ABARCADOR --> Solucin: "); for (int i = 0; i < 5; i++) { // n-1 aristas entre n nodos. System.out.print(solucion[i] + " "); } } }

Tiempo de ejecucin

Para calcular la complejidad del algoritmo lo que hicimos fue obtener el Tiempo de Ejecucin (T(n)), separando las operaciones bsicas (de duracin constante) obtenindose: T(n) = 11 n + 8. Por lo tanto, eliminando las constantes sabemos que la complejidad del algoritmo es O(n).

Exposicin Nro. 6: Investigar un problema del mundo real que se pueda resolver con la

estructura grafo, adems investigar otros algoritmos para la solucin y para la

implementacin debe utilizar listas de adyacencia. No olvide realizar un programa

demostrativo.

Nota: Se tomar en cuenta el material de apoyo utilizado para la exposicin y debe

entregar una copia digital a cada grupo, adems una copia impresa y digital a la profesora

el da de la exposicin.