Equipo 2 «FUNCIONES GENERATRICES «

****6.FUNCIONES GENERATRICES****

La función generatriz es una transformación que permite condensar todos los valores de una secuencia  en una función

Y dado a(z), escribimos  su  correspondiente como .

Esta transformación permite convertir ecuaciones de recurrencia en ecuaciones acerca de la función a (z), que pueden ser mas fáciles de resolver que la recurrencia original. Una vez obtenido el resultado, se debe anti transformar la función para recuperar los valores originales . No lo veremos en el curso, pero también es sumamente útil para contar estructuras combinatorias, problema que aparece frecuentemente en el análisis de algoritmos.

En la Tabla 1 se presentan las funciones generatrices asociadas a varias secuencias conocidas:

En la Tabla 2 se muestran las transformaciones más importantes. Por ejemplo, podemos usar la última para derivar la función generatriz de:

Veamos un ejemplo de transformar una recurrencia en función generatriz. Los números de fibonacci cumplen la propiedad

A un no podemos aplicar funciones generatrices porque la ecuación no es válida para todo n, por ejemplo no está definida para 0 y 1. Lo que haremos será reexpresarla como

Ahora tomamos función generatriz de ambos lados 

multiplicando por  de ambos lados tenemos

Con lo cual termina la primera etapa de la solución. Hemos mostrado cómo convertimos una recurrencia en una ecuación normal acerca de la función generatriz. Cómo recuperar ahora la secuencia.En este caso, notemos que F(Z)se puede expandir en fracciones parciales

Solución:

6.2Definiciones y técnicas de cálculo

Definición:

6.3Particiones de enteros

Ahora nos interesa contar de cuantas maneras se puede escribir un cierto entero positivo n como suma de enteros positivos, donde el orden de los sumandos es ahora irrelevante. Cada una de estas formas será lo que llamaremos una partición de n; y cada uno de los sumandos, una parte. Por ejemplo,

5 = 1 + 1 + 1 + 1 + 1

5 = 1 + 1 + 1 + 2

5 = 1 + 2 + 2

5 = 1 + 1 + 3

5 = 2+3

5 = 1+4

5 = 5

Obsérvese que, por ejemplo, 5 = 2 + 3 y 5 = 3 + 2 representan la misma partición. Por comodidad, se suelen escribir los sumandos de menor a mayor; a veces incluso se abrevia de la siguiente forma:

11 = 2 +2+2+ 2 + 3 =

Donde   nos recuerda que hay que sumar cuatro doses.

Démosle nombre a las cantidades de interés: primero,

p(n) = #{ particiones de n} .

En nuestro análisis consideraremos unas particiones especiales, las particiones de n que tienen exactamente k partes; al número de ellas lo llamaremos pk(n). Obviamente, se cumple que

En general, cuando queramos contar el número de particiones de n que cumplan una determinada propiedad, escribiremos:

p(n | la partición cumple cierta propiedad)

Asi, por ejemplo, los pk(n) que acabamos de introducir corresponden a

pk(n) = p(n | el numero de partes es exactamente k) .

Contar el numero de particiones de un entero n, o el numero de particiones con ciertas características es un problema difícil; las funciones generatrices son la manera habitual y más eficaz de tratar el problema .Para esta primera aproximación al problema nos limitaremos a utilizar argumentos de tipo combinatorio (a veces, muy ingeniosos).

Las particiones de un entero n nos recuerdan a lo que llamábamos composiciones de n. Se diferencian de ellas en que ahora el orden de presentación de los sumandos no es relevante, pero quizás nos puedan ser ´útiles. Veamos el ejemplo de n = 5:

 

 

Particiones de 5                                 Composiciones de 5

Pero no parece sencillo encontrar el diccionario entre estos dos problemas: el numero de composiciones que corresponde a cada partición depende (y no queda claro de qué manera) de la partición en sí.

Estimaciones de tamaño

Una vez que ha fracasado nuestro primer acercamiento a la cuestión, nos ponemos menos ambiciosos y nos planteamos estimar el orden de magnitud de, por ejemplo, los números pk(n).

Obsérvese, antes de nada, que p(n) crece con n: a toda partición de n − 1 se le puede añadir un 1 para obtener una de n (así que de n al menos hay tantas particiones como de n−1). Y lo mismo ocurre para pk(n) (si fijamos k) porque, dada una partición de n, digamos n = a1 + · · · + ak , entonces, por ejemplo, ( +1)+· · ·+ak  es una partición de n+1 (con el mismo número de sumandos). Obsérvese que este procedimiento no siempre crea el mismo número de nuevas particiones. Por ejemplo, a partir de 4 = 2 + 2 obtendríamos solo 5 = 2 + 3, mientras que a partir de 4 = 1 + 3 podríamos obtener 5 = 2 + 3 y también 5 = 1 + 4.

Recuperemos el acercamiento al problema en términos de las composiciones de n. Desde luego, fijados n y el número de sumandos k, al menos hay tantas composiciones como particiones (recordemos que en las composiciones cuenta el orden). Por ejemplo, para n = 3 y k = 2, hay una partición (1 + 2) y dos composiciones (1 + 2 y 2 + 1).

En general,

De la igualdad de las funciones generatrices, tenemos que

integrantes.

• Sandy Guadalupe Salinas Antonio.
• Estefania Cano Martinez.
• David Hernandez Trinidad.
• Lenin Lopez Martinez.

Equipo 3

6. FUNCIONES GENERATRICES

Elaborado por: Elsa Cortes Rito

6.2 Definición y técnicas de cálculo

Se llama función generatriz de la sucesión A = (a₀, a₁, a₂, …, a_k, …) a la serie de potencias A(z)= a₀ + a₁z+ a₂ z² + …+ a_k z^k + …

 

 

 

Ejemplo:

1.- ¿De cuántas formas se pueden asignar dos docenas de robots idénticos a 4 líneas de montaje? de modo que:

 a) al menos 3 robots se asignen a cada línea.

 

Referencias:

GRIMALDI, Ralph P. “Matemáticas discreta y combinatoria”.

Tercera edición. Editorial Addison-Wesley Iberoamericana

http://ocw.upm.es/matematica-aplicada/matematica-discreta/contenidos/material-de-clase/tema-4

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

 

Elaborado por: Ana patricia Matus Vicente

6.3 PARTICIONES DE ENTEROS

En el estudio de la teoría de números nos enfrentamos al problema de descomponer un entero positivo n en sumandos positivos n  y buscar el número de estas descomposiciones,  sin tener  en cuenta el orden. Este número se denota como p(n). Por ejemplo,

p(1)=1:    1

p(2)=2:    2= 1+1

p(3)= 3:    3= 2+1= 1+1+1

p(4)=5:     4= 3+1= 2+2= 2+1+1= 1+1+1+1

p(5)=7:     5= 4+1= 3+2= 3+1+1=  2+2+1= 2+1+1=  1+1+1+1+1.

Como se puede observar en la parte de arriba se muestra p(4)=5, donde: 5 es el numero de particiones que tiene el 4, enseguida se muestra cuales son dichas particiones.

 

 

7. RELACIÓN DE RECURRENCIA

 

Elaborado por:  Geremías Sánchez Martínez.

7.1 la Relación de recurrencia de primer orden.

