martes, 18 de mayo de 2010
El artículo de Ford y de Fulkerson (1956) con el problema de flujo máximo estableció el famoso teorema del flujo máximo - mínimo corte.
Corte: Un corte define una serie de arcos cuya supresión de la red causa una interrupción completa del flujo entre el origen y el destino. La capacidad de corte es igual a la suma de las capacidades de los arcos asociados. Entre todos los cortes posibles en la red , el corte con la menor capacidad es un corte mínimo proporciona el flujo máximo en la red.
Propiedad: v (f) =f(S, S’)-f(S', S).
El corte con la capacidad mas pequeña se denomina corte mínimo.
Cualquier nodo compatible desde el nodo fuente al nodo destino no puede exceder la capacidad de ningún corte. Por lo tanto, el flujo máximo a través de la red esta limitado por la capacidad del corte mínimo.
Para cualquier red del flujo máximo desde el nodo fuente al nodo destino es igual a la capacidad del corte destino.
A partir de este teorema el problema de encontrar el flujo máximo en una red se traduce en encontrar las capacidades de todos los cortes y elegir la minima capacidad. Por otra parte dado el valor máximo de flujo no especifica como este flujo es distribuido a tarves de los cortes que separan el nodo fuente del destino 2n-2.
Ejemplo:
En un grafo dirigido un conjunto de flechas S tal que todo camino dirigido de s a t contiene una flecha de S, decimos que S separa a s de t.
Un corte separa a s de t y un conjunto de flechas que separa a s de t es un corte.
En un grafo dirigido el número mínimo de flechas que separa a s de t es igual al máximo número de caminos dirigidos disjuntos de flechas que unen s con t.
NOTA: que si dos caminos dirigidos no tienen flechas comunes pueden tener vértices comunes. En cambio si dos caminos no tienen vértices comunes no tienen tampoco flechas comunes.
Este algoritmo se puede usar para resolver modelos de: transporte de mercancías (logística de aprovisionamiento y distribución), flujo de gases y líquidos por tuberías, componentes o piezas en líneas de montaje, corriente en redes eléctricas, paquetes de información en redes de comunicaciones, tráfico ferroviario, sistema de regadíos, etc.
Teorema de Ford-Fulkerson (1962): En cualquier red, el flujo máximo que fluye de la fuente al destino es igual a la capacidad del corte mínimo que separa a la fuente del destino.
Corte: Un corte define una serie de arcos cuya supresión de la red causa una interrupción completa del flujo entre el origen y el destino. La capacidad de corte es igual a la suma de las capacidades de los arcos asociados. Entre todos los cortes posibles en la red , el corte con la menor capacidad es un corte mínimo proporciona el flujo máximo en la red.
Propiedad: v (f) =f(S, S’)-f(S', S).
El corte con la capacidad mas pequeña se denomina corte mínimo.
Cualquier nodo compatible desde el nodo fuente al nodo destino no puede exceder la capacidad de ningún corte. Por lo tanto, el flujo máximo a través de la red esta limitado por la capacidad del corte mínimo.
Para cualquier red del flujo máximo desde el nodo fuente al nodo destino es igual a la capacidad del corte destino.
A partir de este teorema el problema de encontrar el flujo máximo en una red se traduce en encontrar las capacidades de todos los cortes y elegir la minima capacidad. Por otra parte dado el valor máximo de flujo no especifica como este flujo es distribuido a tarves de los cortes que separan el nodo fuente del destino 2n-2.
Ejemplo:
En un grafo dirigido un conjunto de flechas S tal que todo camino dirigido de s a t contiene una flecha de S, decimos que S separa a s de t.
Un corte separa a s de t y un conjunto de flechas que separa a s de t es un corte.
En un grafo dirigido el número mínimo de flechas que separa a s de t es igual al máximo número de caminos dirigidos disjuntos de flechas que unen s con t.
NOTA: que si dos caminos dirigidos no tienen flechas comunes pueden tener vértices comunes. En cambio si dos caminos no tienen vértices comunes no tienen tampoco flechas comunes.
Este algoritmo se puede usar para resolver modelos de: transporte de mercancías (logística de aprovisionamiento y distribución), flujo de gases y líquidos por tuberías, componentes o piezas en líneas de montaje, corriente en redes eléctricas, paquetes de información en redes de comunicaciones, tráfico ferroviario, sistema de regadíos, etc.
Teorema de Ford-Fulkerson (1962): En cualquier red, el flujo máximo que fluye de la fuente al destino es igual a la capacidad del corte mínimo que separa a la fuente del destino.
domingo, 16 de mayo de 2010
Proyecto #5 Problemas de Corte Minimo
Definición de corte minimo
En lo que respecta a las redes, un corte es un conjunto de corte en el cual quedan dos partes disjuntas del conjunto de vértices, V1 y V2 que, situados en la red, dejan la fuente en una de ellas y al sumidero en la otra.
Definición de capacidad de un corte
Se llama capacidad de un corte a la suma:
S Capacidad (v,w) ; v Є V1 , w ЄV2
V1 es la parte que contiene a la fuente
V2 es la parte que contiene al sumidero
Sea F un flujo en G y sea (P, P) un corte en G. Entonces la capacidad de (p, p) es mayor o igual que el valor de F; es decir:
Si ЄP S JЄP Cij ³ S i F ai
La notación Si : Significa la suma sobre todos los vértices i
Demostración: observe Sj ЄP S iЄP Cji = Sj ЄP S iЄP F ij
Pues cada lado de la ecuación es simplemente la suma de Fij sobre todas las de i, j Є P
Ahora
S i F ai= Sj ЄP Sj Fji -Sj ЄP Sj
=Sj ЄP SiЄP Fji +Sj ЄP SiЄP Fji- =Sj ЄP SiЄP Fji
=Sj ЄP SiЄP Fji -Sj ЄP SiЄP Fji- £Sj ЄP SiЄP Fji£ Sj ЄP SiЄP Cji
El corte minimal nos da la minima capacidad del corte efectuado en el grafo.
Para el cálculo de la capacidad del corte minimal no se tienen en cuenta las capacidades de las aristas del corte cuya dirección sea contraria al sentido de flujo.
TEOREMA DEL FLUJO MÁXIMO Y EL CORTE MÍNIMO
Sea F un flujo en G y sea (P, P) un corte en G si la igualdad se cumple entonces el flujo es máximo y el corte es mínimo si y solo si:
1) FI J = CI J para i ЄP, J Є P
2) Fij =0 para i Є P, J Є P
El valor del flujo maximal de una red es igual a la capacidad del corte minimal que se puede aplicar a la red.
Se puede obtener, por tanto el corte minimal de una red, conociendo el flujo maximal de la red obtenido mediante la aplicación del algoritmo anteriormente definido.
En lo que respecta a las redes, un corte es un conjunto de corte en el cual quedan dos partes disjuntas del conjunto de vértices, V1 y V2 que, situados en la red, dejan la fuente en una de ellas y al sumidero en la otra.
Definición de capacidad de un corte
Se llama capacidad de un corte a la suma:
S Capacidad (v,w) ; v Є V1 , w ЄV2
V1 es la parte que contiene a la fuente
V2 es la parte que contiene al sumidero
Sea F un flujo en G y sea (P, P) un corte en G. Entonces la capacidad de (p, p) es mayor o igual que el valor de F; es decir:
Si ЄP S JЄP Cij ³ S i F ai
La notación Si : Significa la suma sobre todos los vértices i
Demostración: observe Sj ЄP S iЄP Cji = Sj ЄP S iЄP F ij
Pues cada lado de la ecuación es simplemente la suma de Fij sobre todas las de i, j Є P
Ahora
S i F ai= Sj ЄP Sj Fji -Sj ЄP Sj
=Sj ЄP SiЄP Fji +Sj ЄP SiЄP Fji- =Sj ЄP SiЄP Fji
=Sj ЄP SiЄP Fji -Sj ЄP SiЄP Fji- £Sj ЄP SiЄP Fji£ Sj ЄP SiЄP Cji
El corte minimal nos da la minima capacidad del corte efectuado en el grafo.
Para el cálculo de la capacidad del corte minimal no se tienen en cuenta las capacidades de las aristas del corte cuya dirección sea contraria al sentido de flujo.
TEOREMA DEL FLUJO MÁXIMO Y EL CORTE MÍNIMO
Sea F un flujo en G y sea (P, P) un corte en G si la igualdad se cumple entonces el flujo es máximo y el corte es mínimo si y solo si:
1) FI J = CI J para i ЄP, J Є P
2) Fij =0 para i Є P, J Є P
El valor del flujo maximal de una red es igual a la capacidad del corte minimal que se puede aplicar a la red.
Se puede obtener, por tanto el corte minimal de una red, conociendo el flujo maximal de la red obtenido mediante la aplicación del algoritmo anteriormente definido.
domingo, 25 de abril de 2010
PROYECTO 4
Listas doblemente enlazadas
Este es el tema que elegimos para nuestra presentación.
Mis compañeras Danya A. Peralta Cano y Arely Quintanilla trabajamos
muy bien en equipo por que todas apotamos, ya que primero buscamos la
información sobre el tema seleccionado, lo checamos para saber de que
informa el tema, después cada quien dijo sus opiniones, para hacer la
presentación. Todas trabajamos para que nos quedara con calidad.
En que aspectos:
Estoy bien : Que aunque creí que el tema era difícil lo supe identificar
para después entenderlo bien.
Debo mejorar: Creo que siempre hay que mejorar cada día y
poner todo nuestra dedicación, es lo que yo hago en cada proyecto que he
entregado. Y acepto cada opinión.
Ayudo o me Ayudan: Las dos pociones son las que escojo por que el trabajo
en equipo es para eso, ya que en algunas ocasiones yo aporto; en otrs mis
compañeras pero todo es con es por igual nadie hace de más y nadie de menos
por que es un trabajo en equipo. Y mis compañeras y yo lo tratamos de hacer
bien.
Este es el tema que elegimos para nuestra presentación.
Mis compañeras Danya A. Peralta Cano y Arely Quintanilla trabajamos
muy bien en equipo por que todas apotamos, ya que primero buscamos la
información sobre el tema seleccionado, lo checamos para saber de que
informa el tema, después cada quien dijo sus opiniones, para hacer la
presentación. Todas trabajamos para que nos quedara con calidad.
En que aspectos:
Estoy bien : Que aunque creí que el tema era difícil lo supe identificar
para después entenderlo bien.
Debo mejorar: Creo que siempre hay que mejorar cada día y
poner todo nuestra dedicación, es lo que yo hago en cada proyecto que he
entregado. Y acepto cada opinión.
Ayudo o me Ayudan: Las dos pociones son las que escojo por que el trabajo
en equipo es para eso, ya que en algunas ocasiones yo aporto; en otrs mis
compañeras pero todo es con es por igual nadie hace de más y nadie de menos
por que es un trabajo en equipo. Y mis compañeras y yo lo tratamos de hacer
bien.
http://arelyquintanilla.blogspot.com/
domingo, 14 de marzo de 2010
Torres de Hanói
Introducción
Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Éduard Lucas.Este solitario se trata de un juego de ocho discos de radio creciente que se apilan insertándose en una de las tres estacas de un tablero. El objetivo del juego es crear la pila en otra de las estacas siguiendo unas ciertas reglas. El problema es muy conocido en la ciencia de la computación y aparece en muchos libros de texto como introducción a la teoría de algoritmos.
En su forma más tradicional, consiste en tres varillas verticales. En una de las varillas se apila un número indeterminado de discos (elaborados de madera) que determinará la complejidad de la solución, por regla general se consideran ocho discos. Los discos se apilan sobre una varilla en tamaño decreciente. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio en una de las varillas, quedando las otras dos varillas vacantes. El juego consiste en pasar todos los discos de la varilla ocupada (es decir la que posee la torre) a una de las otras varillas vacantes. Para realizar este objetivo, es necesario seguir tres simples reglas:
1. Sólo se puede mover un disco cada vez.
2. Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
3. Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.
Existen diversas formas de realizar la solución final, todas ellas siguiendo estrategias diversas.
Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Éduard Lucas.Este solitario se trata de un juego de ocho discos de radio creciente que se apilan insertándose en una de las tres estacas de un tablero. El objetivo del juego es crear la pila en otra de las estacas siguiendo unas ciertas reglas. El problema es muy conocido en la ciencia de la computación y aparece en muchos libros de texto como introducción a la teoría de algoritmos.
En su forma más tradicional, consiste en tres varillas verticales. En una de las varillas se apila un número indeterminado de discos (elaborados de madera) que determinará la complejidad de la solución, por regla general se consideran ocho discos. Los discos se apilan sobre una varilla en tamaño decreciente. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio en una de las varillas, quedando las otras dos varillas vacantes. El juego consiste en pasar todos los discos de la varilla ocupada (es decir la que posee la torre) a una de las otras varillas vacantes. Para realizar este objetivo, es necesario seguir tres simples reglas:
1. Sólo se puede mover un disco cada vez.
2. Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
3. Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.
Existen diversas formas de realizar la solución final, todas ellas siguiendo estrategias diversas.
Suscribirse a:
Entradas (Atom)
