Алгоритмы и структуры данных 9. Паросочетания
00:00 Двудольный граф
02:16 Паросочетание
06:10 Жадный алгоритм (чередование)
08:15 Насыщенная вершина
09:41 Увеличивающий путь
13:00 Теорема Бержа
17:23 О графах с вершинами со степенями ≤ 2
21:34 Доказательство теоремы
31:10 Как ориентировать рёбра
33:00 Псевдокод
44:11 Алгоритм Куна (поиск максимального паросочетания)
46:50 Отсутствие увеличивающего пути
01:02:25 Максимальное независимое множество
01:07:11 Теорема Кёнига
Дата лекции: 03.04.24
Лектор: Степанов Илья Данилович
Оператор: Иван Евтушенко
Монтажёр: Роман Зинин
Плейлист: https://www.youtube.com/playlist?list=PL4_hYwCyhAvanbmRgXMbzOdDPt2ZSb3ht
Видео Алгоритмы и структуры данных 9. Паросочетания канала Лекторий ФПМИ
02:16 Паросочетание
06:10 Жадный алгоритм (чередование)
08:15 Насыщенная вершина
09:41 Увеличивающий путь
13:00 Теорема Бержа
17:23 О графах с вершинами со степенями ≤ 2
21:34 Доказательство теоремы
31:10 Как ориентировать рёбра
33:00 Псевдокод
44:11 Алгоритм Куна (поиск максимального паросочетания)
46:50 Отсутствие увеличивающего пути
01:02:25 Максимальное независимое множество
01:07:11 Теорема Кёнига
Дата лекции: 03.04.24
Лектор: Степанов Илья Данилович
Оператор: Иван Евтушенко
Монтажёр: Роман Зинин
Плейлист: https://www.youtube.com/playlist?list=PL4_hYwCyhAvanbmRgXMbzOdDPt2ZSb3ht
Видео Алгоритмы и структуры данных 9. Паросочетания канала Лекторий ФПМИ
Комментарии отсутствуют
Информация о видео
4 апреля 2024 г. 23:00:20
01:20:21
Другие видео канала
Введение в математический анализ 9. Покрытие множества. Предел функции
Формальные языки и трансляции 9. МП-автоматы
Методы оптимизации 2. Задача оптимизации. Выпуклые функции
Микроэкономика 2 4. Провалы рынка и общественные блага
Случайные процессы 11. Модель страхования Крамера-Лундберга
Математическая логика и теория алгоритмов 6. Лемма Цорна и ее следствия
Программирование на языке С++ (базовый поток) 6. Семантика перемещения II.
![[Допсем] Матлогика 12. Машины Тьюринга](https://i.ytimg.com/vi/gIsaLlKOYJg/default.jpg)
[Допсем] Матлогика 12. Машины Тьюринга
Алгебра и геометрия 4. Жорданова нормальная форма
Теория колец и полей 3. Евклидовы кольца
Функциональный анализ 7. Предкомпактные множества. Линейные нормированные пространства
ТФКП 15. Регулярные ветви многозначных функций.
Введение в математический анализ 1. Действительные числа.
Функциональный анализ 8. Самосопряженные операторы
Функциональный анализ 14. Преобразование Фурье. Свёртка
Интеграл Лебега и теория поля 13. Разные виды сходимости
Алгебра и геометрия 9. Полуторалинейные формы. Эрмитовы и евклидовы пространства
Алгоритмы и структуры данных 5. Суффиксный автомат (продолжение)
Основы вероятности и теория меры 3. Мера на полукольце
Алгоритмы и структуры данных 12. Пересечение полуплоскостей.
