Лекция по дискретной математике №15. Алгоритм поиска в ширину. Паросочетания. Поиск максимального.

Описание

МИЭТ
Таймкоды:
0:00 Начало.
1:00 Поиск в ширину на ориентированном графе.
11:00 Паросочетания.
14:10 Наибольшее, максимальное и совершенное паросочетание.
19:00 Применение паросочетаний.
23:38 Задача о наибольшем паросочетании.
27:10 Увеличивающиеся цепи.
30:25 Паросочетание наибольшее, если в графе нет увеличивающих цепей.
36:20 Алгоритм построения наибольшего паросочетания.
39:20 Пример алгоритма.
50:00 Задача о назначениях.
52:45 Свойство задачи о назначениях(уменьшение весов строки/столбца)
1:01:00 АБ-альфа преобразование
1:03:50 Алгоритм построения совершенного паросочетания.