Acoplamiento En Graficas Bipartidas

UNIVERSIDAD DE SONORA
DEPARTAMENTO DE MATEMÁTICAS

BIBLIOTECA
LEsa S
CroCruSmEXA
01
viw iams
AulzipcLatA isvus
,,Iiish

INDICE
INTRODUCCION

1

CAPITULO I: Problema de Acoplamiento
Descripción del problema
Acoplamiento de cardinalidad máxima
Acoplamiento con peso
Métodos de solución del problema de acoplamiento

3
5
11
18

CAPITULO II: Problema deacoplamiento de cardinalidad máxima
Conceptos básicos
Acoplamiento
Teorema de Hall y Acoplamiento perfecto
Problema de cubierta mínima
Descomposición en cadenas
Implementación computacional

21
24
28
31
32
35

CAPITULO III: Problema de acoplamiento con peso
Introducción
Paradoja al problema de asignación
Conceptos básicos
Problema de asignación y su dual
Fundamentosteóricos (caso cuadrado)
Algoritmo Húngaro
Asignación máxima
Convergencia del algoritmo Húngaro
9) Implementación computacional

45
45
47
49
50
56
57
58
59

CONCLUCION

66

APENDICE A

67

APENDICE B

69

BIBLIOGRAFIA

76

INTRODUCCION
La palabra acoplamiento significa literalmente formar parejas. Si
se tiene un conjunto finito de elementos con los quese pueden formar
parejas, se representa la situación con una gráfica que tenga un
vértice por cada elemento, donde una arista entre dos vértices
significa que los elementos representados por tales vértices pueden
forman pareja, pero además las parejas no deben tener un vértice en
común.
En los problemas de acoplamiento en gráficas, la idea más general
consiste en encontrar subconjuntos dearistas que cumplen ciertos
criterios de optimización, donde los parámetros involucrados pueden
ser el número de aristas en la solución, el número de vértices que son
extremos del total de aristas o el peso asociado a las aristas. En
éste trabajo sólo se estudiarán dos tipos de problemas de acoplamiento
los cuales son: Acoplamiento de Cardinalidad Máxima y Acoplamiento con
Peso (problema deasignación), ambos en gráficas bipartitas.
Los problemas de acoplamiento se estudiaron por mucho tiempo
tanto en Análisis Combinatorio como en Investigación de Operaciones,
llamando la atención de muchos investigadores interesados por sus
múltiples aplicaciones tales como: sistema de representantes
distintos, problema de cubrimiento, descomposición en cadenas,
cuadrados latinos, problema delmatrimonio, calendarización de vuelos,
enrole de locomotoras, etc. y sus diversas variantes. Sin embargo, en
1957 Claude Berge fué el primero en plantear estos problemas usando el
concepto de trayectoria aumentante. El demostró que un acoplamiento es
máximo si y sólo si no hay trayectoria aumentante, éste es un
resultado clásico de Optimización Combinatoria el cual es la base de
losalgoritmos más eficientes para resolver los problemas de
acoplamiento.
El método Húngaro para la solución del problema de acoplamiento
con peso (problema de asignación) está fundamentado en el trabajo de
dos Matemáticos Húngaros, D. Kóning y J. Egerváry, y particularmente
en el teorema dado por Kóning, este teorema fué establecido y
demostrado en términos de teoría de gráficas. Una prueba de ésteteorema usando teoría de gráficas fué dada por Kuhn en 1955 quien
desarrolló un algoritmo para obtener n ceros independientes (en
distinto renglón y distinta columna) de una matriz obteniendo un
acoplamiento de cardinalidad máxima en una gráfica bipartita asociada.
Este algoritmo está basado en el trabajo de los matemáticos Húngaros
Kóning y Egerváry. En honor a ellos le llamó a éste MétodoHúngaro o
Algoritmo Húngaro. Este trabajo condujo al siguiente año, al método
primal-dual para obtener el acoplamiento de peso máximo en gráficas
generales.
Este trabajo tiene por objeto el análisis y desarrollo de los
fundamentos teóricos de los principales métodos de solución de
problemas de acoplamientos. Así como su implementación para la
solución de problemat de aplicación.

1...