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