Транспортные сети. Задача о максимальном потоке в сети
Курсовая работа, 08 Марта 2014, автор: пользователь скрыл имя
Краткое описание
В своей курсовой работе я рассматриваю тему «Транспортные сети». Моя курсовая работа состоит из следующих разделов:
• Транспортные сети;
• Поток в транспортной сети;
• Орграф приращений;
• Алгоритм построения максимального потока в транспортной сети и т.д.
Содержание
Введение………………………………………………………………3стр
Теоретическая часть………………………………………..………. 4стр
Теорема Форда-Фалкерсона………………………………………….
Алгоритм решения……………………………………………...…….5стр
Поток в транспортной сети…………………………………………..7стр
Орграф приращений…………………………………………………10стр
Алгоритм построения максимального потока
В транспортной сети………………………………………………10стр
Практическая часть…………………………………………….. .…12стр
Этап 1…………………………………………………………………12стр
Этап 2………………………………………………………………... 13стр
Этап 3………………………………………………………………....13стр
Этап 4……………………………………………………………...….14стр
Этап 5…………………………………………………………………14стр
Заключение…………………………………………………………..16стр
Список используемой литературы……………………………..…..17стр
Прикрепленные файлы: 1 файл
Транспортные сети. Задача о максимальном потоке в сети.doc
— 319.59 Кб (Скачать документ)Просмотрим V6
Изменение потока:
Вносим изменения потока. Дуга (S,V3) стала насыщенной.
Поток f=21 является максимальным, а множество дуг составляют минимальный разрез сети. Минимальный разрез на рисунке обозначен волнистой линией.
Заключение.
Бурное развитие дискретной математики обусловлено прогрессом компьютерной техники, необходимостью создания средств обработки и передачи информации, а также представления различных моделей на компьютерах, являющихся по своей природе конечными структурами.
Транспортной сетью называется конечный Связный орграф G(V, E) без петель, каждой дуге которого поставлено в соответствие некоторое неотрицательное число c( ), называемое пропускной способностью дуги, и существует:
1) ровно одна вершина , в которую не заходит ни одна дуга, называемая источником или началом сети;
- ровно одна вершина , из которой не выходит ни одной дуги; эта вершина называется стоком или концом сети.
Список используемой литературы
1. А.М. Аллавердиев, И.В. Платонова «Прикладная математика. Элементы теории графов» М.2000
2. Лекции по прикладной
3. В.Н. Нефедов, В.А. Осипова «Курс дискретной математики» М. 1992
4. С.В. Судоплатов, Е.В. Овчинникова
«Элементы дискретной