Teoría de grafos/Contenido del curso

Teoría de Grafos

Un algoritmo para la ruta más corta

<nowiki>public void Floyd(int grafo[][]){

       int A[][]=new int[tamañografo][tamañografo];

       System.out.println("Grafo");
       for(int i=1;i<grafo.length;i++){
           for(int j=1;j<grafo.length;j++){
               A[i][j]=grafo[i][j].getCosto();
               System.out.print(A[i][j]+"  ");//imprime el grafo
           }
           System.out.println("");
       }
       System.out.println("");

       for(int i=1;i<grafo.length;i++){
           A[i][i]=0;//elementos de la diagonal de la matriz igualados a cero.
           }

       for(int k=1;k<grafo.length;k++){
           for(int i=1;i<grafo.length;i++){
               for(int j=1;j<grafo.length;j++){                   
                   if(A[i][k]+A[k][j]<A[i][j]){
                       A[i][j]=A[i][k]+A[k][j];//asigna los nuevos valores a la matriz que representan los caminos mas cortos entre todos los pares de vértices del grafo.
                       System.out.println("");
                   }
               }
           }
       }
       System.out.println("");

       System.out.println("Matriz de caminos mas cortos");
       for(int i=1;i<grafo.length;i++){
           for(int j=1;j<grafo.length;j++){
               System.out.print(A[i][j]+"  ");
           }
           System.out.println("");
       }
   }

Arboles

Árboles de expansión =)

Chale.

Recorridos de un árbol

