Кубенский А.А. Дискретная математика. Графы

27 слайдов.
(Выходные данные отсутствуют). Содержание:
Алгоритм Флойда-Уоршалла.
Транзитивное замыкание графа отношения. Алгоритм «умножения матриц».
Алгоритм «умножения матриц».
Алгоритм Джонсона для разреженных графов.
Построение минимального скелета нагруженного графа. Алгоритм Прима.
Построение минимального скелета нагруженного графа. Алгоритм Крускала.
Сети и потоки.
Формальное определение потока.
Лемма о потоке в сети.
Остаточная сеть.
Метод Форда – Фалкерсона.
Теорема о минимальном разрезе.
Пример реализации метода Форда – Фалкерсона.
Анализ метода Форда – Фалкерсона.
Сеть с несколькими истоками и стоками.
Максимальное паросочетание в двудольном графе.
Применение метода Форда – Фалкерсона для нахождения максимального паросочетания.
Задача коммивояжера.
Алгоритмы решения задачи коммивояжера.