Proyecto Final Matematicas DiscretasAlumno(a):Estela Solano Hermida

Universidad del Papaloapan

Materia: Matematicas Discretas

Alumno(a): Estela Solano Hermida

Profr:M.C Pablo Rodrigo Díaz Monterrosas

Carrera: Ingenieria en Computación

Semestre: 3°

9 de Febrero de 2011

Proyecto Final Matematicas DiscretasAlumno(a):Estela Solano Hermida

CONTENIDO

4. OPTIMIZACION EN GRAFOS4.1 Caminos mas cortos de un grafo4.2 Flujos de grafos4.3 Teoria de emparejamiento4.4 Arboles ponderados y árbles de expansion minima

6.FUNCIONES GENERATRICES 6.1 Ejemplos introductorios 6.2 Definiciones y técnicas de calculo 6.3 Particiones de enteros 6.4 La ecuacion generatriz exponencial 6.5 El operador suma

7.RELACION DE RECURRENCIA 7.1 La relacion de recurrencia de primer orden

7.2 La relacion de recurrencia lineal homogenea de segundo xxxxxorden con coeficientes constantes 7.3 La relacion de concurrencia no homogenea 7.4 El metodo de las funciones generatrices 7.5 Algoritmos de divide y venceras

Proyecto Final Matematicas DiscretasAlumno(a):Estela Solano Hermida

4. OPTIMIZACION EN GRAFOS

4.1 Caminos mas cortos de un grafoCamino mas corto: entre dos vértices v y w en una red, es un camino simple de v a w tal que no haya camino mas corto que este entre esos vértices.

Para hallar el caminos mas corto usaremos el Algoritmo de Dijsktra. Busca los caminos mas cortos a partir de una fuente v dada en grafos con pesos no-negativos Prim: construcción incremental, incorporando cada vez un vértice relacionado con el AGM por un arco de tamaño mínimo Aquí, mismo principio: 1. incorporar la fuente v 2. poner en el árbol un arco conectado al árbol y hacia un vértice no presente en el árbol y dando un camino mas corto de la fuente hacia este nodo 3. si no has incorporado todos los vértices, ir al 2

Ejemplos:

Proyecto Final Matematicas DiscretasAlumno(a):Estela Solano Hermida

Algoritmo de Dijsktra, y como Funciona:

1. Descripción: El algoritmo de Dijkstra, también llamado algoritmo de caminos más cortos, es un algoritmo para la determinación del camino más corto dado un vértice origen.

2. Estructura de datos utilizada: Este algoritmo utiliza un tipo de estructura de colas llamado cola de prioridad. Una cola de prioridad es una estructura de datos en la que los elementos se atienden en el orden indicado por una prioridad asociada a cada uno.

3. Como funciona el Algoritmo?• Seleccionamos el nodo no visitado con menor distancia acumulada( al

iniciar, este será siempre el nodo de inicio).• Sumamos la distancia acumulada en dicho nodo con la distancia de las aristas a los nodos a los

que podemos acceder. Comparamos la nueva distancia con la que teníamos acumulada en el nodo destino (en caso de tener ya alguna) y nos quedamos con la menor.

• Marcamos el nodo actual como visitado y volvemos al paso 1.

Proyecto Final Matematicas DiscretasAlumno(a):Estela Solano Hermida

Algoritmo:

4.2 Flujos de grafosUna red de flujo es un grafo dirigido G = (V,E) en donde cada arco tiene una capacidad no negativa

Se distinguen dos vértices: la fuente s y el destino t.

Se supone que cada vértice se encuentra en alguna ruta de s a t.

Un flujo en G es una función tal que

• Restricción de capacidad: • Simetría: • Conservación:

Proyecto Final Matematicas DiscretasAlumno(a):Estela Solano Hermida

El valor del flujo es

El problema del flujo máximo trata de maximizar este flujo.

Algoritmo de flujo máximo

Tenemos el conocido problema de flujo máximo o maximal: ¿cuál es la tasa mayor a la cual el material puede ser transportado de la fuente al sumidero sin violar ninguna restricción de capacidad?