Para una función numérica (a_0, a₁, a₂,… a_r,…), una ecuación que relaciona a_r, para cualquier r, a una o mas de las a_i, i < r, es llamada una relación de recurrencia, que también se conoce como una ecuación de diferencias. Con la relación de recurrencia podemos llevar a cabo el calculo paso por paso para determinar a_r a partir de a_r-1, a_r-2,…, para determinar a_r+1  a partir de a_r, a_{r – 1,}…, y asi sucesivamente, siempre que el valor en uno o mas puntos permita iniciar el calculo. Los valores obtenidos por la función se denominan “valores de frontera”. En el primer caso, la condición frontera es a₀ = 1 y a₁ = 1. De esta forma se puede afirmar que una función numérica puede ser descrita mediante una relación de recurrencia junto a un conjunto apropiado de condiciones de frontera. La función numérica también es conocida como la solución de la relación de recurrencia.

La relación de recurrencia lineal general de primer orden con coeficientes constantes tiene la forma:

A_n+1 + ca_n = f(n),   n>=0,

Donde c es una constante y f(n) es una relación en el conjunto N de los enteros no negativos.

La función a= (3^0, 3¹, 3²,…, 3^r,…) puede expresarse mediante una expresión general para a_r = 3^r   r>=0.

De la primera expresión podemos observar que el valor de a_r  es  el triple del valor de a_r-1, para todo r, conociendo el valor de a_r-1podemos calcular el valor de a_r. El valor de a_r-1 puede ser calculado como el triple de a_r-2, el cual otra vez es el triple de a_r-3. Al final, necesitamos el valor de a₀, el cual sabemos que es 1. Por ello la relación a_r = 3ª_r-1 también especifica por completo la función numérica a.

A continuación se muestran algunos ejemplos en donde se utilizan las relaciones de recurrencia.

Ejemplo 1.- Determine si la secuencia { a_n } es una solución de recurrencia  a_n=2a_n-1 – a_n-2 para n = 2, 3,4,…., donde a_n = 3n para cada entero n no negativo.

Resultado.

• Suponga que a_n=3n para cada entero n no negativo.
• Entonces para n>=2 vemos que:

 

2ª_n-1 – a_n-2 = 2(3(n-1)) – (3(n-2)) = 6n-6-3n+6 = 3n = a_n.

 

Por lo tanto { a_n }, donde a_n=3n, es una solución de la relación de recurrencia.

 

Ejemplo 2.- Determine si la secuencia { a_n } es una solución de la relación de recurrencia a_n=2ª_n-1 – a_n-2 para n=2, 3,4,…, donde a_n =2ⁿpara cada entero n no negativo.

Resultado.

• Suponga que a_n = 2ⁿ para cada entero n no negativo.
• Entonces para n>=2 vemos que:

2ª_n-1 – a_n-2 = 2(2^n-1) – (2^n-2) = 2(2¹) – (2⁰) = 3 ≠ a_n = 4.

Por lo tanto, { a_n }, donde a_n = 2ⁿ , no es una solución de la relación de recurrencia.

http://eisc.univalle.edu.co/cursos/web/material/750084M/1/DiscII_3.pdf

http://www.cuvalles.udg.mx/academiainformatica/pags/cursos/segundo/MATEMATICAS%20DISCRETAS%20CAPITULO%203.pdf

 

Elaborado por: Elsa Cortes Rito

7.2 La relación de recurrencia lineal  homogénea de 2° orden con coeficientes  constantes

 

La relación de recurrencia  lineal  general de segundo orden  con coeficientes  constantes  se define como:

 

 

Ejemplo:

Resolver la relación de recurrencia

Solución:

 

 

Presenta: Geremias Sánchez Martínez.

 7.3 La Relación de recurrencia no homogénea.

Consideremos la relación lineal no homogénea de orden k (k € Z⁺),

a_n + c₁ a_n-1 + …… + c_k a_n-k = f(n)     n>=k

Donde c₁,c₂,…, c_k son constantes reales, c_k ≠ 0.

La solución general de esta relación re recurrencia esta dada por

a_n = a_n^(h) + a_n^(p) .

Donde a_n^(h) es la solución general de la relación de recurrencia homogénea asociada

a_n + c₁ a_n-1 + …… + c_k a_n-k = 0

y a_n^(p)es una solución particular de la relación no homogénea

a_n + c₁ a_n-1 + …… + c_k a_n-k = f(n).

Si f(n) es una combinación lineal de las funciones c, n^t , rⁿ, sen (αn), cos (αn),  n^trⁿ, rⁿsen(αn), donde c, r y α son constantes reales y t es un entero positivo, el método de coeficientes indeterminados sirve para determinar una solución particular a_n^(p) de la relación.

El método funciona de la siguiente manera:

Si f(n) es un múltiplo constante de una de las formas de la primera columna de la tabla 1 y no es solución de la relación homogénea asociada, entonces a_n^(p) tiene la forma que se muestra en el correspondiente renglón de la segunda columna de la misma tabla. (A, B, A₀, A₁,….,A_t-1, A_t son constantes determinadas mediante la sustitución de  a_n^(p) en la relación dada).

http://www.soarem.org.ar/Documentos/22%20Alberto.pdf

Si f(n) es una combinación lineal de términos como los de la primera columna de la tabla 1, y ninguno de estos términos es una solución de la relación homogénea asociada, entonces a_n^(p) se forma como la suma de los términos correspondientes en la columna encabezada por  a_n^(p) .

A continuación se muestra un ejemplo en donde podemos observar como se desarrolla una relación de recurrencia de no homogénea.

Ejemplo 1. Para n>=1, sea S un conjunto con 2ⁿ números reales.

El siguiente procedimiento se usa para determinar los elementos máximo y mínimo de S. queremos determinar el número de comparaciones realizadas entre los pares de elementos S durante la ejecución de este procedimiento. Cabe aclarar que existe la posibilidad de lograr los mismos resultados mediante otro método notablemente mejor que requiera menos comparaciones.

Denotamos con a_n  el número de comparaciones necesarias para determinar los elementos máximo y mínimo de S. Cuando n=!, es decir cuando S consta de  dos números reales, a₁ = 1. Cuando:

n=2, | S |=2²=4,

Por lo que

S = { x_1, x₂, x₃, x₄ }, x_i € R

para i=1,2,3,4.

Podemos particionar a S en dos subconjuntos de tamaño dos:

S₁= { x₁ , x₂}, S₂ = {x₃, x₄}_.

Como cada uno de ellos posee dos elementos, utilizamos una comparación para determinar los elementos máximo y mínimo de cada conjunto. Luego si comparamos los elementos mínimos de S₁y S₂ y después comparamos sus elementos máximos, encontramos los elementos mínimo y máximo de S, y vemos que:

a₂ = 4 = 2a₁ + 2.

 

En general, si:

| S | = 2ⁿ⁺¹,

Escribimos

S = S₁ ᴗ S₂,

Donde

| S₁ | = | S₂ | = 2ⁿ.

 Para determinar los elementos máximo y mínimo de cada uno de los conjuntos S₁y S₂, necesitamos una comparación mas pata determinar finalmente cada uno de los elementos máximo y mínimo de S; en consecuencia

a_n+1 =2a_n + 2,  n>=1 y a₁ = 1.

Vemos que se trata de una relación de recurrencia lineal, de primer orden, no homogéneo y con coeficientes constantes.

La solución general de la relación homogénea asociada:

a_n+1 – 2a_n = 0,

Está dada por

a_n^(h) = c (2ⁿ).

 

Ahora utilizamos el método de coeficientes indeterminados para hallar una solución particular:

a_n^(p) .

Como f(n) = 2 no es solución de:

a_n+1 – 2ª_n = 0,

Sea

a_n^(p) = A, una constante.

Sustituyendo esta solución en la relación original vemos que:

A = 2ª +2, con lo cual A = -2.

Así

a_n = c (2ⁿ) – 2.

Utilizando la condición inicial:

a₁ = 1,

Obtenemos:

c = 3/2.

