Лекция по дискретной математике №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 Алгоритм построения совершенного паросочетания.