EMPAREJAMIENTOS EN GRAFOS BIPARTITOS: En torno al TEOREMA DE HALL. Teoremas minimax. Programación lineal y principio de dualidad. Emparejamientos perfectos. Rectángulos latinos. Algoritmos para grafos bipartitos

Description

Prólogo

Capítulo 1. Teoremas minimax
1.1. Teorema de Menger
1.1.1. Teorema de Menger para vértices
1.1.2. Teorema de Menger para aristas
1.1.3. Teorema de Menger para digrafos
1.2. Teorema de Hall
1.3. Teorema húngaro
1.4. Teorema de Dilworth
1.4.1. Teorema dual del teorema de Dilworth

Capítulo 2. Generalizaciones
2.1. Transversales
2.2. Matroides
2.2.1. Función rango
2.3. Matroide transversal
2.4. Teorema de Rado
2.5. Transversales comunes

Capítulo 3. Programación lineal y principio de dualidad
3.1. Conceptos generales
3.2. Matrices absolutamente unimodulares
3.3. Emparejamientos máximos
3.4. Flujo máximo

Capítulo 4. Aplicaciones en diversos problemas
4.1. Emparejamientos perfectos en grafos bipartitos regulares
4.2. Rectángulos latinos
4.3. Criterio de Ryser
4.4. Matrices doblemente estocásticas
4.5. Coloración de aristas de un grafo
4.6. Conexidad por vértices y por aristas
4.7. Teorema de Erdos

Capítulo 5. Algoritmos para grafos bipartitos
5.1. Teorema de Berge
5.2. Búsqueda de un emparejamiento máximo
5.3. Búsqueda de un recubrimiento de vértices mínimo
5.4. Algoritmo húngaro
5.5. Problema de asignación de cuello de botella

Capítulo 6. Problemas

Bibliografía

Índice de autores

Índice de materias