Алгоритмы и структуры данных 11. Паросочетания. Покрытия и независимые мн-ва

Введение в программирование, алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики

Лекция прочитана 14 апреля 2022 года
Лектор: Степанов Илья Даниилович
Оператор: Жулябина Ирина
Монтаж: Жильцов Игорь

0:00 - Определения: парсоч, увеличивающий путь, чередование вдоль него
12:17 - Теорема Бержа
13:50 - Д-во "слева направо"
14:50 - "Справа налево" Лемма. Структура компонент связности в неорграфе с вершинами степени не больше 2
20:10 - Непосредственно д-во
33:17 - Алгоритм поиска максимального парсоча
34:32 - Алгоритм Куна (для двудольного графа)
48:20 - Корректность. Лемма. Чередование не создаёт новые увеличивающие пути
57:20 - Разбираем разные случаи
1:01:40 - Независимые множества и вершинные покрытия
1:03:49 - Пример
1:04:50 - Упражнение. X - независимое мн-во т. и т. т., к. V \ X - вершинное покрытие
1:05:45 - Поиск максимального независимого мн-ва и минимального вершинного покрытия в двудольном графе
1:10:10 - L+, L-, R+, R-
1:11:05 - Теорема Кёнига: L+ U R- = max независимое, L- U R+ = min покрытие
1:12:10 - Д-во: покажем, что L+ U R- - это какое-то независимое мн-во (т. е. L- U R+ - какое-то покрытие)
1:16:06 - Докажем, что L- U R+ минимально среди покрытий
1:17:43 - |L- U R+| ≤ |M|
1:21:46 - ∀ покрытия Cov: |M| ≤ |Cov|