En otras palabras, el problema consiste en determinar la máxima capacidad de flujo que puede ingresar a través de la fuente y salir por el nodo de destino.

El procedimiento para obtener el flujo máximo de una red, consiste en seleccionar repetidas veces cualquier trayectoria de la fuente al destino y asignar el flujo máximo posible en esa trayectoria.

:'''Capacidad residual''': es la capacidad adicional de flujo que un arco puede llevar:

:<math>c_{f}(u,v)= c(u,v) - f(u,v) \,</math>

• Dada una red de flujo máximo, plantee la red residual asociada.

• Encuentre la [[trayectoria]] de la [[fuente]] al destino con capacidad de [[flujo]] estrictamente positivo (si no existe alguno, es por que se ha encontrado el óptimo).

• Examine estas [[trayectoria]]s para encontrar la rama o arco con la menor capacidad de flujo restante e incremente en éste valor, la capacidad del flujo en sentido contrario.

• Determine todas las trayectorias estrictamente positivas, hasta que no se permita flujo del nodo a un nodo destino.

Podemos, mediante el [[Algoritmo de Ford-Fulkerson]], encontrar el flujo máximo de una red.

Para hallar la distancia más corta entre dos puntos en una red.

4.3 Teoria de emparejamientoUn emparejamiento en un grafo G=(V,A) es un subconjunto M A tal que dos aristas cualesquiera de⊂ M no tienen un extremo común. Un emparejamiento es máximo si no hay otro de cardinal mayor. Un emparejamiento es maximal si no está contenido en otro de cardinal mayor. Un emparejamiento M es perfecto si todos los vértices de G son extremo de alguna arista de M.

Proyecto Final Matematicas DiscretasAlumno(a):Estela Solano Hermida

Caminos y emparejamientos

Dado un emparejamiento M, los extremos de las aristas de M se llaman vértices saturados por M. Un camino de G se dice alternado para M o M-alternado si sus aristas alternativamente están o no están en M.

4.4 Arboles ponderados y árboles de expansion minima

Definición. Se llama árbol ponderado a un árbol en el que cada arista tiene asignado un número llamado peso.

Definición. Sea G un grafo ponderado. Un árbol generador minimal (AGM) de G es un árbol ponderado que es generador de G, y que tiene peso minimo.

Proyecto Final Matematicas DiscretasAlumno(a):Estela Solano Hermida

Árboles de expansión mínimos.

Definición. Un grafo ponderado o grafo con pesos es un grafo G(V, E), en el que a cada arista se le asigna un valor real no negativo o peso. Sobre el conjunto de aristas se introduce una función peso. El peso de un subgrafo de un grafo ponderado es la suma de los pesos de todas sus aristas. W: E --> R^+:

Ejemplo 3.3.2. Dado el grafo con pesos:

Proyecto Final Matematicas DiscretasAlumno(a):Estela Solano Hermida

BOSQUE DE EXPANSIÓN

Un bosque de expansión es un tipo de subgrafo que generaliza el concepto de árbol de expansión. Hay dos definiciones de uso común:

• Según la primera, un bosque de expansión es un subgrafo que consiste en un árbol de expansión en cada componente conexo del grafo (equivalentemente, es un subgrafo libre de ciclos maximal). Esta definición es frecuente en informática y optimización, así como la que se emplea habitualmente al tratar los bosques mínimos de expansión, la generalización a subgrafos disconexos de árboles de expansión minimales.

• Otra definición, empleada en teoría de grafos, es la de un bosque de expansión es un subgrafo que es a la vez bosque (es decir, no contiene ciclos) y de expansión (es decir, incluye a todos los vértices).

6.FUNCIONES GENERATRICES 6.1 Ejemplos introductorios

La función generatriz es una transformación que permite condensar todos los valores de una secuencia {a0 , a1 , ..., an , ...} en una unica función

y dado a(z), escribimos su an correspondiente como an = [z n ]a(z). Esta transformación permite convertir ecuaciones de recurrencia en ecuaciones acerca de la función a(z), que pueden ser más fáciles de resolver que la recurrencia original.

Proyecto Final Matematicas DiscretasAlumno(a):Estela Solano Hermida

