City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Matchings
Saint Petersburg / spring 2010, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

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

Видео лекций: https://www.lektorium.tv/course/22771