Modulo V

Recursividad y grafos:

 Relaciones de recurrencia:

      Una ecuación recurrente es un tipo específico de relación de recurrencia. Una relación de recurrencia para la sucesión ${\displaystyle a_{0},a_{1},a_{2},\ldots }$ es una ecuación que relaciona ${\displaystyle a_{n}\,}$ con alguno de sus predecesores ${\displaystyle a_{0},a_{1},\ldots ,a_{n-1}}$. Las condiciones iniciales para la sucesión ${\displaystyle a_{0},a_{1},\ldots }$ son valores dados en forma explícita para un número finito de términos de la sucesión.

Resolver una relación de recurrencia consiste en determinar una fórmula explícita (cerrada) para el término general ${\displaystyle a_{n}\,}$, es decir una función no recursiva de n.

Hay tres métodos para resolver relaciones recurrentes: iteración, transformada Z y un método especial que se aplica a las relaciones de recurrencia lineales homogéneas con coeficientes constantes.

Un ejemplo de una relación de recurrencia es el siguiente:

${\displaystyle x_{n+1}=rx_{n}(1-x_{n})\,}$

Algunas definiciones de recurrencia pueden tener relaciones muy complejas (caóticas), y sus comportamientos a veces son estudiados por los físicos y matemáticos en un campo conocido como análisis no lineal.

Algoritmos recursivos:

      Llamaremos algoritmos recursivos a aquellos que realizan llamadas recursivas para llegar al resultado, y algoritmos iterativos a aquellos que llegan a un resultado a través de una iteración mediante un ciclo definido o indefinido.

Todo algoritmo recursivo puede expresarse como iterativo y viceversa. Sin embargo, según las condiciones del problema a resolver podrá ser preferible utilizar la solución recursiva o la iterativa.

      Una posible implementación iterativa de la función factorial vista anteriormente sería:

def factorial(n):
    """ Precondición: n entero >=0
        Devuelve: n! """

    fact = 1
    for num in xrange(n, 1, -1):
        fact *= num
    return fact

     Se puede ver que en este caso no es necesario incluir un caso base, ya que el mismo ciclo incluye una condición de corte, pero que sí es necesario incluir un acumulador, que en el caso recursivo no era necesario. Por otro lado, si hiciéramos el seguimiento de esta función, como se hizo para la versión recursiva, veríamos que se trata de una única pila, en la cual se van modificando los valores de num y fact. Es por esto que las versiones recursivas de los algoritmos, en general, utilizan más memoria (la pila del estado de las funciones se guarda en memoria) pero suelen ser más elegantes.

Tipos de Grafos:

     La teoría de grafos (también llamada teoría de las gráficas) es un campo de estudio de las matemáticas y las ciencias de la computación, que estudia las propiedades de los grafos.

 

Grafo Dodecaedro

Grafo de Arco       

Grafo de Pez      

      Un grafo es un conjunto de puntos (vértices) en el espacio, que están conectados por un conjunto de líneas (aristas).

• Grafo simple. o simplemente grafo es aquel que acepta una sola una arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Es la definición estándar de un grafo.

• Multígrafo. o pseudografo son grafos que aceptan más de una arista entre dos vértices. Estas aristas se llaman múltiples o lazos (loops en inglés). Los grafos simples son una subclase de esta categoría de grafos. También se les llama grafos no-dirigido.

• Grafo dirigido. Son grafos en los cuales se ha añadido una orientación a las aristas, representada gráficamente por una flecha

• Grafo etiquetado. Grafos en los cuales se ha añadido un peso a las aristas (número entero generalmente) o un etiquetado a los vértices.

• Grafo aleatorio. Grafo cuyas aristas están asociadas a una probabilidad.

• Hipergrafo. Grafos en los cuales las aristas tienen más de dos extremos, es decir, las aristas son incidentes a 3 o más vértices.

• Grafo infinito. Grafos con conjunto de vértices y aristas de cardinal infinito.

Representación de grafos:

      

El grafo está representado por un arreglo de aristas, identificadas por un de pares de vértices, que son los que conecta esa arista. El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (conectado o no conectado).

Grafos eulerianos y hamiltonianos:

• Grafo eulerianos. Son de los grafos no orientados formados por un ciclo eulerianos; es decir, aquellos que pueden recorrerse completamente desde un vértice y regresar al punto de origen sin pasar dos veces por la misma arista. El nombre de este tipo de grafos proviene del matemático Leonard Euler quien abordó por primera vez el asunto de cómo debían caracterizarse los grafos para poder recorrerse de la manera deseada tras desestimar el problema de los puentes de Königsberg. El problema análogo de recorrido pero que en lugar de limitar el doble paso por las aristas lo hace impidiendo que se transite dos veces por los vértices ha dado lugar a la existencia de los grafos hamiltonianos. 

• Grafo hamiltonianos: En el campo matemático de la teoría de grafos, un camino hamiltoniano en un grafo es un camino, una sucesión de aristas adyacentes, que visita todos los vértices del grafo una sola vez. Si además el último vértice visitado es adyacente al primero, el camino es un ciclo hamiltoniano. El problema de encontrar un ciclo (o camino) hamiltoniano en un grafo arbitrario se sabe que es NP-completo. Los caminos y ciclos hamiltonianos fueron nombrados después que William Rowan Hamilton, inventor del juego de Hamilton, lanzara un juguete que involucraba encontrar un ciclo hamiltoniano en las aristas de un grafo de un dodecaedro. Hamilton resolvió este problema usando cuaterniones, pero esta solución no se generaliza a todos los grafos.

