Дополнительные главы теории паросочетаний

Общая информация
ЛекторМ. А. Бабенко
Семестрвесна 2010
Дата начала03.04.2010
Количество пар5
Язык курсарусский
Видеоhttp://video.yandex.ru/users/pdmicsclub/collection/12/
Аннотация Помимо стандартных результатов, которые обычно упоминаются в курсах по комбинаторной оптимизации, будут рассказаны не столь хорошо известные, но красивые аспекты этой теории. Будут приведены как классические, так и совсем свежие результаты данной области. Предварительный список тем:
  1. Простейшие факты и определения. Паросочетания, вершинные покрытия, двойственность. Минимакасная формула Кёнига-Эгервари для двудольного случая. Теорема Холла. Алгоритм построения максимального паросочетания.
  2. Реберные раскраски двудольных графов и их связь с паросочетаниями.
  3. Совершенные паросочетания в регулярных двудольных графах, быстрый алгоритм их построения. Применение к реберным раскраскам. Выделение регулярных и почти-регулярных подграфов в регулярных графах.
  4. Недвудольные паросочетания: формула Татта-Бержа, алгоритм Эдмондса. Теорема Петерсена.
  5. Структура максимальных паросочетаний, структурная теорема Эдмондса-Галлаи.
  6. 2-паросочетания. 2-парсочетания с ограничениями. Минимаксные формулы и быстрые алгоритмы их нахождения максимальных 2-паросочетаний без треугольников в общем и регулярном случае.
  7. Алгебраические алгоритмы поиска максимальных паросочетаний.
Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

Ваша оценка: Пусто Средняя: 4.3 (6 votes)
Share |
Максим Бабенко