Алгоритмы и структуры данных 12. Алгоритм Диница

Таймкоды: 00:00:00 - Интро 00:00:05 - Алгоритм Диница (Dinitz) 00:00:40 - Напоминание про работу Э-К 00:03:55 - Идея алгоритма Диница 00:05:50 - Слоистая сеть (Определение) 00:07:50 - Блокирующий поток (Определение) 00:08:30 - Пример 00:09:45 - Алгоритм Диница 00:13:30 - Как искать блокирующие поток в слоистой сети 00:32:30 - Асимптотика 00:40:30 - Лемма 00:45:30 - Следствие 00:48:30 - Теорема (б/д) (Диниц с масштабированием) 00:49:20 - Теоремы (Карзанова) 00:51:40 - Первая теорема Карзанова 00:52:50 - Лемма 1 00:55:40 - Лемма 2 01:04:35 - Доказательство теоремы Карзанова 01:11:20 - Вторая теорема Карзанова 01:13:00 - Утверждение (Единичные сети) 01:18:00 - Исправление кода 01:19:00 - Продолжаем 01:20:10 - Алгоритм Хопкрофта-Карпа (Поиск максимального паросочетания в двудольном графе) 01:23:10 - Утверждение (О декомпозиции потока) Дата лекции: 21.04.26 Лектор: Степанов Илья Данилович Оператор: Пахомов Михаил Монтажёр: Пахомов Михаил Плейлист на YouTube: https://www.youtube.com/playlist?list=PL4_hYwCyhAvZcovb3rsD3_g1fIQIAOZVg Плейлист в ВК: https://vkvideo.ru/playlist/-206078025_234