Московский Государственный Институт Делового Администрирования
КУРСОВАЯ РАБОТА
На тему: «Транспортные сети. Задача о максимальном потоке в сети»
Работу
выполнила: Болотина Юлия
Работу
проверил: Аллавердиев А.М
Москва 2003
Содержание
Введение………………………………………………………………3стр
Теоретическая часть………………………………………..………. 4стр
Теорема Форда-Фалкерсона………………………………………….
Алгоритм решения…………………………………………………….5стр
Поток в транспортной сети…………………………………………..7стр
Орграф приращений…………………………………………………10стр
Алгоритм построения максимального потока
В транспортной сети………………………………………………10стр
Практическая часть…………………………………………….. .…12стр
Этап 1…………………………………………………………………12стр
Этап 2………………………………………………………………… 13стр
Этап 3………………………………………………………………….13стр
Этап 4………………………………………………………………….14стр
Этап 5…………………………………………………………………14стр
Заключение…………………………………………………………..16стр
Список используемой литературы……………………………..…..17стр
Введение.
В своей курсовой работе я рассматриваю тему «Транспортные сети». Моя
курсовая работа состоит из следующих разделов:
• Транспортные сети;
• Поток в транспортной сети;
• Орграф приращений;
• Алгоритм построения максимального потока в транспортной сети и т.д.
В задаче, которую я рассматриваю, да и вообще в задачах на данную тему
фундаментальную роль играет изучение поперечных сечений сети (то есть
множеств дуг, которые соединяют вершины двух не пересекающихся множеств
вершин) и нахождение ограниченного поперечного сечения, которое является
самым узким местом. Эти узкие места определяют пропускную способность
системы в целом.
ТЕОРЕТИЧЕСКАЯ ЧАСТЬ:
), называемое пропускной способностью дуги, и существует:
, в которую не заходит ни одна дуга, называемая источником или началом
сети;
, из которой не выходит ни одной дуги; эта вершина называется стоком
или концом сети.
Потоком сети называется неотрицательная функция f(1) такая, что f(e)
меньше или равно c(e). (Поток не может превышать пропускную способность
дуги.)
(Поток называется полным, если содержит насыщенную дугу f(e)=c(e).)
Разрезом L сети G(V,E) называется множество насыщенных дуг, отделяющих
источник s от стока t.
Теорема Форда-Фалкерсона.
.
. Тогда выполняется равенство
(1)
. Но тогда из (1) получаем
Следствие 1. Используя теорему Форда-Фалкерсона получаем, что величина
максимального потока в транспортной сети равна пропускной способности
минимального разреза.
– максимальный поток.
Алгоритм решения.
Сначала будем строить полный поток, затем проверим, можно ли его
увеличить. Если нет, то этот поток является максимальным. Если же его
можно увеличить, то будем строить другой полный поток и т.д. Решать
задачу будем с помощью метода расстановки пометок.
Две основные процедуры (операции алгоритма):
( операция расстановки пометок;
( операция изменения потока.
– натуральное число или бесконечность. Вообще возможны три состояния
вершины:
не помечена;
помечена, но не просмотрена;
помечена и просмотрена.
Источник помечен, но не просмотрен. Остальные вершины не помечены.
Чтобы источник S был помечен и просмотрен, надо поместить все вершины,
смежные с S.
.
. Далее просматриваем следующую вершину, и так до тех пор, пока не
пометим сток t или же пока нельзя будет больше пометить ни одной
вершины, сток при этом останется не помеченным. Если сток окажется не
помеченным, то процесс нахождения максимального потока в сети можно
считать законченным, а если сток помечен, то нужно переходить к
процедуре 2.
Переходим к следующей вершине и так до тех пор, пока не достигнем
источника S. Здесь изменение потока прекращается. Далее переходим к
процедуре 1 и так до тех пор, пока величину потока уже нельзя изменить.
Рассмотрим конкретную задачу о нахождении максимального потока в
сети.
Дана сеть G(V,E) (рис. 11) с источником S и стоком t. Пропускные
способности дуг указаны. Найти максимальный поток из S в t.
Поток в транспортной сети.
, определенная на множестве X дуг транспортной сети D и принимающая
целочисленные значения, называется допустимым потоком (или просто
потоком) в транспортной сети D, если:
;
•для любой промежуточной вершины v выполняется равенство
т.е. сумма потоков по дугам, заходящим в v, равна сумме потоков по
дугам, исходящим из v.
).
в транспортной сети D выполняется равенство:
имеем:
), что в сумме даёт нулевой вклад в левую часть равенства (2). Учитывая
сказанное, заключаем, что из равенства (2) следует справедливость
равенства (1).
, или, что то же самое – величина, равная сумме потоков по всем дугам,
исходящим из
содержит, по крайней мере, одну насыщенную дугу.
принимает максимальное значение по сравнению с другими допустимыми
потоками в транспортной сети D.
, что противоречит условию максимальности потока). Обратная же, вообще
говоря, неверно. Существуют полные потоки, не являющиеся максимальными.
Тем на менее полный поток можно рассматривать как некоторое приближение
к максимальному потоку.
Орграф приращений.
:
равна либо 0, либо бесконечности.
Алгоритм построения максимального потока в транспортной сети.
Важным следствием теоремы Форда-Фалкерсона является Алгоритм построения
максимального потока в транспортной сети.
Алгоритм:
).
.
и переходим к шагу 2.
ПРАКТИЧЕСКАЯ ЧАСТЬ:
Задача о максимальном потоке.
Для заданной транспортной сети определить величину максимального потока
грузов, которые можно доставить в течение заданного времени из города S
в город t. Пропускные способности всех участков дорог считаются
известными.
Этап 1.
Припишем около каждой дуги после значения пропускной способности
значение первоначального потока.
Просмотрим вершину S, для этого пометим вершиныV , V , V .
.
Изменение потока:
Поэтому заменим величину первоначального потока:
,
Этап 2.
. Просмотрим V2, V4 уже помечена,
Изменение потока:
Вносим изменения потока. Дуга (V2, t) стала насыщенной.
Этап 3.
Просмотрим вершину V1. Вершины V4 и V2 получают метки
Просмотрим V3, V2 уже помечена, Просмотрим
V2, V4 уже помечена, Просмотрим V4,
Изменение потока:
Вносим изменения потока. Дуга (V3,V2) стала насыщенной.
Этап 4.
Просмотрим вершину V3. Вершины V2 и V3 получают метки
Просмотрим V2. Вершины V4, V5 и t получают метки
Изменение потока:
Вносим изменения потока. Дуга (V3, V2) стала насыщенной.
Этап 5.
Просмотрим вершину V3. Вершина V6 получает метку
Просмотрим V6
Изменение потока:
Вносим изменения потока. Дуга (S,V3) стала насыщенной.
составляют минимальный разрез сети. Минимальный разрез на рисунке
обозначен волнистой линией.
Заключение.
Бурное развитие дискретной математики обусловлено прогрессом
компьютерной техники, необходимостью создания средств обработки и
передачи информации, а также представления различных моделей на
компьютерах, являющихся по своей природе конечными структурами.
), называемое пропускной способностью дуги, и существует:
, в которую не заходит ни одна дуга, называемая источником или началом
сети;
, из которой не выходит ни одной дуги; эта вершина называется стоком
или концом сети.
Список используемой литературы
1. А.М. Аллавердиев, И.В. Платонова «Прикладная математика. Элементы
теории графов» М.2000
2. Лекции по прикладной математике И.В. Платоновой
3. В.Н. Нефедов, В.А. Осипова «Курс дискретной математики» М. 1992
4. С.В. Судоплатов, Е.В. Овчинникова «Элементы дискретной математики» М.
2002
PAGE
PAGE 2
Нашли опечатку? Выделите и нажмите CTRL+Enter