Por lo tanto la solución general de la relación esta dada por

a_n = (3/2)2ⁿ – 2, n>=1.

 

http://www.soarem.org.ar/Documentos/22%20Alberto.pdf

FUNCIONES GENERATRICES – RELACIONES DE RECURRENCIA -E1

Integrantes del equiop 1:

José Reyes Palacio

Ricardo Cruz Santos

Oswualdo Arquisiris Kecha

Nexon Lenin Ceferino Pomposo

Salvador *observación

 

 

Objetivo:

Proporcionar al alumno de la clase de Matemáticas Discretas los recursos teóricos necesarios para el desarrollo y solución de los temas vistos en clase ( funciones generatrices y relaciones de recurrencia), así como desarrollar estrategias que faciliten su aprendizaje.

 

«Nunca consideres el estudio como una obligación,

sino como una oportunidad para penetrar en el bello y

maravilloso mundo del saber.»

Albert Einstein(1879-1955)

Científico alemán nacionalizado

estadounidense.

Contenido:

6.1.    Ejemplos introductorios.

6.2.    Definiciones y técnicas de cálculo.

6.3.    Particiones de enteros.

 

Por: José Reyes Palacio

 

• 6.1 .- EJEMPLOS INTRODUCTORIOS.

En lugar de definir en este punto una función generatriz, examinaremos algunos ejemplos para derivar la idea a partir de ellos.

1.- Determine la función generatriz para el numero de formas de distribuir 35 monedas de un peso entre 5 personas, si (a) no hay restricciones; (b) cada persona obtiene al menos un peso;(c)cada persona tiene al menos  2 pesos;(d)la persona de mayor edad obtiene al menos 10 pesos; y (e) las dos personas mas jóvenes deben obtener al menos 10 pesos.

Solución: se corresponde con el coeficiente de x³⁵ de;

a)   (1+x+x²…..)⁵                           d)    (x¹⁰+x¹¹…..).(1+x+x²+…..)

b)  (x+x²…..)⁵                                    e)  (x¹⁰+x¹¹…..)². (1+x+x²…..)

c) (x²+x³…..)⁵

2.- Encuentre las funciones generatrices para las siguientes sucesiones.

(Grimaldi)

a) 1, -1, 1, -1, 1, …

b) 0, 0, 0, 6, -6, 6, -6, 6…

c) 1, 2, 4, 8, 16 …

 

a)

f(x) = 1 – x + x2 – x3 + x4 …    (1)

x.f(x) =    x – x2 + x3 – x4 …    (2)

Sumando ambas expresiones obtenemos (1+x)f(x) = 1, de donde

f(x) = 1/(1+x)

b)

f(x) = 6×3 – 6×4 + 6×5 – …  = 6×3 ( 1 – x + x2 – … ) y aplicando el apartado c)

la función generatriz pedida es:

f(x) = 6x3/ (1+x)

c)

f(x) = 1 + x2 + x4 + x6 + …   (1).

-x2.f(x)= – x2 – x4 – x6 – …   (2)

Sumando ambas expresiones obtenemos (1-x2)f(x) = 1, de donde

f(x) = 1/ (1-x2)

Por: Ceferino pomposo Nexon.

 

Eqipo 3

Elaborado por: Ana patricia Matus Vicente

4.1 Camino más corto en un grafo

El camino más corto en un grafo consiste en encontrar un camino entre dos vértices o nodos, de modo que la suma de los pesos de sus aristas que lo constituyen sea mínima.

Para poder calcular el camino más corto en un grafo  trabajaremos con dos algoritmos que son:

Algoritmo de Dijkstra.

Algoritmo de Floyd.

El algoritmo de Dijkstra

Este algoritmo resuelve el problema de encontrar los caminos más cortos a partir de un origen, en grafos pesados que no tengan pesos negativos, consiste en ir buscando un camino mínimo atravéz del peso de sus aristas de valor medio de un punto a otro punto.

Por ejemplo:

Atravéz del siguiente grafo encontraremos el camino más corto del nodo A al nodo B, C,  D, E, F.

Equipo 2 «COMBINATORIA BASICA»

****COMBINATORIA BASICA****
David Hernández Trinidad.

– Conteo de objetos
• Se utiliza para determinar: La complejidad de algoritmos, calcular probabilidades de eventos
• Sus reglas básicas resuelven problemas de: Enumeración de posibles números de teléfono, password disponibles en un sistema.

– Permutaciones y Combinaciones
• Se pueden expresar muchos problemas de conteo en términos de disposiciones ordenadas ó no ordenadas de objetos de un conjunto.
• Se pueden analizar “juegos de embite” (póquer) usando técnicas de conteo, así como para determinar las probabilidades de ganar loterías.
• Un problema asociado a la combinatoria se refiere a la generación de todas las ordenaciones posibles de un determinado grupo de elementos (importante en simulación).

5.1 Principios básicos de conteo

Lenin Lopez Martinez

Hay dos principios básicos en combinatoria:

Principio de la adición. Si se desea escoger un objeto que puede tener r tipos distintos, y para el primer tipo hay t₁ opciones, para el segundo tipo hay t₂ opciones, para el tercer tipo t₃ opciones, y así sucesivamente hasta t_r opciones para el ultimo tipo, entonces el objeto puede escogerse de t₁ +t₂ …+t₃ maneras.

Lo que el principio anterior dice, es que el total de opciones es la suma del número de opciones en cada tipo. Como por ejemplo, supongamos que hay que escoger un libro de entre tres materias: matemáticas, historia y biología. Hay seis libros de matemáticas, 9 de historia y 4 de biología . Entonces tenemos 6+9+4 = 19 opciones.

Principio de la multiplicación. Si una tarea se ha de realizar en n etapas, y si la primera etapa tiene k₁ maneras de realizarse, la segunda tiene k₂ maneras, y así sucesivamente hasta k_n , maneras de realizar la ultima, entonces el numero de formas de realizar la tara es k ₁× k₂ ×…×k_n.

Si una persona ha de escoger como vestirse, teniendo 4 camisas, 6 pantalones, 5 pares de calcetines y 2 pares de zapatos, entonces tiene 4 × 6 × 5 ×2 = 240 formas de vestirse, ya que cada elección de la camisa (4 opciones) tiene 6 opciones para el pantalón, lo que da 4 × 6 = 24 opciones para la camisa y pantalón. Para cada una de esas 24 tiene 5 pares de calcetines, totalizando 120 formas, y para cada una de esas tiene dos opciones de los zapatos, de modo que se duplica el total y al final tiene 240 formas de vestirse. El principio de la multiplicación puede visualizarse mediante un diagrama de árbol.

Veamos algunos ejercicios que usan estos principios.
Ejemplo ¿cuántos números de 5 cifras están formados únicamente de cuatros y dos (ejemplos: 44242, 24422)?

R= Nos están pidiendo números de cinco cifras, es decir nos piden llenar con dos y cuatros las cinco rayitas _ _ _ _ _. En la primera rayita podemos poner un dos o un cuatro (2 opciones), en la segunda podemos poner un dos o un cuatro (2 opciones), lo mismo en la tercera, cuarta y quinta rayita. El principio de la multiplicación dice que el total es 2× 2 × 2× 2 × 2= 2⁵ = 32. Así la respuesta es que hay 32 números pedidos.

Ejemplo ¿Cuántos números de cinco cifras no tienen cincos ni treses?
R=Como en el ejemplo anterior, tenemos que llenar cinco espacios _ _ _ _ _.En el primer espacio, de los diez dígitos, no podemos usar el 3 ni el cinco, pero tampoco podemos usar un cero ya que si ponemos cero, el numero tendría menos de cinco cifras. Entonces tenemos 7 opciones para el primer espacio. En las restantes 4 posiciones podemos poner cualquier digito excepto el 3 y el 5, es decir 8 opciones en cada caso. El principio de la multiplicación nos da un total de 7 × 8⁴ = 28672.

