В настоящем пособии рассматривается теорема Ф.Холла о системе различных представителей, решающая задачу о свадьбах, и эквивалентные ей теоремы Менгера, Дилворта, Кёнига---Эгервари, Форда---Фалкерсона. Показано, что эти теоремы являются проявлением принципа двойственности в линейном программировании. Приведен также венгерский алгоритм решения задачи о назначениях.

Книга ориентирована на студентов специальностей "Математика", "Прикладная математика", "Прикладная математика и информатика", "Программная инженерия", изучающих дискретную математику и дискретную оптимизацию.

Оглавление

Предисловие

Минимаксные теоремы

1.1. Теоремы Менгера

1.1.1. Вершинная форма

1.1.2. Рёберная форма

1.1.3. Теоремы Менгера для орграфов

1.2. Теорема Холла

1.3. Венгерская теорема

1.4. Теорема Дилворта

2. Обобщения

2. 1. Трансверсали

2.2. Понятие матроида

2.3. Трансверсальный матроид

2.4. Теорема Радо

2.5. Общие трансверсали

3. Линейное программирование и принцип двойственности

3.1. Общие сведения

3.2. Абсолютно унимодулярные матрицы

3.3. Наибольшие паросочетания

3.4. Максимальный поток

4. Приложения к различным задачам

4.1. Совершенные паросочетания в регулярных двудольных графах

4.2. Латинские прямоугольники

4.3. Критерий Райзера

4.4. Дважды стохастические матрицы

4.5. Рёберная раскраска графов

4.6. Вершинная и рёберная Связность

4.7. Теорема Эрдёша

5. Алгоритмы для задач о двудольных графах

5.1. Теорема Бёржа

5.2. Нахождение наибольшего паросочетания

5.3. Нахождение наименьшего вершинного покрытия

5.4. Венгерский алгоритм

5.5. Задача о назначениях на узкое место

6. Упражнения

Ответы Указания. Решения

Литература

Предисловие

Данное учебное пособие является расширенным вариантом гл.LXXI учебника [5] и посвящено ряду замечательных результатов теории графов, которые были получены в 30--50-х годах прошлого столетия различными математиками, и которые, как выяснилось впоследствие, эквивалентны друг другу: каждая из этих теорем может быть выведена из любой другой.

В комбинаторном анализе и теории сложности вычислений (как и вообще в математике) важнейшей является идея сведения одной задачи к другой. Поэтому интересно показать, как внешне различные утверждения переходят друг в друга в результате построения некоторых дополнительных конструкций. Понимание таких переходов и преобразований важно и для программистов: зная, как одна задача сводится к другой, можно алгоритм решения первой задачи преобразовать в алгоритм решения второй задачи.

В пособии, помимо формулировок и различных доказательств теорем Холла, Менгера, Дилворта, Форда--Фалкерсона, Кёнига--Эгервари,

* рассматривается их обобщение (критерий существования независимой трансверсали теорема);

* устанавливается связь данных теорем с теорией двойственности в линейном программировании;

* приводятся примеры задач, эффективно решаемых с помощью этих теорем;

* обсуждаются некоторые алгоритмы, связанные с двудольными графами (при этом упор делается не на технических деталях, а на принципиальных моментах);

* имеются задачи для самостоятельного решения.

За рамками пособия остались критерий существования совершенного паросочетания в произвольном (не двудольном) графе (теорема Татта) и алгоритмы поиска наибольшего паросочетания в произвольном графе. Для изучения этих вопросов читатель может обратиться к книгам [11] и [15].

Первое издание вышло в 2004 г. в издательстве ЮУрГУ. Во втором издании более подробно разбирается задача о пополнении латинских

квадратов (приведено новое доказательство критерия Райзера), добавлены новые задачи (с решениями), обновлён библиографический список.