Паросочетания

Четверг, 20 апреля 2017
Таймс, ауд. 405

Описание

  • Лемма о дополняющем пути

  • Алгоритм Куна

  • Теорема Кёнига, поиск минимального вершинного покрытия

  • Связь: вершинное покрытие, независимое множество, клика

  • Лемма Холла, существование совершенного паросочетания в регулярном двудольном графе