Дискретная математика (Обход графа, Алгоритм Форда – Фалкерсона и т.д. и т.п), страница 8
Описание файла
Файл "Дискретная математика" внутри архива находится в папке "Обход графа, Алгоритм Форда - Фалкерсона и т.д. и т.п". Документ из архива "Обход графа, Алгоритм Форда – Фалкерсона и т.д. и т.п", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 3 семестр, которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "дискретная математика" в общих файлах.
Онлайн просмотр документа "Дискретная математика"
Текст 8 страницы из документа "Дискретная математика"
Продолжение таблицы
Окончание таблицы
8. Алгоритм Форда – Фалкерсона
-
S = {1}; T = {2, 3, 4, 5};
Р+: (1, 2); (1, 4)
Максимальный поток: 5 -
S = {1, 3}; T = {2, 3, 4, 5};
Р+: (3, 4); (3, 5)
Максимальный поток: 7 -
S = {1}; T = {2, 3, 4, 5};
Р+: (1, 2); (1, 3); (1, 4)
Максимальный поток: 7 -
S = {1, 4}; T = {2, 3, 5};
Р+: (1, 2); (1, 3); (1, 4); (4, 5)
Максимальный поток: 7 -
S = {1}; T = {2, 3, 4, 5};
Р+: (1, 2); (1, 4)
Максимальный поток: 6 -
S = {1, 2, 3}; T = {4, 5};
Р+: (1, 5); (3, 4)
Максимальный поток: 6 -
S = {1, 2, 3, 4}; T = {5};
Р+: (1, 5); (2, 5); (4, 5)
Максимальный поток: 7 -
S = {1}; T = {2, 3, 4, 5};
Р+: (1, 3); (1, 5)
Максимальный поток: 6 -
S = {1, 2, 3, 4}; T = {5};
Р+: (1, 5); (2, 5); (4, 5)
Максимальный поток: 6 -
S = {1, 4}; T = {2, 3, 5};
Р+: (1, 3); (1, 5); (4, 5)
Максимальный поток: 10 -
S = {1}; T = {2, 3, 4, 5};
Р+: (1, 2); (1, 4)
Максимальный поток: 10 -
S = {1, 3}; T = {2, 3, 4, 5};
Р+: (1, 2); (1, 4); (1, 5); (3, 4)
Максимальный поток: 7 -
S = {1}; T = {2, 3, 4, 5};
Р+: (1, 3); (1, 5)
Максимальный поток: 8 -
S = {1, 2, 3, 4}; T = {5};
Р+: (3, 5); (4, 5)
Максимальный поток: 9 -
S = {1}; T = {2, 3, 4, 5};
Р+: (1, 2); (1, 3); (1, 5)
Максимальный поток: 9 -
S = {1, 4}; T = {2, 3, 5};
Р+: (1, 2); (1, 5); (4, 5)
Максимальный поток: 8 -
S = {1}; T = {2, 3, 4, 5};
Р+: (1, 2); (1, 4); (1, 5)
Максимальный поток: 10 -
S = {1}; T = {2, 3, 4, 5};
Р+: (1, 3); (1, 4); (1, 5)
Максимальный поток: 6 -
S = {1}; T = {2, 3, 4, 5};
Р+: (1, 2); (1, 3); (1, 4)
Максимальный поток: 8 -
S = {1}; T = {2, 3, 4, 5};
Р+: (1, 2); (1, 4)
Максимальный поток: 8 -
S = {1, 2, 4}; T = {3, 5};
Р+: (2, 5); (4, 5)
Максимальный поток: 6 -
S = {1, 2}; T = {3, 4, 5};
Р+: (1, 5); (2, 4); (2, 5)
Максимальный поток: 7 -
S = {1, 2}; T = {3, 4, 5};
Р+: (1, 5); (2, 4); (2, 5)
Максимальный поток: 7 -
S = {1, 3}; T = {2, 4, 5};
Р+: (1, 2); (1, 5); (3, 4)
Максимальный поток: 9
содержание
-
Предисловие
-
Введение
-
Определение графа
-
Диаграммы
-
Смежность
-
Изоморфизм
-
Основные примеры графов. Маршруты, подграфы, связность
-
Расстояние в графе
-
Операции над графами
-
Матричное задание графов
-
Матрица связности. Слабая и сильная связность.
-
Обход графов в ширину и глубину
-
Описание алгоритма
-
Пример
-
Задания
-
Алгоритм Тэрри
-
Описание алгоритма
-
Пример
-
Задания
-
Матроиды. Жадные алгоритмы. Алгоритм Краскала.
-
Описание алгоритма
-
Пример
-
Задания
-
Сетевые алгоритмы. Выбор кратчайшего пути
-
Нахождение кратчайшего пути в сети без контуров
-
Описание алгоритма
-
Пример
-
Задания
-
Алгоритм Беллмана – Форда
-
Описание алгоритма
-
Пример
-
Задания
-
Алгоритм Дейкстра
-
Описание алгоритма
-
Пример
-
Задания
-
Алгоритм Флойда – Уоршела
-
Описание алгоритма
-
Пример
-
Задания
-
Алгоритм Форда – Фалкерсона
-
Описание алгоритма
-
Пример
-
Задания
-
Ответы
11