5.2 Combinaciones y permutaciones

Sandy Guadalupe Salinas Antonio.

Formas de distribuir y seleccionar objetos de un conjunto finito.

•  Las permutaciones son maneras de distribuir objetos.
•   Las combinaciones son formas de seleccionar objetos.

Empecemos con las permutaciones:

Definición: Dados n objetos distintos, cualquier forma de ordenar estos objetos se denomina una permutación. Las formas de ordenar r de los n objetos se denominan r-permutaciones.

 permutación. Las formas de ordenar r de los n objetos se denominan r-permutaciones.

Teorema: El número de r-permutaciones de un conjunto con n elementos, P(n, r), está dado por:

P(n, r)= n·(n–1)·(n–2)…(n–r+1), r ≤n

Demostración: En una r-permutación hay que cubrir r lugares.

•  Como hay n elementos, hay n maneras de cubrir el primer lugar.
• Una vez seleccionado el primero, quedan n–1 elementos para cubrir el segundo, y así sucesivamente.
• Por tanto, hay n– r+1 elementos para cubrir el último lugar.
• Aplicando la regla del producto: Hay n maneras de seleccionar el primer elemento, n·(n–1) maneras de seleccionar los dos primeros, y así sucesivamente.
• Finalmente, hay n·(n–1)·(n–2)…(n–r+1) maneras de seleccionar r.

• Formula:P(n, n)= n!Por lo tanto:P(n, r) = n! / (n–r)!Donde n es el número de cosas que puedes elegir, y eliges r de ellas
  (No se puede repetir, el orden importa)

  Una permutación de objetos implica orden mientras que una combinación no toma el orden de los objetos considerados. Veamos algún ejercicio que nos ayude a entender más el tema:

  1.-a) ¿Cuántos números de 5 cifras diferentes se puede formar con los dígitos: 1, 2, 3, 4, 5.
  m = 5, n = 5.
  Sí entran todos los elementos. De 5 dígitos entran 5.

  Sí importa el orden. Son números distintos el 12345, 24531, 54321.
  No se repiten los elementos. El enunciado nos pide que las cifras sean diferentes.

  R=

  b) si solo tomamos o elegimos 3 dígitos, ¿cuántas cifras de 3 dígitos  se pueden formar?

  R=5!/ (5-3)!=5!/2!=60 cifras diferentes

• Ahora vallamos con las combinaciones en cuyo caso el orden de los elementos en cada agrupación no determina agrupaciones distintas. Las combinaciones sin repetición:

¿Cuántos grupos de r elementos distintos tomados de un total de n elementos podemos formar si el orden de los elementos no importa?

Si el orden importara, estaríamos en el caso de variaciones sin repetición y tendríamos:

 n*(n-1)*…*(n-r+1)

Por otra parte la permutación de todos los grupos que tengan los mismos componentes será equivalente (en este caso no importa el orden).por lo tanto, como para cada grupo tenemos r! posibles permutaciones, las posibilidades finales son:

Aquí viene como se aplica lo de permutaciones y como funciona: http://profe-alexz.blogspot.com/2010/05/permutaciones-ejercicios-resueltos.html

5.3 Combinaciones con repeticiones: Distribuciones

Estefania Cano Martinez.

Las combinaciones con repetición de m elementos tomados de n en n (m ≥ n), son los distintos grupos formados por n elementos de manera que:

No entran todos los elementos.

No importa el orden.

Sí se repiten los elementos.

Donde n es el número de cosas que puedes elegir, y eliges r de ellas
(Se puede repetir, el orden no importa)

Veamos algunos ejemplos:

1.- En una bodega hay cinco tipos diferentes de botellas. ¿De cuántas formas se pueden elegir cuatro botellas?

No entran todos los elementos. Sólo elije 4

Equipo 3

Elaborado por: Ana patricia Matus Vicente

5.1 PRINCIPIO BÁSICO DE CONTEO.

El estudio de la combinatoria básica nos muestra dos principios básicos de conteo las cuales son:

• Regla de la suma.
• Regla del producto o también conocida como el principio de elección.

A continuación se muestra una breve explicación en lo que consiste cada principio:

• Regla de la suma: si una primera tarea puede realizarse en n formas distintas, y no es posible realizar ambas tarea de manera simultánea, entonces, para llevarla a cabo cualquiera de ellas pueden realizarse cualquiera de m + n formas.

              Se supone que estas m formas son distintas a menos que se indique lo contrario.

• Regla del producto: si un procedimiento se puede descomponer en las etapas primera y segunda, y si existen m resultados posibles de la primera etapa y si, para cada uno de estos resultados, existen n resultados posibles para la segunda etapa, el procedimiento entero puede realizarse, en el orden dado, de m*n formas.

Ejemplo en donde se muestra la aplicación de la regla de la suma.

1. Se desea determinar el número de enteros entre 1 y 50 que sean múltiplos de 7 o de 11. Los números a considerar son de dos tipos: múltiplos de 7 y múltiplos de 11.

Solución:

M= Los múltiplos de 7 entre 1 y 50 son: 7, 14, 21, 28, 35, 42,49. Múltiplos totales son 7.

N= Los múltiplos de 11 entre 1 y 50 son: 11, 22, 32, 44. Múltiplos totales son 4.

Por el principio de la suma, es M + N, es decir: 7+4=11.

11 es el números de enteros entre 1 y 50 que son múltiplos de 7 y 11.

Ejemplo en donde se muestra la aplicación de la regla del producto.

1. Se dispone de una baraja de 40cartas de la cual extraemos cuatro de dos formas diferentes :

(a) Sin devolución de cada carta extraída.

(b) Con devolución de la carta en cada extracción.

Calcular el número de formas diferentes de obtener cuatro cartas en cado caso.

Solución:

En primer caso tenemos 40 cartas, de lo cual extraeremos cuatro sin devolver cada carta extraída, por lo cual al quitar la primera carta solo quedaran 39 cartas, al quitar la segunda carta quedaran solo 38 cartas, así sucesivamente hasta quitar las cuatro cartas que corresponden.

 

En segundo caso tenemos 40 cartas, de lo cual extraeremos cuatro, pero en este caso se devolverá cada carta extraída, por lo cual al quitar la primera carta quedaran 40 cartas, al extraer la segunda carta seguirá quedando 40 cartas, así sucesivamente hasta quitar las cuatro cartas que corresponde quitar.

 

5.2 PERMUTACIONES Y COMBINACIONES.

Elaborado por: Geremías Sánchez Martínez.

PERMUTACIONES

Dados n objetos distintos, cualquier forma de ordenarlos se denomina una permutación. Las formas de ordenar  los n objetos se denominan permutaciones r a r  y se denota de esta manera:

P (n, r) es el número de r-permutaciones (permutaciones de r elementos) de un objeto de n elementos.   

Podemos tomar el siguiente ejemplo: enumerar todas las permutaciones 2 a 2 de las letras a, b y c.

La solución sería:

ab, ac,  ba,  bc, ca, cb

Primer teorema importante que debemos saber para conocer el número de permutaciones r a r de n objetos diferentes esta dado por:

P(n, r) = n(n-1) (n-2)… (n+r-1), r < n

El segundo es: la regla del producto que  indica el número de pares ordenados que se pueden formar a partir de los conjuntos A y B y es n1 x n2;

Donde n1 = | A | y n2 = | B |.