Proyecto Final Matematicas DiscretasAlumno(a):Estela Solano Hermida

6.2 Definiciones y técnicas de calculo

Proyecto Final Matematicas DiscretasAlumno(a):Estela Solano Hermida

Proyecto Final Matematicas DiscretasAlumno(a):Estela Solano Hermida

6.3 Particiones de enteros

Proyecto Final Matematicas DiscretasAlumno(a):Estela Solano Hermida

6.4 La ecuacion generatriz exponencial

Proyecto Final Matematicas DiscretasAlumno(a):Estela Solano Hermida

6.5 El operador suma

Proyecto Final Matematicas DiscretasAlumno(a):Estela Solano Hermida

Proyecto Final Matematicas DiscretasAlumno(a):Estela Solano Hermida

7.RELACION DE RECURRENCIA

7.1 La relacion de recurrencia de primer orden

Una relación de recurrencia para una sucesión a0 , a1 , a2 ,...., an ,... es una expresión que relacionan con uno o más términos precedentes a0 , a1 , a2 ,...., an-1 , para cualquier n entero mayor o igual que un entero inicial k. Los valores de los primeros términos necesarios para empezar a calcular se llaman condiciones iniciales. Si an = c1 an-1 +c2 an-2 + ... + cm an-m + g(n) donde c1 ,... , cm son constantes decimos que la relación de recurrencia es lineal de coeficientes constantes. Si además g(n)=0 diremos relación lineal homogénea. • Resolución de relaciones de recurrencia lineales de primer orden. • Resolución de relaciones de recurrencia lineales y homogéneas de segundo orden: (*) a n = c1 a n−1 + c2 a n− 2

7.2 La relacion de recurrencia lineal homogenea de segundo orden con coeficientes constantes

Relación homogónea de orden 2: Cn an + Cn−1 an−1 + Cn−2 an−2 = 0, n ≥ 2. Con base en nuestro trabajo con las relaciones recursivas geométricas, buscamos solución de la forma an = Cr n , donde c = 0 y r = 0. Si sustituimos an = cr n en la ecuación, obtenemos: Cn r n + Cn−1 r n−1 + Cn−2 r n−2 = 0. Realizando las factorizaciones adecuadas y considerando que c, r = 0, esto se convierte en Cn r 2 + Cn−1 r + Cn−2 = 0, que es una ecuación cuadrática llamada la ecuación característica.

CASO A: Raices distintasResolveremos la relación de recurrencia an + an−1 − 6an−2 = 0 donde n ≥ 2 y a0 = 1, a1 = 2. Sustituimos an = cr n . 1 Obtenemos la ecuación caracterıstica y hallamos sus soluciones. 2 Verificamos que ambas soluciones sean linealmente independientes. 3 Escribimos la solución general como an = c1 r1 + c2 r2 . 4 Usando las condiciones iniciales a0 y a1 hallamos los valores de 5 c1 , c2 .

Proyecto Final Matematicas DiscretasAlumno(a):Estela Solano Hermida

CASO B: Raices complejasResolveremos la relación de recurrencia an = 2(an−1 − an−2 ), donde n ≥ 2 y a0 = 1 y a1 = 2. Sustituimos an = cr n . 1 Obtenemos la ecuación caracterıstica y hallamos sus soluciones. 2 Escribimos la solución general como an = c1 r1 + c2 r2 . 3 Escribimos ambas soluciones en la forma polar. 4 reescribimos la solución general usando coeficientes k1 = c1 + c2 y k2 = (c1 − c2 )i 5 Usando las condiciones iniciales a0 y a1 hallamos los valores de 6 k1 , k2 .

CASO B: Raices reales repetidasResolveremos la relación de recurrencia: an+2 = 4an+1 − 4an , donde n ≥ 0 y a0 = 1, a1 = 3. 1 Sustituimos an = cr n . 2 Obtenemos la ecuación caracterıstica y hallamos sus soluciones. 3 Dado que no tenemos dos soluciones linealmente independientes, probamos con la solución an = nr 4 Escribimos la solución general como an = c1 r n + c2 nr n . 5 Usando las condiciones iniciales a0 y a1 hallamos los valores de c1 , c2 . EJEMPLO:

