Здравствуйте.

В этот week-end 3-4 апреля в Питерском Computer Science клубе при ПОМИ будет прочитан мини-курс лекций "Дополнительные главы теории паросочетаний".

Лектор: Максим Бабенко, Московский государственный университет.

Язык курса: русский

Посещение свободное

Аннотация

Помимо стандартных результатов, которые обычно упоминаются в курсах по комбинаторной оптимизации,
будут рассказаны не столь хорошо известные, но красивые аспекты этой теории. Будут приведены
как классические, так и совсем свежие результаты данной области.

Предварительный список тем:

1. Простейшие факты и определения. Паросочетания, вершинные покрытия, двойственность. Минимакасная формула Кёнига–Эгервари для двудольного случая. Теорема Холла. Алгоритм построения максимального паросочетания.
   
2. Реберные раскраски двудольных графов и их связь с паросочетаниями.
   
3. Совершенные паросочетания в регулярных двудольных графах, быстрый алгоритм их построения. Применение к реберным раскраскам. Выделение регулярных и почти–регулярных подграфов в регулярных графах.
   
4. Недвудольные паросочетания: формула Татта–Бержа, алгоритм Эдмондса. Теорема Петерсена.
   
5. Структура максимальных паросочетаний, структурная теорема Эдмондса–Галлаи.
   
6. 2–паросочетания.
   
7. 2–парсочетания с ограничениями. Минимаксные формулы и быстрые алгоритмы их нахождения максимальных 2–паросочетаний без треугольников в общем и регулярном случае. Алгебраические алгоритмы поиска максимальных паросочетаний.

Курс состоит из 5 лекций: 2 лекции в субботу (17:20 – 18:55, 19:05 – 20:40) и три в воскресенье (11:15 – 12:50, 13:00 – 14:35, 15:35 – 17:10).

Страница курса.