Ejemplo: se tienen 3 procesos y 4 computadoras. Hay que asignar cada tarea a una sola computadora y ninguna debe recibir más de un proceso. ¿De cuantas maneras se puede hacer esto?

La solución podría ser la siguiente: hay 3 x 4 maneras de asignar 3 procesos a 4 computadoras.

Existen dos tipos de permutaciones:

• Se permite repetir: como el siguiente 333.
• Sin repetición: por ejemplo los tres primeros en una carrera. No puedes quedar primero y segundo a la vez.

1. Permutaciones con repetición

Son las más fáciles de calcular. Si tienes n cosas para elegir y eliges r de ellas, las permutaciones posibles son:

n × n ×… (r veces) = n^r

Porque hay n posibilidades para la primera elección, después hay n posibilidades para la segunda elección, y así sucesivamente. Por ejemplo si se tiene 10 números para elegir (0,1,…,9) y eliges 3 de ellos:

10 × 10 ×… (3 veces) = 10³ = 1000 permutaciones

Dejando en claro que la formula solo seria.    n^r

Donde n es el número de cosas que puedes elegir, y eliges r de ellas. Se pueden repetir, el orden no importa.

2. Permutaciones sin repetición

En este caso, se reduce el número de opciones en cada paso. Por ejemplo, ¿cómo se podría ordenar a 16 bolas de billar?, después de elegir por ejemplo la bola número 14 no se puede elegir la misma otra vez.

Así que la primera elección tiene 16 posibilidades, y la siguiente elección tiene 15 posibilidades, después 14, 13, etc. Y el total de permutaciones sería:

16 × 15 × 14 × 13… = 20, 922, 789, 888,000

Pero si sólo se quiere elegir a 3 de ellas, así que sería solamente:

16 × 15 × 14 = 3360

Es decir, hay 3,360 maneras diferentes de elegir 3 bolas de billar de entre 16.

La fórmula que se maneja para estos casos es la siguiente:

 

 

Donde n es el número de cosas que puedes elegir, y eliges r de ellas. Se pueden repetir, el orden no importa.

Otras de las notaciones que las personas suelen usar es la siguiente.

 

Conclusión: Las permutaciones son maneras de distribuir objetos y lo que importa es el lugar que ocupa cada elemento.

 

 

Elaborado por: Elsa Cortés Rito

COMBINACIONES

Una combinación de r  a r  de un conjunto de n elementos  es una selección  desordenada de  r elementos del conjunto.

Por ejemplo, sean cuatro elementos {a, b, c, d}. Los conjuntos, tomados de tres en tres, que se pueden formar con esos cuatro elementos son:

{a, b, c}, {a, b, d} , {a, c, d} y {b, c, d}

Es decir, en total hay 4 conjuntos diferentes formados con tres elementos. Se dice entonces que existen 4 combinaciones posibles.

Es importante notar la diferencia que existe entre una permutación y una combinación. En la permutación lo que importa es el lugar que ocupa cada elemento, mientras que en la combinación no, sino solamente «los integrantes» del conjunto. Hay que recordar que en un conjunto no importa el orden de los elementos. Por ejemplo, los siguientes conjuntos son iguales por tener los mismos elementos, aunque se hayan escrito en diferente orden:

{b, c, d} = {c, b, d}

Y  la fórmula general para calcular las combinaciones que se pueden obtener con n elementos, tomados de r en r, es:

Por tanto en el ejemplo anterior  n es igual a los cuatros elementos  a, b, c Y d  que tenemos para formar los conjuntos de tres y obviamente  r  es igual a 3 el número de  elementos que va a contener  el conjunto.

Entonces:

                                n = 4

                                 r = 3

De manera que:

Otro ejemplo sería:

¿Cuántos equipos de voleibol se pueden formar a partir de 9 jugadores disponibles?

Solución: Se requieren 6 jugadores para formar un equipo de voleibol, por lo que, en este caso se tiene que:

n = 9

r = 6

De manera que:

 

 

Conclusión:

 

En el estudio matemático de las combinaciones, lo que interesa saber es  cuántas son, no cuáles son.

 

Referencias:

 

 

http://www.uam.es/personal_pdi/ciencias/gallardo/capitulo3b.pdf

 http://www.fic.umich.mx/~lcastro/combinaciones.pdf

 

 

 

 

 

 Elaborado por: Itzel Meléndez Sosa

5.3 COMBINACIÓNES CON REPETICIÓN: DISTRIBUCIONES.

Las combinaciones con repetición de m elementos tomados de n en n (m ≥ n), son los distintos grupos formados por n elementos de manera que:

No entran todos los elementos.

No importa el orden.

Sí se repiten los elementos.

Se representa por CRm, n.

Para construir este tipo de combinaciones podemos partir por ejemplo de un conjunto A ={1,2,3,4} y podemos formar todas las combinaciones con repetición posibles. Si se tratara de un elemento. Tendríamos un conjunto de cuatro elementos y podríamos hacer grupos de uno, por lo cual nos quedarían cuatro grupos de un elemento: 1, 2, 3, 4.

En caso de tener grupos de dos elementos, la forma de construirlos será parecida a la de las combinaciones ordinarias a excepción de que al permitirse repetir los elementos debemos agregar a cada una de las de orden uno, el mismo elemento y todos los siguientes. El resultado sería el siguiente 11, 12, 13, 14, 22, 23, 24, 33, 34, 44.

Cuando hablamos de orden de agrupación, hacemos referencia al número de elementos que intervienen en cada agrupación. Una agrupación de orden uno se denomina monería, una de orden dos binaria, etc.

Sea A un conjunto con n elementos y m un natural menor o igual que n. Llamaremos combinación con repetición de m elementos de A  todo subconjunto de m elementos de A en el que un elemento puede presentarse hasta m veces. De esta forma no influye el orden de colocación de los elementos. En este tipo de combinaciones si se repiten los elementos.

El número de combinaciones con repetición se puede calcular de la siguiente forma:

 

Ejemplo:

En una bodega hay en un cinco tipos diferentes de botellas. ¿De cuántas formas se pueden elegir cuatro botellas?

No entran todos los elementos. Sólo elije 4.

No importa el orden. Da igual que elija 2 botellas de anís y 2 de ron, que 2 de ron y 2 de anís.

Sí se repiten los elementos. Puede elegir más de una botella del mismo tipo.

«Combinatoria basica» – E1

No hay errores. Los acontecimientos que atraemos hacia nosotros, por desagradables que sean, son necesarios para aprender lo que necesitamos aprender; todos los pasos que damos son necesarios para llegar adonde hemos escogido.

Richard Bach

COMBINATORIA BASICA

La Combinatoria es una rama de las matemáticas que, básicamente, estudia la construcción y enumeración de agrupaciones de elementos pertenecientes a un conjunto, siguiendo determinados criterios. No guarda ninguna relación estructural con el Cálculo de Probabilidades. Para nosotros es una herramienta más como lo son las integrales o las sucesiones de números reales.

Por: Ricardo Cruz Santos

Cuando existen un conjunto de varias opciones para realizar una determinada tarea, estas formas se pueden combinar para llegar a un número determinado de posibilidades a realizar. A esto se le denomina combinatoria .

El estudio de la combinatoria basica comienza con 2 principios del conteo:

• La regla de la suma o  principio de adición.
• La regla del producto o  principio de la multiplicación.

REGLA DE LA SUMA

Si se desea escoger un objeto que puede tener r tipos distintos, y para el primer tipo hay t₁ opciones, para el segundo tipo hay t₂ opciones, para el tercer tipo t₃ opciones, y así sucesivamente hasta t_r opciones para el ultimo tipo, entonces el objeto puede escogerse de t₁ +t₂ …+t₃ maneras.