Proyecto Final Matematicas DiscretasAlumno(a):Estela Solano Hermida

7.3 La relacion de concurrencia no homogeneaSi an = c1 an−1 +c2 an−2 · · ·+cm an−m +g(n), para n ≥ m, se dice que la relaci n de recurrencia es lineal no homogónea de orden m. A la relación an = c1 an−1 +c2 an−2 · · ·+cm an−m , resultante de eliminar g(n) se le llama relación de recurrencia lineal homogénea asociada.

Proposición 3.3.1.

Si T y S son soluciones de la relación de recurrencia lineal no homogónea, entonces S − T es solución de la relación de recurrencia lineal homogénea asociada. Observación 3.3.2. Pasos para resolver una relación de recurrencia lineal no homogénea: • Se obtiene la solución general de la ecuación homogénea asociada. • Se obtiene una soluci n particular de la relación de recurrencia no homogénea. • La suma de la solución general de la ecuación lineal homogénea asociada y de una solución particular de la relación de recurrencia lineal no homogénea nos da la solución general de la relación de recurrencia lineal no homogénea. • La solución especıfica se obtiene a partir de las condiciones iniciales.

Observación 3.3.3. Una solución particular (xn ) de la relación de recurrencia lineal no ho- mogénea se puede encontrar en algunos casos especiales. • Si g(n) = Pk (n) (polinomio de grado k), entonces xn = Qk (n) (polinomio de grado k), excepto si 1 es raíz caracterí stica con multiplicidad s, en cuyo caso xn = ns Qk (n). • Si g(n) = pan , p R, entonces xn = qan , q R, excepto si a es raíz caracterıstica con ∈ ∈ multiplicidad s, en cuyo caso xn = qns an . • Si g(n) = an Pk (n), entonces xn = an Qk (n), excepto si a es raíz caracterıstica con multiplicidad s, en cuyo caso xn = ns an Qk (n).

7.4 El metodo de las funciones generatrices

Sea la solución a un cierto problema una secuencia de números, , que se desean determinar. Una forma de proceder es buscar una fórmula para el término enésimo. Pero esto no es siempre posible o fácil de hacer. Por ejemplo, no podemos dar una fórmula para el enésimo número primo. La funciones generatrices nos entregan otra forma de proceder. Si bien dar una fórmula para los miembros de la secuencia puede ser complicado, a menudo es relativamente fácil dar una formula simple para la suma de una serie de potencias, cuyos coeficientes corresponden a la secuencia que andamos buscando.

Por definición, la función generatriz de una secuencia es una serie formal

La serie se define en el sentido algebraíco, no analítico. Formalmente hablando, agregamos al conjunto de números reales la indeterminada , cuya naturaleza no es relevante para la construcción. El nuevo término y los números pueden ser sumados y multiplicados, y ambas operaciones son postuladas para ser conmutativas y la suma es también distributiva con respecto a la multiplicación. Este conjunto

Proyecto Final Matematicas DiscretasAlumno(a):Estela Solano Hermida

expandido de números reales pasa a ser un anillo. En este caso se tendrá inverso para la serie formal,

siempre y cuando el término constante de la serie sea distinto de 0

Ejemplo 4.2.5

Como , podemos establecer que

En términos analíticos, es una variable tomando valores en los números reales o complejos, y la identidad se mantiene cuando la serie de la derecha es convergente, i.e., cuando . Sin embargo, en la teoría formal no nos interesa la pregunta de convergencia. En ese sentido, el término función generatriz no es tan consistente con la operación de sustituir un número por con el fin de establecer el valor de la serie en ese punto, eso no es legal. Las funciones generatrices frecuentemente aparecen en el ámbito de análisis de algoritmos cuando el coeficiente representa el número de estructuras de un tamaño

dado. Pero, muchas veces estamos normalmente interesados no sólo en contar estructuras de un tamaño dado, sino que también en conocer valores de varios parámetros relacionados con las estructuras. Usamos funciones generatrices bivariadas para este propósito. Estas son funciones de dos variables que representan secuencias doblemente indexadas: un índice para el tamaño del problema y una para los valores de los parámetros siendo analizados. Las funciones generatrices bivariadas nos permiten capturar ambos índices con sólo una función generatriz de dos variables.