Algoritmo del camino mas corto de Dijkstra: 

     El algoritmo de Dijkstra es un algoritmo eficiente (de complejidad O (n2 ), donde “n” es el número de vértices) que sirve para encontrar el camino de coste mínimo desde un nodo origen a todos los demás nodos del grafo. Fue diseñado por el holandés Edsger Wybe Dijkstra en 1959. Este algoritmo es un típico ejemplo de algoritmo ávido, que resuelve los problemas en sucesivos pasos, seleccionando en cada paso la solución más óptima con el objeto de resolver el problema. El fundamento sobre el que se basa este algoritmo es el principio de optimizar: si el camino más corto entre los vértices “u” y “v” pasa por el vértice “w”, entonces la parte del camino que va de “w” a “v” debe ser el camino más corto entre todos los caminos que van de “w” a “v”. De esta manera, se van construyendo sucesivamente los caminos de coste mínimo desde un vértice inicial hasta cada uno de los vértices del grafo, y se utilizan los caminos conseguidos como parte de los nuevos caminos. Dicho en otras palabras: “Dado un grafo a cuyos arcos se han asociado una serie de pesos, se define el camino de coste mínimo de un vértice “u” a otro “v”, como el camino donde la suma de los pesos de los arcos que lo forman es la más baja entre las de todos los caminos posibles de “u” a “v”.” El algoritmo de Dijkstra en cada paso selecciona un vértice “v” cuya distancia es desconocida, entre los que tiene la distancia más corta al vértice origen “s”, entonces el camino más corto de “s” a “v” ya es conocido y marca el vértice “v” como ya conocido. Así, sucesivamente se van marcando nuevos vértices hasta que estén todos marcados; en ese momento es conocida la distancia mínima del origen “s” al resto de los vértices. Entre las condiciones más importantes que deben considerarse para aplicar el algoritmo están: Las aristas deben tener un peso no negativo. El grafo debe ser dirigido y por supuesto ponderado. Una posible aplicación de este algoritmo se presenta cuando se desea encontrar la ruta más corta entre dos ciudades; cada vértice representa una ciudad y las aristas representan la duración de los vuelos.

Arboles:

 

      En ciencias de la computación y en informática, un árbol es un tipo abstracto de datos (TAD) ampliamente usado que imita la estructura jerárquica de un árbol, con un valor en la raíz y subárboles con un nodo padre, representado como un conjunto de nodos enlazados. Una estructura de datos de árbol se puede definir de forma recursiva (localmente) como una colección de nodos (a partir de un nodo raíz), donde cada nodo es una estructura de datos con un valor, junto con una lista de referencias a los nodos (los hijos) , con la condición de que ninguna referencia esté duplicada ni que ningún nodo apunte a la raíz. Alternativamente, un árbol se puede definir de manera abstracta en su conjunto como un árbol ordenado, con un valor asignado a cada nodo. Ambas perspectivas son útiles: mientras que un árbol puede ser analizado matemáticamente, realmente es representado como una estructura de datos en la que se trabaja con cada nodo por separado (en lugar de como una lista de nodos y una lista de adyacencia entre nodos, como un grafo). Mirando a un árbol como conjunto, se puede hablar de el nodo padre de un nodo dado, pero en general se habla de una estructura de datos de un nodo dado que sólo contiene la lista de sus hijos sin referencia a su padre (si lo hay).

Arboles recubridores minimales: algoritmos de Kruskal y Prim

      

     Un árbol recubridor es un subgrafo que tiene que ser un árbol y contener todos los vértices del grafo inicial. Cada arista tiene asignado un peso proporcional entre ellos, que es un número representativo de algún objeto, distancia, etc.; y se usa para asignar un peso total al árbol recubridor mínimo computando la suma de todos los pesos de las aristas del árbol en cuestión. Un árbol recubridor mínimo o un árbol de expansión mínimo es un árbol recubridor que pesa menos o igual que todos los otros árboles recubridores. Todo grafo tiene un bosque recubridor mínimo.

      El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo. Si el grafo no es conexo, entonces busca un bosque expandido mínimo (un árbol expandido mínimo para cada componente conexa). Este algoritmo toma su nombre de Joseph Kruskal, quien lo publicó por primera vez en 1956​. Otros algoritmos que sirven para hallar el árbol de expansión mínima o árbol recubridor mínimo son el algoritmo de Prim, el algoritmo del borrador inverso y el algoritmo de Boruvka.

     El Algoritmo de Prim consiste en incrementar el tamaño de un árbol, empezando por un vértice inicial al cual se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima. Esto quiere decir que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya pertenecen al árbol. Por tanto, el árbol recubridor mínimo estará completamente construido cuando no queden más vértices por agregar. Los requisitos para proceder con el Algoritmo de Prim son:

• Grafo conexo
• Tener todos los arcos etiquetados

La idea fundamental consiste en añadir en cada paso una arista de peso mínimo a un árbol previamente construido. Para verlo de un modo más explícito, se definen los siguientes pasos:

1. Se elige un vértice U de G y se considera el árbol S={U}.
2. Se considera la arista e de mínimo peso que une un vértice de S y un vértice que no es de S, y se hace S=S+e .
3. Si el número de aristas de T es n-1, el algoritmo termina. En caso contrario, volveríamos al paso 2.