'''

Árboles binarios de busqueda

¿Qué son los árboles binarios de búsqueda? Empezaremos recordando lo que son los árboles. Un árbol es una colección de nodos que puede estar vacía o no. Si no está vacía, el árbol estará formado por un nodo raíz y cero o más subárboles que están unidos a la raíz por otras tantas aristas. Para que un árbol sea binario es requisito indispensable el que el número máximo de hijos que tenga cada nodo sea 2. Por lo tanto el árbol anterior no es un árbol binario, ya que el nodo A tiene 3 hijos. Por último, un árbol será de búsqueda si todos sus nodos cumplen las siguientes condiciones: • Todos los nodos situados a su izquierda son menores que él. • Todos los nodos situados a su derecha son mayores que él. Resumiendo, se puede decir que un árbol binario de búsqueda es un árbol en el que cada nodo tiene a lo sumo dos hijos, y en el que para cada nodo todos los nodos a su izquierda son menores que él y todos los nodos a su derecha son mayores que él. Unidad 5.- Grafos y árboles Ing. Miguel Ángel Durán Jacobo 27 El siguiente árbol es un ejemplo de árbol de búsqueda: En cambio este árbol viola la condición de orden en el nodo 2, ya que un nodo a su derecha, 1, no es mayor que él. Transformación de un árbol general en un árbol binario. En esta sección estableceremos los mecanismos necesarios para convertir un árbol general en un árbol binario. Para esto, debemos seguir los pasos que se describen a continuación: 1. Enlazar los hijos de cada nodo en forma horizontal (los hermanos). 2. Enlazar en forma vertical el nodo padre con el nodo hijo que se encuentra más a la izquierda. Además, debe eliminarse el vínculo de ese padre con el resto de sus hijos. 3. Rotar el diagrama resultante aproximadamente 45 grados hacia la izquierda, y así se obtendrá el árbol binario correspondiente. Unidad 5.- Grafos y árboles Ing. Miguel Ángel Durán Jacobo 28 OPERACIONES BÁSICAS EN ÁRBOLES BINARIOS DE BÚSQUEDA Como en toda estructura de datos hay dos operaciones básicas, inserción y eliminación. Inserción: El procedimiento de inserción en un árbol binario de búsqueda es muy sencillo, únicamente hay que tener cuidado de no romper la estructura ni el orden del árbol. Cuando se inserta un nuevo nodo en el árbol hay que tener en cuenta que cada nodo no puede tener más de dos hijos, por esta razón si un nodo ya tiene 2 hijos, el nuevo nodo nunca se podrá insertar como su hijo. Con esta restricción nos aseguramos mantener la estructura del árbol, pero aún nos falta mantener el orden. Para localizar el lugar adecuado del árbol donde insertar el nuevo nodo se realizan comparaciones entre los nodos del árbol y el elemento a insertar. El primer nodo que se compara es la raíz, si el nuevo nodo es menor que la raíz, la búsqueda prosigue por el nodo izquierdo de éste. Si el nuevo nodo fuese mayor, la búsqueda seguiría por el hijo derecho de la raíz. Este procedimiento es recursivo, y su condición de parada es llegar a un nodo que no tenga hijo en la rama por la que la búsqueda debería seguir. En este caso el nuevo nodo se inserta en ese hueco, como su nuevo hijo. Vamos a verlo con un ejemplo sobre el siguiente árbol: Se quiere insertar el elemento 6. Lo primero es comparar el nuevo elemento con la raíz. Como 6 > 4, entonces la búsqueda prosigue por el lado derecho. Ahora el nuevo nodo se compara con el elemento 8. En este caso 6 < 8, por lo que hay que continuar la búsqueda por la rama izquierda. Como la rama izquierda de 8 no tiene ningún nodo, se cumple la condición de parada de la recursividad y se inserta en ese lugar el nuevo nodo. Borrar: El borrado en árboles binarios de búsqueda es otra operación bastante sencilla excepto en un caso. Vamos a ir estudiando los distintos casos. Tras realizar la búsqueda del nodo a eliminar observamos que el nodo no tiene hijos. Este es el caso más sencillo, únicamente habrá que borrar el elemento y ya habremos concluido la operación. Unidad 5.- Grafos y árboles Ing. Miguel Ángel Durán Jacobo 29 Si tras realizar la búsqueda nos encontramos con que tiene un sólo hijo. Este caso también es sencillo, para borrar el nodo deseado, hacemos una especie de puente, el padre del nodo a borrar pasa a apuntar al hijo del nodo borrado. Por último, el caso más complejo, si el nodo a borrar tiene dos hijos. En este caso se debe sustituir el nodo a borrar por mayor de los nodos menores del nodo borrado, o por el menor de los nodos mayores de dicho nodo. Una vez realizada esta sustitución se borra el nodo que sustituyó al nodo eliminado (operación sencilla ya que este nodo tendrá un hijo a lo sumo). Sobre el siguiente árbol queremos eliminar el elemento 6. Tenemos dos opciones para sustituirlo: • El menor de sus mayores: 7. • El mayor de sus menores: 4. • Vamos a sustituirlo por el 7 (por ejemplo). El árbol resultante sería el siguiente, tras eliminar también el elemento 7 de su ubicación original. Otras operaciones En los árboles de búsqueda la operación buscar es muy eficiente. El algoritmo compara el elemento a buscar con la raíz, si es menor continua la búsqueda por la rama izquierda, si es mayor continua por la izquierda. Este procedimiento se realiza recursivamente hasta que se encuentra el nodo o hasta que se llega al final del árbol. Unidad 5.- Grafos y árboles Ing. Miguel Ángel Durán Jacobo 30 Otra operación importante en el árbol es el recorrido el mismo. El recorrido se puede realizar de tres formas diferentes: • Preorden: Primero el nodo raíz, luego el subárbol izquierdo y a continuación el subárbol derecho. • In orden: Primero el subárbol izquierdo, luego la raíz y a continuación el subárbol derecho. • Postorden: Primero el subárbol izquierdo, luego el subárbol derecho y a continuación la raíz. Utilización de árboles binarios de búsqueda. Los árboles binarios de búsqueda son unas estructuras de datos muy utilizadas en la informática. Una de sus más importantes aplicaciones es el almacenamiento de información asociada con claves de búsqueda, ya que permite un almacenamiento y recuperación de la información muy eficiente. Sean T un árbol ordenado y A el conjunto de todos los vértices de T. Se define un árbol posiciónala binario B (t) sobre el conjunto de vértices A, como sigue. Si v ∈ A, entonces, el hijo izquierdo VL de v en B (t) es el primer hijo de v en T, si éste existe. El hijo derecho VR de v en B (t) es el siguiente hermano de v en T (en el orden dado de los hermanos de T), si es que este existe. Ejemplo. La figura a continuación muestra el dígrafo de un árbol etiquetado T. Se supone que cada conjunto de hermanos está ordenado de izquierda a derecha, como en el dibujo. Así, los hijos del vértice 1, es decir, los vértices 2, 3 Y 4, quedan ordenados con el vértice 2 en primer lugar, el 3, en segundo y el 4, en tercero. De manera similar, el primer hijo del vértice 5 es el vértice 11, el segundo es el vértice 12 y el tercero es el vértice 13. En la siguiente figura aparece el dígrafo del árbol posicional binario correspondiente, B(T). Para obtenerla basta trazar una arista izquierda desde cada uno de los vértices v hacia su primer hijo (si tiene hijos). Después se traza una arista derecha de cada uno de sus vértices v hacia su siguiente hermano. Así, la arista izquierda del vértice 2, va al vértice 5, ya que el vértice 5 es el primer hijo del vértice 2 en el árbol T. Además, la arista derecha del vértice 2, va hacia el vértice 3, ya que el vértice 3 es el siguiente hermano en el renglón (entre todos los hijos del vértice 1). Con frecuencia, la representación de B(T) a manera de lista doblemente enlazada se llama representación en lista enlazada de T. 1 2 3 4 5 6 7 8 9 10 11 12 13 Unidad 5.- Grafos y árboles Ing. Miguel Ángel Durán Jacobo 31

Modelo de redes y redes de petri

Un algoritmo de flujo máximo

Algoritmo de Ford-Fulkerson