Minimal Pareos

INTRODUCCIÓN

Este trabajo esta formado por dos temas, el primero lleva por nombre “Teorema de Corte Minimal” y el otro “Pareo” o “Emparejamiento que viene siendo lo mismo.

En la primera parte se da una explicación de dicho tema y una demostración de cómo se origina el teorema, también mencionamos algo del flujo maximal ya que se relaciona con el corte minimal.

En la segunda parte se habló de el “Pareo” en el que se explica que a cada elemento X le corresponde uno o más elementos de Y, y a Y sólo le corresponde un elemento de X; se definen tres tipos de emparejamiento (mínimo, máximo y perfecto). Incluimos algunos dibujos en el tema de emparejamiento para su fácil comprensión.

METODOLOGIA

Este trabajo de investigación se logro a base de consulta en libros y paginas de Internet.

Lo primero que se realizó fue visitar varias páginas del buscador de Google de Internet en la cual no se encontró información relacionada con el tema que deberíamos desarrollar. Después visitamos el buscador de altavista en el cual encontramos el tema de emparejamiento ya que es el otro nombre que recibe el tema de pareo.

Luego visitamos la biblioteca de la escuela y consultamos en un libro de Matemáticas para computadora en el cual encontramos más información.

También cada integrante del equipo, anteriormente hizo lo posible por encontrar información sobre el tema que desarrollamos.

Se reunió y recopiló toda la información encontrada y se resumió para poder estructurar el tema. Una vez que se realizó este paso se prosiguió a realizar cada parte que debe contener el trabajo de investigación documental.

2.1 TEOREMA DE CORTE MINIMAL

Definición de corte y capacidad de un corte. Propiedad: v(f)=f(S,S')-f(S',S).

Corolario: el valor de cualquier flujo es menor o igual que la capacidad de cualquier corte. Corolario: Si el valor de un flujo es igual a la capacidad de un corte entonces el flujo es maximal y el corte es minimal.

Teorema: Existen flujos maximales. Algoritmo ``Naive'' para encontrar un flujo maximal. Ejemplo donde funciona. Ejemplo donde falla. Como modificar el algoritmo para que funcione. Construcción de S (f). Prueba del Max-Flow-Min-Cut Theorem. Algoritmo de escaneo-etiqueteado de Ford-Fulkerson. Ejemplos de aplicación del algoritmo de Ford-Fulkerson. Complejidad del algoritmo si los vértices se etiquetean al azar. Complejidad del algoritmo si los vértices se etiquetean ``scan-first-label-first''. Ejemplo de que la complejidad puede ser desastrosa si no se usa el último método. Aplicaciones del Algoritmo. Refinamientos: Algoritmo de Dinic. Complejidades.

DEFINICIÓN: si N= (V, E) es una red de transporte y C es un conjunto de corte para el grafo no dirigido asociado con N, entonces C es un corte, o corte a-z, si la eliminación de las aritas de C de la red produce la separación de a y z.

TEOREMA: Sea f un flujo en una red N= (V, E). Si C (P, P) es cualquier corte en N, entonces val(f) puede exceder a c = .

Demostración: Sea el vertice a la fuente de N y el vertice z su sumidero:Como ge(a)=0 se sigue que para cualquier wε V,f(w,a)= 0. En concecuencia,

Val (f)= ∑ f (a,U)=∑ f(a,U) - ∑ f(w,a).

uεv uεv wεv

Por la condición (b) en la definición de un flujo, para cualquier x ε P,x≠a,∑uεvf(x, U) ∑wεvf(w,x)=0.

Si sumamos los resultados de las ecuaciones anteriores obtenemos

val(f) = [∑f(a,U) - ∑f(w,a) ] + ∑ [∑f(x,U) - ∑f(w,x)]

uεv wεv xεP uεv wεv

= ∑f(x,U) - ∑f(w,x)

xεP xεP

uεv wεv

= [∑f(x,U) - ∑f(x,U) ] + ∑ [∑f(w,x) - ∑f(w,x)]

xεP xεP xεP xεP

uεv UεP wεP wεP

Como sumamos

= ∑f(x,U) -y ∑f(w,x)

xεP xεP

...