7.5 Algoritmos de divide y venceras

Diseño e implementación

La resolución de un problema mediante esta técnica consta fundamentalmente de los siguientes pasos:

1. En primer lugar ha de plantearse el problema de forma que pueda ser descompuesto en k subproblemas del mismo tipo, pero de menor tamaño. Es decir, si el tamaño de la entrada es n, hemos de conseguir dividir el problema en k subproblemas (donde 1 ≤ k ≤ n), cada uno con una entrada de tamaño nk y donde 0 ≤ nk < n. A esta tarea se le conoce como división.

2. En segundo lugar han de resolverse independientemente todos los subproblemas, bien directamente si son elementales o bien de forma recursiva. El hecho de que el tamaño de los subproblemas sea estrictamente menor que el tamaño original del problema nos garantiza la convergencia hacia los casos elementales, también denominados casos base.

3. Por último, combinar las soluciones obtenidas en el paso anterior para construir la solución del problema original.

Los algoritmos divide y vencerás (o divide and conquer, en inglés), se diseñan como procedimientos generalmente recursivos.

Proyecto Final Matematicas DiscretasAlumno(a):Estela Solano Hermida

Por el hecho de usar un diseño recursivo, los algoritmos diseñados mediante la técnica de Divide y Vencerás van a heredar las ventajas e inconvenientes que la recursión plantea:

• Por un lado el diseño que se obtiene suele ser simple, claro, robusto y elegante, lo que da lugar a una mayor legibilidad y facilidad de depuración y mantenimiento del código obtenido.

• Por contra, los diseños recursivos conllevan normalmente un mayor tiempo de ejecución que los iterativos, además de la complejidad espacial que puede representar el uso de la pila de recursión.

Sin embargo, este tipo de algoritmos también se pueden implementar como un algoritmo no recursivo que almacene las soluciones parciales en una estructura de datos explícita, como puede ser una pila, cola, o cola de prioridad. Esta aproximación da mayor libertad al diseñador, de forma que se pueda escoger qué subproblema es el que se va a resolver a continuación, lo que puede ser importante en el caso de usar técnicas como Ramificación y acotación o de optimización.

Proyecto Final Matematicas DiscretasAlumno(a):Estela Solano Hermida

BIBLIOGRAFIAOptimizacion de Grafos

http://polimedia.upv.es/visor/?id=88e48587-257c-f146-85fd-ff48ddc9bc9a

http://es.wikipedia.org/wiki/Red_de_flujo

http://www.dma.fi.upm.es/grafos/EmpFlujos03.PDF

http://es.wikipedia.org/wiki/%C3%81rbol_de_expansi%C3%B3n

Funciones Generatrices https://www.ucursos.cl/ingenieria/2007/1/CC53A/1/material_docente/bajar?

id_material=120247 http://www610.megaupload.com:800/files/2541d5ce26bf450771bdade7e40dad65/M.

%20discretas%203ra%20ed%20es.part2.rar

http://books.google.com.mx/books? id=lHqqjoR0b1YC&pg=PA433&lpg=PA433&dq=ejemplos+introductorios+de+funciones+generatrices+informacion&source=bl&ots=gQt-kzOgXk&sig=yO5z-7b9tdLKcO4GEmm4dRtIynE&hl=es&ei=LKZJTaSsNYiisQPasKS0Cg&sa=X&oi=book_result&ct=result&resnum=1&ved=0CBEQ6AEwAA#v=onepage&q&f=false

Relaciones de Recurrencia http://www.dma.fi.upm.es/ctorres/matematicadiscreta/curso0203/3rec-t0203.pdf

https://www.itescam.edu.mx/principal/sylabus/fpdb/recursos/r58767.PDF

http://www.dma.fi.upm.es/docencia/cursosanteriores/0405/primerciclo/matdiscreta/15M/T eoriaRecurrencia.pdf

http://www.dim.uchile.cl/~gespinoz/principal/node31.html

http://es.wikipedia.org/wiki/Algoritmo_divide_y_vencer%C3%A1s