Лекция 5. Теория графов. Задачи о максимальном потоке и минимальном разрезе.

Курс лекций по математическим методам принятия решений Запись дистанционных лекций на специальности бизнес-информатика Плейлист со всеми лекциями и семинарами курса:    • Математические методы принятия решений   0:00 Начало 1:52 Теория: сети и потоки 10:03 Задача о максимальном потоке 10:56 Построение сети 11:41 Вход и выход сети 14:20 Пропускные способности дуг 16:34 Матрица смежности 17:20 Переменные 17:55 Алгоритм Форда-Фалкерсона 20:56 Целевая функция 22:08 Ограничения 20:40 Результаты решения 27:48 Задача о минимальном разрезе 27:58 Теория: разрезы 31:31 Теорема Форда-Фалкерсона 35:00 Алгоритм Штор-Вагнера 36:39 Матрица инцидентности 38:20 Переменные 39:37 Теория: потенциалы вершин 41:28 Целевая функция 42:18 Ограничения 45:07 Результаты решения 47:03 Модернизация сети 52:48 Л. Форд, Д. Фалкерсон и Корпорация RAND 57:56 Задание на семинар