Un ejemplo simple:

Imagine que está en el supermercado y desea comprar manzanas. Llega a la sección de frutas y se encuentra con ellas, divididas en 4 cajas. En la primera hay 15 manzanas, en la segunda hay 12, en la tercera 9 y en la cuarta 5. Si desea llevar algunas, se tiene 15 + 12 + 9 + 5 = 41 opciones para llevar manzanas.

Es decir, podemos llevar desde 1 hasta 41 manzanas de las diferentes cajas que tenemos disponibles. En este caso el número de manzanas que llevemos de cada caja no tiene importancia, ya que todas tienen el mismo tipo de elemento.

REGLA DEL PRODUCTO

Si una tarea se ha de realizar en n etapas, y si la primera etapa tiene k₁ maneras de realizarse, la segunda tiene k₂ maneras, y así sucesivamente hasta k_n, maneras de realizar la última, entonces el número de formas de realizar la tara es k ₁× k₂ ×…×k_n.

Ejemplo: Imaginemos ahora que queremos armar nuestra propia computadora; para esto necesitaremos comprar las piezas necesarias. Tenemos entre los artículos 4 tipos distintos de gabinetes, 5 tipos de procesadores, 6 tipos de tarjetas madre, 3 tipos de memoria RAM y 2 tipos de unidades de disco duro. Si podemos elegir solo un elemento de cada dispositivo, tenemos entonces 4 x 5 x 6 x 3 x 2 = 720 combinaciones posibles.

En este caso, usamos un solo artículo, ya que una computadora básicamente requiere solo un elemento de cada uno, o bien solo contamos con un elemento a la vez.

Las etapas que se menciona en la definición son cada artículo escogido.

Segunda aportación E1

El pase de diapositivas requiere JavaScript.

Algoritmo de FORD-FULKERSON

• http://www.cs.pitt.edu/~kirk/cs1501/animations/Network.html

Algoritmo de FLOYD-WARSHALL

• http://www.pms.ifi.lmu.de/lehre/compgeometry/Gosper/shortest_path/shortest_path.html
• http://alexle.net/wp-content/uploads/2006/04/floyd.html

Algoritmo de DIJKSTRA

• http://students.ceid.upatras.gr/~papagel/project/kef5_7_1.htm

Algoritmo de KRUSKAL

• http://students.ceid.upatras.gr/~papagel/project/kruskal.htm

Algoritmo de PRIM

• http://students.ceid.upatras.gr/~papagel/project/prim.htm

OPTIMIZA CION DE GRAFOS (Equipo_2)

4.-OPTIMIZA CION DE GRAFOS

La idea central estudio de propiedades basadas en los conceptos de conexión y distancia en grafos, tanto desde un punto de vista teórico como su aplicación en problemas de optimización.

Se recoge los conceptos y propiedades teóricas sobre grafos y se formulan los problemas de optimización, que se abordaran posteriormente. Está dedicado al estudio de una clase de grafos caracterizada por cumplir cierta restricción en la conexión entre vértices. Se presenta una nueva clase de grafos generalizando la anterior, para la cual se han obtenido diversas propiedades y resultados interesantes.

Los siguientes capítulos estudian problemas de optimización sobre grafos con peso en las aristas. Así, el capítulo tercero plantea el problema del camino mínimo. Para su resolución se dan diversos métodos que buscan la determinación de los caminos mínimos no dominados y eficientes.

Se aborda el problema del árbol generador. Se introducen varios algoritmos que nos permiten determinar los arboles generadores eficientes y, supuesta una función de utilidad con determinadas condiciones definida sobre el conjunto de arboles generador optimo

4.1.EL CAMINO MAS CORTO.

Elaboro: David Hernandez Trinidad

En la Teoría de grafos, el problema de los caminos más cortos es el problema que consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es mínima.

Los caminos más cortos entre dos nodos, para diferenciarlo de la siguiente generalización:

• El problema de los caminos más cortos desde un origen en el cual tenemos que encontrar los caminos más cortos de un vértice origen v a todos los demás vértices del grafo.
• El problema de los caminos más cortos con un destino en el cual tenemos que encontrar los caminos más cortos desde todos los vértices del grafo a un único vértice destino, esto puede ser reducido al problema anterior invirtiendo el orden.
• El problema de los caminos más cortos entre todos los pares de vértices, el cual tenemos que encontrar los caminos más cortos entre cada par de vértices (v , v’) en el grafo.

Algoritmo de Dijkstra, resuelve el problema de los caminos más cortos desde un único vértice origen hasta todos los otros vértices del grafo.

       Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial,         un vector D de tamaño N guardará al final del algoritmo las distancias desde x al resto de los nodos.

1. Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.
2. Sea a = x (tomamos a como nodo actual).
3. Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos v_i.
4. Si la distancia desde x hasta v_i guardada en D es mayor que la distancia desde x hasta a, sumada a la distancia desde a hasta v_i; esta se sustituye con la segunda nombrada, esto es:
   si (D_i > D_a + d(a, v_i)) entonces D_i = D_a + d(a, v_i)
5. Marcamos como completo el nodo a.
6. Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenando los valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.

Ejemplo del algoritmo de Dijkstra:

Camino                                                                        longitud (peso o coste)

Algoritmo Floyd -Warshall

• Obtiene la mejor ruta entre todo par de nodos.
• Trabaja con la matriz D inicializada con las distancias directas entre todo par de nodos.
• La iteración se produce sobre nodos intermedios, es decir, para todo elemento de la matriz se prueba si lo mejor para ir de i a j es a través de un nodo intermedio elegido o como estaba anteriormente, y esto se prueba con todos los nodos de la red.
  Una vez probados todos los nodos de la red como nodos intermedios, la matriz resultante da la mejor distancia entre todo par de nodos.

Es decir el algoritmo es el siguiente:

• Empezando con el nodo 1 como intermedio (n=0), se prueba con todos los nodos como nodos intermedios, el último es con el nodo N como nodo intermedio (n=N-1), y así se van hallando las distancias mínimas.

Ejemplo del algoritmo de Floyd:

4.2 FLUJOS EN DATOS.

Elaboro: Lenin Lopez Martinez.

Entendiendo una red de flujo como un grafo dirigido, donde la fuente es quien produce o inicia el traspaso de algún material o producto por los arcos, estos últimos, vistos como caminos o conductos y tomando en cuenta la ley de corrientes de Kirchoff, donde, la suma de flujos entrantes a un vértice debe ser igual a la suma de flujos saliendo del vértice.

ü  Flujos máximo
Uno de los problemas más comunes de flujo en redes es el de Flujo Máximo. Esto es, dada un red de flujos, encontrar un flujo de un nodo v a uno u tal que ningún otro flujo tenga mayor valor. El flujo que sale de v debe ser igual al flujo que entra a u.

v   Algoritmo de Ford-fullkerson

• • Este método depende de tres ideas importantes: Camino de aumento y red residual.
• • Este método es iterativo. Se comienza con f(u,v) =0 para cada par de nodos.
• • En cada iteración se incrementa el valor del flujo buscando un camino de aumento, el cual es un camino desde la fuente al resumidero que puede conducir más flujo.

Ford-Kulkerson_metodo (G, s, t)

Inicializar flujo f a 0;

While (existe un camino de aumento p) do

Aumentar el flujo f a lo largo de p;

Return f;

