TEOREMA DE CORTE MINIMAL

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 una red, 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

RECABAR INFORMACION DE CADA UNO DE LOS TEMAS A INVESTIGAR

CIBER DOMINGO 2 DE ENERO DEL 2005

SELECCIÓN Y ACOMODACION DE TODA LA INFOMACION RECOLECTADA CENTRO DE COMPUTO DEL ITESCAM JUEVES 6 DE DE ENERO DEL 2005

ELABORACION DEL DOCUMENTO EN FORMA GENERAL (DESGLOSADA)CADA TEMA Y LA COMPRENSION DE ESTOS CIBER MIERCOLES 12 DE ENERO DEL 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 la suma:

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 i

Demostració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 corte efectuado 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 del algoritmo de flujo maximal, de todos los cortes posibles, serán cortes minimales aquellos que estén formados por aristas en las que el valor de la capacidad coincida con el valor del flujo. Para mejor comprensión ver ejemplo:

PAREOS O PAREJAMIENTOS

Este es un problema puede reducirse a encontrar el flujo maximal en una red:

A J1

J2

B

J3

C

J4

D

J5

A=J2 Y J5

B=J2 Y J5

C=J1, J3, J4 Y J5

D=J2 Y J5

Supóngase que 4 personas A, B, C, y D llenan solicitudes para cinco trabajadores j1,j2, j3, j4 y j5. Considérese que el solicitante está calificado para A=j2 y j5, el B esta calificado B=j2 y j5, el C=j1, j3, j4 , j5 y el D= j2 y j5

La situación puede ser modelada por el grafo de la figura anterior donde los vértices representan a los solicitantes y a los trabajos. Un lado une a un solicitante con el trabajo para el cual esta calificado. Es posible demostrar que no se puede parear un trabajo con cada solicitante; basta considerar que A, B y D están calificados solo para los trabajo J2 y J5. Si A y B se les asigna un trabajo, no queda trabajo alguno para D. Por lo tanto no existe asignación de trabajo para A, B, C y D.

En el ejemplo anterior consiste en hallar trabajos para las personas calificadas.

...