Historia de mexico
Páginas: 7 (1715 palabras)
Publicado: 19 de noviembre de 2010
INTRODUCCIÓN
Presento a su consideración este encarpetado en donde se presentan temas acerca del teorema de corte minimal, los problemas de parear o parejar elementos de un conjunto con elementos de otro conjunto. Se vera que estos problema puede reducirse a encontrar el flujo maximal en una red. También se tratará la existencia de algunos tipos de parejamientos que pueden existir en unared, así como también la forma de expresarlos.
CAPITULO I:
METODOLOGÍA
|PASOS A SEGUIR |LUGAR DE REUNION |FECHA |
|CONOCER LOS TEMAS A TRATAR EN LA INVESTIGACION |CASA DE UN INTEGRANTE |LUNES 21 DE DICIEMBRE DEL |
|| |2004 |
|REVISAR EN LIBROS LOS TEMAS DE INVESTIGACION |CASA DE UN INTEGRANTE |MARTES 28 DE DICIEMBRE |
| | |DEL 2004 |
|RECABARINFORMACION DE CADA UNO DE LOS TEMAS A INVESTIGAR | |DOMINGO 2 DE ENERO DEL |
| |CIBER |2005 |
|SELECCIÓN Y ACOMODACION DE TODA LA INFOMACION RECOLECTADA |CENTRO DE COMPUTO DEL ITESCAM |JUEVES 6 DE DE ENERODEL |
| | |2005 |
|ELABORACION DEL DOCUMENTO EN FORMA GENERAL (DESGLOSADA)CADA TEMA Y |CIBER |MIERCOLES 12 DE ENERO DEL|
|LA COMPRENSION DE ESTOS ||2005 |
CAPITULO II:
TEOREMA DE CORTE MINIMAL
Definición de corte
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 lasuma:
(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:
(i ЄP ( JЄP Cij ( ( i F ai
La notación (i : Significa la suma sobre todos los vértices iDemostración: observe (j ЄP ( iЄP Cji = (j ЄP ( 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
( i F ai= (j ЄP (j Fji -(j ЄP (j
=(j ЄP (iЄP Fji +(j ЄP (iЄP Fji- =(j ЄP (iЄP Fji
=(j ЄP (iЄP Fji -(j ЄP (iЄP Fji- ((j ЄP (iЄP Fji( (j ЄP (iЄP Cji
El corte minimal nos da la minima capacidad del corteefectuado en el grafo.
Nota: 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.
Metodología
En el último grafo...
Presento a su consideración este encarpetado en donde se presentan temas acerca del teorema de corte minimal, los problemas de parear o parejar elementos de un conjunto con elementos de otro conjunto. Se vera que estos problema puede reducirse a encontrar el flujo maximal en una red. También se tratará la existencia de algunos tipos de parejamientos que pueden existir en unared, así como también la forma de expresarlos.
CAPITULO I:
METODOLOGÍA
|PASOS A SEGUIR |LUGAR DE REUNION |FECHA |
|CONOCER LOS TEMAS A TRATAR EN LA INVESTIGACION |CASA DE UN INTEGRANTE |LUNES 21 DE DICIEMBRE DEL |
|| |2004 |
|REVISAR EN LIBROS LOS TEMAS DE INVESTIGACION |CASA DE UN INTEGRANTE |MARTES 28 DE DICIEMBRE |
| | |DEL 2004 |
|RECABARINFORMACION DE CADA UNO DE LOS TEMAS A INVESTIGAR | |DOMINGO 2 DE ENERO DEL |
| |CIBER |2005 |
|SELECCIÓN Y ACOMODACION DE TODA LA INFOMACION RECOLECTADA |CENTRO DE COMPUTO DEL ITESCAM |JUEVES 6 DE DE ENERODEL |
| | |2005 |
|ELABORACION DEL DOCUMENTO EN FORMA GENERAL (DESGLOSADA)CADA TEMA Y |CIBER |MIERCOLES 12 DE ENERO DEL|
|LA COMPRENSION DE ESTOS ||2005 |
CAPITULO II:
TEOREMA DE CORTE MINIMAL
Definición de corte
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 lasuma:
(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:
(i ЄP ( JЄP Cij ( ( i F ai
La notación (i : Significa la suma sobre todos los vértices iDemostración: observe (j ЄP ( iЄP Cji = (j ЄP ( 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
( i F ai= (j ЄP (j Fji -(j ЄP (j
=(j ЄP (iЄP Fji +(j ЄP (iЄP Fji- =(j ЄP (iЄP Fji
=(j ЄP (iЄP Fji -(j ЄP (iЄP Fji- ((j ЄP (iЄP Fji( (j ЄP (iЄP Cji
El corte minimal nos da la minima capacidad del corteefectuado en el grafo.
Nota: 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.
Metodología
En el último grafo...
Leer documento completo
Regístrate para leer el documento completo.