• • Se repite el proceso previo hasta no encontrar un camino de aumento.
• • Capacidad residual: es la capacidad adicional de flujo que un arco puede llevar: cf (u, v)  = c (u, v) – f(u,v)
• • Dado una red de flujo G= (v, E) y un flujo f, la red residual: inducida por f es Gf = (V, Ef), con Ef = {(u,v) ∈ VxV: cf (u,v)>0

Ejemplo del algoritmo de Ford-Fullkerson:

ü  Grafos Bipartitos

Un grafo G = (V,E) se dice que es bipartito si el conjunto de vértices V puede particionarse en dos subconjuntos V1 y V2 tales que todas las aristas tengan un extremo en V1 y el otro en V2.

En la figura se representa un grafo bipartito con

V1 = {s, t, u, v} y V2 = {x, y, z}.

ü  Grafos Bipartitos Completos

Si G = (V,E) es un grafo bipartito con V = V1 ᴜ V2, V1 ∩ V2 = Ø, |V1| = m, |V21 = n y E = V1 × V2 (es decir, si (u, v) es una arista para todo par de vértices u 2 V1, v 2 V2) entonces se dice que G es un grafo bipartito completo y se denota Km,n. La siguiente figura se representa K3, 3.

4.3 EMPAREJAMIENTO DE GRAFOS.

Elaboro:Sandy Guadalupe Salinas Antonio.

Un emparejamiento de un grafo simple G, es cualquier subgrafo 1-regular de G, es decir un subgrafo inducido por las aristas dos a dos no incidentes entre sí.

A = {a, b, c, d, e, f, g, h, i, j, k, l}

M = {(c, i), (e, g), (f, h), (d, j)}

                                                

 

ü  Emparejamiento máximal

Un emparejamiento es máximal en un grafo si no se puede ampliar agregando aristas (toda arista de G comparte extremos con alguna arista de M).

ü  Emparejamiento máximo

Un emparejamiento es máximo si tiene el mayor número posible de aristas.

 

ü  Emparejamiento en Grafos Bipartitos

En un grafo bipartito tenemos un emparejamiento completo y decimos que M es completo para Χ si |M| = | Χ |.

4.3 ARBOLES PONDERADOS Y ARBOLES DE EXPANSION MINIMOS.

Elaboro: Estefania Cano Martinez.

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.

El peso total del grafo es:

W(G)=w(a,b)+w(a,c)+w(a,d)+w(a,e)+w(a,f)+w(b,c)+w(b,e)+w(b,f)+w(b,g)+w(c,e)+w(c,f)+w(d,g)+w(e,f)+w(f,g)=8+2+12+4+6+6+9+3+9+3+5+3+4+5=79.

El peso del subgrafo H formado por los vértices a, b, c, d seria W (H)=8+2+12+6=28.

Un árbol de expansión mínimo de un grafo conexo G con pesos es un árbol generador de G que tiene el menor peso. En general no es único.  Todo grafo conexo con pesos tiene un árbol generador mínimo.

Algoritmo de Prim. Se parte de un vértice y se van alcanzando los demás, de uno en uno, del modo más económico posible, con respecto al peso de las aristas.

1. Seleccionar un vértice arbitrario u.

2. Hacer S={u} y T={}.

3. Para cada vértice z de V-S asignar t(z)=w(u, z) si existe la arista (u, z). Si esta arista no existe asignar .t(z) =∞

4. Elegir el vértice v de V-S tal que t(v) sea el menor de los números t(z) para todo z de V-S.

5. Insertar v en S

6. Insertar la arista (u, v) en T

7. Mientras V: S≠

a) Para cada z de V-S se actualiza t(z)=min{t(z),w(v, z)}.

b) Elegir el vértice v de V-S tal que t(v) sea el menor de los números t(z) para todo z de V-S.

c) Insertar v en S

d) Insertar en T la arista (u,v) tal que u está en S y t(v)=w(u,v).

Ejemplo del algoritmo de prim:

Algoritmo de Kruskal: Se eligen aristas de la forma más económica. Inicialmente se ordenan las aristas por su peso. A continuación se van eligiendo las aristas de menor peso de modo tal, que no formen ciclo con las aristas anteriormente seleccionadas. Para evitar que se formen ciclos se asignan etiquetas a los vértices de modo que los vértices que formen parte de las aristas ya elegidas tengan todas las mismas etiquetas.

1. T={}

2. Asignar etiquetas a todos los vértices t(i)=i, i=1, 2, …, n.

3. Mientras halla vértices con etiquetas diferentes repetir.

a) Escoger la arista (u, v) de menor peso tal que t(u) sea diferente de t(v). Agregarla a T

b) Asignar a todos los vértices de una componente conexa de T la misma etiqueta.

 

ejemplo del algoritmo de Kruskal:

 

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             

                       

 

Equipo 3

Elaborado por: Ana patricia Matus Vicente
4.1 CAMINO MÁS CORTO EN UN GRAFO
El camino más corto en un grafo consiste en encontrar un camino entre dos vértices o nodos, de modo que la suma de los pesos de sus aristas que lo constituyen sea mínima.
Para poder calcular el camino más corto en un grafo trabajaremos con dos algoritmos que son:
Algoritmo de Dijkstra.
Algoritmo de Floyd.

EL ALGORITMO DE DIJKSTRA
Este algoritmo resuelve el problema de encontrar los caminos más cortos a partir de un origen, en grafos pesados que no tengan pesos negativos, consiste en ir buscando un camino mínimo atravéz del peso de sus aristas de valor medio de un punto a otro punto.

Por ejemplo:
Atravéz del siguiente grafo encontraremos el camino más corto del nodo A al nodo B, C, D, E, FLa siguiente imagen muestra el valor del camino minino que hay del vértice A para los demás nodos.

Imagen elaborada por: Ana Patricia Matus Vicente.

El siguiente link muestra la ejecución de una aplicación de cómo funciona el algoritmo de Dijkstra.

http://students.ceid.upatras.gr/~papagel/project/kef5_7_1.htm

ALGORITMO DE FLOYD
Este algoritmo permite hallar la ruta más corta en grafos dirigidos ponderados.

• Obtiene la mejor ruta entre todo par de nodos.

• Trabaja con la matriz D inicializada con las distancias directas entre todo par de nodos.

• La iteración se produce sobre nodos intermedios, es decir, para todo elemento de la matriz se prueba si lo mejor para ir de i a j es a través de un nodo intermedio elegido o como estaba anteriormente, y esto se prueba con todos los nodos de la red.

• Una vez probados todos los nodos de la red como nodos intermedios, la matriz resultante da la mejor distancia entre todo par de nodos.

Imagen elaborada por: Ana Patricia Matus Vicente.

      El siguiente link muestra la ejecución de una aplicación de cómo funciona el algoritmo de Floyd.
http://students.ceid.upatras.gr/~papagel/project/kef5_7_2.htm

Elaborado por: Elsa Cortes Rito
4.2 FLUJOS EN GRAFOS
Un flujo es un conjunto de pesos conectados con las aristas de un grafo y que pueden indicar la capacidad de transportar objetos de un lugar a otro.
Un flujo en una red satisface las siguientes condiciones:

•   Ningún flujo en la arista es mayor que su capacidad.

• El flujo total que entra a cada nodo es igual al flujo total que sale de dicho nodo.

Ejemplo:
Sea un grafo dirigido G = (V, E), en el que se consideran dos nodos o vértices: uno denominado nodo origen y otro denominado nodo destino. Se considera que no existe un arco directo que conecte el nodo origen con el nodo destino. Pues el grafo estará formado por unos nodos intermedios conocidos como puntos de transbordo a través de los cuales el flujo es desviado.

Para calcular el flujo máximo de un grafo en redes se utiliza el clásico algoritmo de Ford-Fulkerson este algoritmo consiste en:

1.   Primero se comienza con flujo nulo en todas partes.
2.   Luego se incrementa el flujo a lo largo de cualquier camino de origen a destino que no tenga aristas llenas que avancen o aristas vacías que retrocedan.
3. Se continúa hasta que no hayan más caminos como estos en la red.

El flujo máximo que entra y sale del grafo es 3.

Este grafo fue basado en: http://ccg.ciens.ucv.ve/~ernesto/nds/CotoND200302.pdf
Este es un link para ver un ejemplo animado de un problema de flujo máximo.
http://www-desir.lip6.fr/~durrc/MaxFlow/
http://www-b2.is.tokushimau.ac.jp/~ikeda/suuri/maxflow/MaxflowApp.shtml?demo2

Elaborado por: Itzel Meléndez Sosa
4.3 TEORÍA DE EMPAREJAMINETOS
En matemática discreta y particularmente en teoría de grafos un conjunto independiente de aristas también llamado emparejamiento, en un grafo es un conjunto de aristas independientes, es decir, sin vértices en común.
Definición:
Dado un grafo G= (V, E) un emparejamiento M en G es un conjunto de aristas no adyacentes entre si. En otras palabras, es un subconjunto M⊂G tal que dos aristas cualesquiera de M no tienen un extremo común.
Un emparejamiento es máximo 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.

EMPAREJAMIENTO EN GRAFOS BIPARTITOS
Encontrar un emparejamiento máximo bipartito (a menudo llamado cardinalidad máxima de un grafo bipartito) en un grafo bipartito                G= ((X,Y),E) es quizás el problema más simple. El algoritmo de los caminos aumentantes lo encuentra por búsqueda de caminos aumentantes por cada a y añadiéndolo al apareamiento si existe. Como cada camino puede ser encontrado en tiempo , el costo de tiempo es O(VE). Todas las aristas con flujo de a constituyen un apareamiento máximo. Una mejora sobre esto es el algoritmo de Hopcroft-Karp, de costo de tiempo .
En un grafo bipartito ponderado, cada arista tiene asociado un valor. Un emparejamiento máximo bipartito ponderado está definido como un apareamiento perfecto donde la suma de los valores de sus arcos en el apareamiento tiene un valor máximo.. Si el grafo no es completamente bipartito, los arcos ausentes son introducidos con valor cero. Encontrar tal apareamiento es conocido como problema del asignamiento. Para resolverlo se usa la búsqueda del camino mínimo modificado con el algoritmo del camino aumentante. Si usamos el algoritmo de Bellman-Ford, con costo de tiempo . El más especializado es el algoritmo Húngaro que resuelve el problema de asignación con costo de tiempo .

Elaborado por: Geremias Sánchez Martínez
4.4 ARBOLES PONDERADOS Y ARBOLES DE EXPANSIÓN MÍNIMA.
Un grafo ponderado o grafo con pesos es un grafo G (V, E) en el que cada arista se le asigna un valor real no negativo o peso. El peso en un subgrafo de un grafo ponderado es la suma de los pesos de todas sus aristas.
Ejemplo: dado el grafo con pesos.

El peso total del grafo es:
W(G)=w(a,b)+w(a,c)+w(a,d)+w(a,e)+w(a,f)+w(b,c)+w(b,e)+w(b,f)+w(b,g)+w(c,e)+w(c,f)+w(d,g)+w(e,f)+w(f,g)= 8+2+12+4+6+6+9+3+9+3+5+3+4+5=79.
El peso del subgrafo W (H)=8+2+12+6=28.

CONCEPTO DE ÁRBOL GENERADOR MÍNIMO.
Un árbol generador mínimo de un grafo conexo G con pesos es un árbol generador de G que tiene el menor peso. En general no es único. Lo denotaremos por MIN (G), en donde 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. Un árbol recubridor mínimo es un árbol recubridor que pesa menos o igual que otros arboles recubridores.

Existen proposiciones que nos dicen cuando un árbol tiene un árbol generador mínimo.
Proposición 1. Todo grafo conexo con pesos tiene un árbol generador mínimo.
Proposición 2. Dado un grafo G con peso, la arista de mayor peso de un ciclo no pertenece a ningún MIN (G).
Existen diversos algoritmos para hallar el costo mínimo de un árbol.

Imagen tomada desde:
http://es.wikipedia.org/wiki/%C3%81rbol_recubridor_m%C3%ADnimo

ALGORITMO DE PRIM.
Es el algoritmo más sencillo de implementar y el mejor método para grafos densos. Este algoritmo puede encontrar el peso mínimo de cualquier grafo conexo.
El siguiente ejemplo ilustra el funcionamiento del algoritmo. La secuencia de las ilustraciones van de izquierda a derecha y de arriba hacia abajo. La primera imagen muestra el grafo pesado y las siguientes muestran el funcionamiento del algoritmo de prim y como va cambiando el conjunto U durante la ejecución.

Imagen tomada desde: http://ccg.ciens.ucv.ve/~ernesto/nds/CotoND200302.pdf

A continuación se presenta el algoritmo de Prim:
Comienza
Grafo T = nuevo Grafo (numNodos) // crea un grafo sin arcos
Para i = 1 hasta numNodos
Comienza
BajoCosto [i] = G[1][i]
Cercano [i] = 1
Termina
Para i = 1 hasta numNodos //encuentra el vértice k fuera del árbol a
Comienza //algún vértice en el árbol
Min = bajoCosto [2]
k = 2
Para j = 3 hasta numNodos
Si bajoCosto [j] < min entonces
Comienza
Min = bajoCosto [j]
k = j
Termina
T.añade (k, cercano [k]) // se añade k al árbol
BajoCosto [k] = a
Para j = 2 hasta numNodos
Si G[k][j] < bajoCosto [i] y bajoCosto [j] < a entonces
Comienza
BajoCosto [j] = G[k][j]
Cercano [j] = k
Termina
Termina
Regresa T
Termina.
El siguiente link muestra la ejecución de una aplicación de cómo funciona el algoritmo de Prim.
http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/PrimApp..shtml?demo1

El siguiente ejemplo ilustra la metodología anterior, utilizando una pila de aristas P, en donde las aristas se van apilando de menor a mayor según el peso de la misma. La secuencia de ilustraciones va de izquierda a derecha.

Imagen tomada desde: http://ccg.ciens.ucv.ve/~ernesto/nds/CotoND200302.pdf

ALGORITMO DE KRUSKAL
Un enfoque diferente para encontrar un árbol abarcador mínimo es añadir un arco a la vez, en cada paso, utilizando el arco más pequeño que no forme ciclos, así, teniendo un boque con n-árboles, en n pasos, combinar dos subárboles hasta obtener uno sólo. Este algoritmo se atribuye a J. Kruskal (1956).
El algoritmo comienza a partir de un conjunto de arboles degenerados formados por un solo nodo, que son los nodos del grafo, y se comienzan a combinar arboles de dos en dos usando la arista menos costosa posible, hasta que solo quede un solo árbol: el árbol de expansión mínima.
El siguiente ejemplo muestra el funcionamiento del algoritmo: la secuencia de ilustraciones va de izquierda a derecha.

Imagen tomada desde:

Haz clic para acceder a CotoND200302.pdf

A continuación se presenta el algoritmo de Kruskal:
Grafo T = nuevo Grafo ()
Mientras T contenga menos de n-1 arcos y E distinta de 0
Comienza
Escoger un arco (v, w) de E de costo mínimo
Borrar (v, w) de E
Si (v, w) no crea un ciclo en T entonces
T = T È (v, w)
Otro
Descartar (v, w)
Termina
Termina
El siguiente link muestra la ejecución de una aplicación de cómo funciona el algoritmo de Kruskal.
http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/kruskal/kruskalApp.shtml?demo2