Реферат: Транспортные сети. Задача о максимальном потоке в сети

Московский Государственный Институт ДеловогоАдминистрирования

КУРСОВАЯРАБОТА

На тему:«Транспортные сети. Задача о максимальном потоке в сети»

Работу выполнила: Болотина Юлия

Работупроверил: Аллавердиев А.М

Москва 2003

Содержание

Введение………………………………………………………………3стр

Теоретическаячасть………………………………………..………. 4стр

ТеоремаФорда-Фалкерсона………………………………………….

Алгоритмрешения……………………………………………...…….5стр

Поток в транспортнойсети…………………………………………..7стр

Орграфприращений…………………………………………………10стр

Алгоритм построения максимальногопотока

В транспортнойсети………………………………………………10стр

Практическая часть…………………………………………….. .…12стр

Этап1…………………………………………………………………12стр

Этап 2…………………………………………………………………13стр

Этап3………………………………………………………………....13стр

Этап4……………………………………………………………...….14стр

Этап5…………………………………………………………………14стр

Заключение…………………………………………………………..16стр

Список используемойлитературы……………………………..…..17стр

Введение.

В своейкурсовой работе я рассматриваю тему «Транспортные сети». Моя курсовая работасостоит из следующих разделов:

• Транспортные сети;

• Поток в транспортной сети;

• Орграф приращений;

• Алгоритм построения максимальногопотока в транспортной сети и т.д.

В задаче,которую я рассматриваю, да и вообще в задачах на данную тему фундаментальнуюроль играет изучение поперечных сечений сети (то есть множеств дуг, которыесоединяют вершины двух не пересекающихся множеств вершин) и нахождениеограниченного поперечного сечения, которое является самым узким местом. Этиузкие места определяют пропускную способность системы в целом.

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ:

Транспортной сетьюназывается конечный Связныйорграф G(V, E) безпетель, каждой дуге которого поставлено в соответствие некотороенеотрицательное число c(<img src="/cache/referats/15102/image002.gif" v:shapes="_x0000_i1025">), называемое пропускнойспособностью дуги, и существует:

1)

ровно одна вершина <img src="/cache/referats/15102/image004.gif" v:shapes="_x0000_i1026">, в которую не заходит ни одна дуга, называемая источником или началом сети;

2)

ровно одна вершина <img src="/cache/referats/15102/image006.gif" v:shapes="_x0000_i1027">, из которой не выходит ни одной дуги; эта вершина называетсястоком или концом сети.

Потоком сетиназывается неотрицательная функцияf(1) такая, что f(e) меньшеили равно c(e). (Поток не может превышать пропускную способностьдуги.)

Дуга <img src="/cache/referats/15102/image008.gif" v:shapes="_x0000_i1028">называется насыщенной потокомf, если <img src="/cache/referats/15102/image010.gif" v:shapes="_x0000_i1029">(Поток называется полным,если содержит насыщенную дугу f(e)=c(e).)

РазрезомL сети G(V,E) называется множество насыщенных дуг, отделяющихисточник sот стока t.

Теорема Форда-Фалкерсона.

ПустьD– транспортная сеть, <img src="/cache/referats/15102/image012.gif" v:shapes="_x0000_i1030"> — допустимый поток вэтой сети, <img src="/cache/referats/15102/image014.gif" v:shapes="_x0000_i1031"> — множество вершин <img src="/cache/referats/15102/image016.gif" v:shapes="_x0000_i1032"> таких, что длинаминимального пути из <img src="/cache/referats/15102/image018.gif" v:shapes="_x0000_i1033"> в <img src="/cache/referats/15102/image020.gif" v:shapes="_x0000_i1034"> в орграфе приращений <img src="/cache/referats/15102/image022.gif" v:shapes="_x0000_i1035"> равна нулю. Тогда,если <img src="/cache/referats/15102/image024.gif" v:shapes="_x0000_i1036">, то <img src="/cache/referats/15102/image012.gif" v:shapes="_x0000_i1037"> — максимальный поток,величина которого равна <img src="/cache/referats/15102/image026.gif" v:shapes="_x0000_i1038">.

Пусть<img src="/cache/referats/15102/image024.gif" v:shapes="_x0000_i1039">. Тогда выполняется равенство

<img src="/cache/referats/15102/image027.gif" v:shapes="_x0000_i1040"><img src="/cache/referats/15102/image029.gif" v:shapes="_x0000_i1041"> (1)

Если <img src="/cache/referats/15102/image033.gif" v:shapes="_x0000_i1043"><img src="/cache/referats/15102/image035.gif" v:shapes="_x0000_i1044"> имеем <img src="/cache/referats/15102/image037.gif" v:shapes="_x0000_i1045"><img src="/cache/referats/15102/image039.gif" v:shapes="_x0000_i1046"> существует путьнулевой длины из <img src="/cache/referats/15102/image041.gif" v:shapes="_x0000_i1047"> в <img src="/cache/referats/15102/image020.gif" v:shapes="_x0000_i1048"><img src="/cache/referats/15102/image044.gif" v:shapes="_x0000_i1049">

Следствие1. Используя теорему Форда-Фалкерсона получаем, что величина максимальногопотока в транспортной сети равна пропускной способности минимального разреза.

Следствие2. Пусть <img src="/cache/referats/15102/image012.gif" v:shapes="_x0000_i1051"> — допустимый поток втранспортной сети D.Тогда, если длина минимального пути из v1 в vnв орграфе приращений <img src="/cache/referats/15102/image022.gif" v:shapes="_x0000_i1052"> равна бесконечности,то <img src="/cache/referats/15102/image012.gif" v:shapes="_x0000_i1053"> — максимальный поток.

Алгоритм решения.

Сначала будем строить полный поток,затем проверим, можно ли его увеличить. Если нет, то этот поток являетсямаксимальным. Если же его можно увеличить, то будем строить другой полный потоки т.д. Решать задачу будем с помощью метода расстановки пометок.

Две основные процедуры (операцииалгоритма):

·

операция расстановкипометок;

·

операцияизменения потока.

Рассмотрим первую процедуру. Для каждойвершины данной сети нужно приписать пометку, которая имеет следующий вид: <img src="/cache/referats/15102/image049.gif" v:shapes="_x0000_i1054"> или <img src="/cache/referats/15102/image051.gif" v:shapes="_x0000_i1055"><img src="/cache/referats/15102/image016.gif" v:shapes="_x0000_i1056"><img src="/cache/referats/15102/image012.gif" v:shapes="_x0000_i1057"> – натуральноечисло или бесконечность. Вообще возможны три состояния вершины:

1)

не помечена;

2)

помечена, но не просмотрена;

3)

помечена и просмотрена.

Расставлять пометки начнем с источника S. Он получит пометку <img src="/cache/referats/15102/image054.gif" v:shapes="_x0000_i1058"> Источник помечен, ноне просмотрен. Остальные вершины не помечены. Чтобы источник Sбыл помечен ипросмотрен, надо поместить все вершины, смежные с S.

Вершина <img src="/cache/referats/15102/image056.gif" v:shapes="_x0000_i1059"> получит пометку <img src="/cache/referats/15102/image058.gif" v:shapes="_x0000_i1060"><img src="/cache/referats/15102/image060.gif" v:shapes="_x0000_i1061">

Теперь все вершины <img src="/cache/referats/15102/image056.gif" v:shapes="_x0000_i1062"> смежные с S, помечены, но непросмотрены. А вершина Sпомечена и просмотрена. Начнём просматривать ту из вершин <img src="/cache/referats/15102/image056.gif" v:shapes="_x0000_i1063"><img src="/cache/referats/15102/image056.gif" v:shapes="_x0000_i1064"><img src="/cache/referats/15102/image063.gif" v:shapes="_x0000_i1065"> выполняется следующееусловие <img src="/cache/referats/15102/image065.gif" v:shapes="_x0000_i1066"><img src="/cache/referats/15102/image067.gif" v:shapes="_x0000_i1067"><img src="/cache/referats/15102/image069.gif" v:shapes="_x0000_i1068"><img src="/cache/referats/15102/image063.gif" v:shapes="_x0000_i1069"> выполняется условие <img src="/cache/referats/15102/image072.gif" v:shapes="_x0000_i1070"><img src="/cache/referats/15102/image063.gif" v:shapes="_x0000_i1071"> получает метку <img src="/cache/referats/15102/image075.gif" v:shapes="_x0000_i1072"><img src="/cache/referats/15102/image077.gif" v:shapes="_x0000_i1073">tили же пока нельзя будет больше пометить ни одной вершины, сток при этомостанется не помеченным. Если сток окажется не помеченным, то процесснахождения максимального потока в сети можно считать законченным, а если стокпомечен, то нужно переходить к

процедуре2.

Рассмотрим процедуру изменения потока. Есливершина <img src="/cache/referats/15102/image063.gif" v:shapes="_x0000_i1074"> имеет пометку <img src="/cache/referats/15102/image067.gif" v:shapes="_x0000_i1075"><img src="/cache/referats/15102/image081.gif" v:shapes="_x0000_i1076"> заменяем на <img src="/cache/referats/15102/image083.gif" v:shapes="_x0000_i1077"><img src="/cache/referats/15102/image063.gif" v:shapes="_x0000_i1078"> имеет пометку <img src="/cache/referats/15102/image075.gif" v:shapes="_x0000_i1079"><img src="/cache/referats/15102/image087.gif" v:shapes="_x0000_i1080"> заменяем на <img src="/cache/referats/15102/image089.gif" v:shapes="_x0000_i1081">

Переходим к следующей вершине и так до техпор, пока не достигнем источника S. Здесь изменение потока прекращается. Далеепереходим к процедуре 1 и так до тех пор, пока величину потока уже нельзяизменить.

Рассмотрим конкретную задачу о нахождениимаксимального потока в сети.

Дана сеть G(V,E)(рис. 11) с источником S и стоком t. Пропускные способности дуг указаны.Найти максимальный поток из Sв t.

Поток в транспортнойсети.

Функция<img src="/cache/referats/15102/image091.gif" v:shapes="_x0000_i1082">, определенная на множестве Xдуг транспортной сети Dи принимающаяцелочисленные значения, называется допустимым потоком (или просто потоком) втранспортной сети D,если:

•для любой дуги <img src="/cache/referats/15102/image093.gif" v:shapes="_x0000_i1083"> величина <img src="/cache/referats/15102/image091.gif" v:shapes="_x0000_i1084"><img src="/cache/referats/15102/image095.gif" v:shapes="_x0000_i1085"><img src="/cache/referats/15102/image097.gif" v:shapes="_x0000_i1086">

•для любой промежуточной вершины vвыполняется равенство

т.е.сумма потоков по дугам, заходящим в v, равна сумме потоков по дугам, исходящим из v.

Пример. На рисунке показан допустимый потокв транспортной сети. При каждой дуге указана величина потока по ней. Очевидно,что выполняются все условия, перечисленные в определении допустимого потока(проверяем выполнение второго условия для промежуточных вершин <img src="/cache/referats/15102/image102.gif" v:shapes="_x0000_i1088">

Для любого допустимого потока <img src="/cache/referats/15102/image012.gif" v:shapes="_x0000_i1089"> в транспортной сети Dвыполняется равенство:

По определению допустимого потока <img src="/cache/referats/15102/image012.gif" v:shapes="_x0000_i1091"> имеем:

Заметим, что для каждой дуги <img src="/cache/referats/15102/image110.gif" v:shapes="_x0000_i1094"> где <img src="/cache/referats/15102/image112.gif" v:shapes="_x0000_i1095"><img src="/cache/referats/15102/image091.gif" v:shapes="_x0000_i1096"> входит в левую частьравенства лишь один раз и при этом со знаком плюс. Аналогично для каждой дуги <img src="/cache/referats/15102/image115.gif" v:shapes="_x0000_i1097"><img src="/cache/referats/15102/image091.gif" v:shapes="_x0000_i1098"><img src="/cache/referats/15102/image118.gif" v:shapes="_x0000_i1099"> величина <img src="/cache/referats/15102/image091.gif" v:shapes="_x0000_i1100"> входит в левую частьравенства (2) один раз со знаком плюс (при <img src="/cache/referats/15102/image121.gif" v:shapes="_x0000_i1101"><img src="/cache/referats/15102/image123.gif" v:shapes="_x0000_i1102">

Величиной потока <img src="/cache/referats/15102/image012.gif" v:shapes="_x0000_i1103"> в транспортной сети Dназывается величина <img src="/cache/referats/15102/image012.gif" v:shapes="_x0000_i1104"><img src="/cache/referats/15102/image020.gif" v:shapes="_x0000_i1105">

Пусть <img src="/cache/referats/15102/image012.gif" v:shapes="_x0000_i1108"> — допустимый поток в транспортной сети D. Дуга <img src="/cache/referats/15102/image093.gif" v:shapes="_x0000_i1109"> называется насыщенной,если поток по ней равен её пропускной способности, т.е. если <img src="/cache/referats/15102/image131.gif" v:shapes="_x0000_i1110">. Поток <img src="/cache/referats/15102/image012.gif" v:shapes="_x0000_i1111"> называетсяполным, если любой путь в Dиз <img src="/cache/referats/15102/image133.gif" v:shapes="_x0000_i1112"> содержит, по крайнеймере, одну насыщенную дугу.

Поток <img src="/cache/referats/15102/image012.gif" v:shapes="_x0000_i1113"> называетсямаксимальным, если его величина <img src="/cache/referats/15102/image135.gif" v:shapes="_x0000_i1114"> принимает максимальноезначение по сравнению с другими допустимыми потоками в транспортной сети D.

Очевидно, что максимальный поток <img src="/cache/referats/15102/image012.gif" v:shapes="_x0000_i1115"> обязательно являетсяполным (т.к. в противном случае в Dсуществует некоторая простая цепь <img src="/cache/referats/15102/image137.gif" v:shapes="_x0000_i1116"> из V1 в Vn, не содержащаянасыщенных дуг, а следовательно, можно увеличить на единицу потоки по всемдугам из <img src="/cache/referats/15102/image137.gif" v:shapes="_x0000_i1117"> и темсамым увеличить на единицу <img src="/cache/referats/15102/image135.gif" v:shapes="_x0000_i1118">, что противоречит условию максимальностипотока). Обратная же, вообще говоря, неверно. Существуют полные потоки, неявляющиеся максимальными. Тем на менее полный поток можно рассматривать какнекоторое приближение к максимальному потоку.

Орграф приращений.

Введем для заданной транспортной сети Dи допустимого потока <img src="/cache/referats/15102/image012.gif" v:shapes="_x0000_i1119"> в этой сети орграфприращений <img src="/cache/referats/15102/image022.gif" v:shapes="_x0000_i1120">D. Каждой дуге <img src="/cache/referats/15102/image140.gif" v:shapes="_x0000_i1121"> транспортной сети Dв орграфе приращений <img src="/cache/referats/15102/image022.gif" v:shapes="_x0000_i1122"> соответствует дведуги: <img src="/cache/referats/15102/image095.gif" v:shapes="_x0000_i1123"> и <img src="/cache/referats/15102/image142.gif" v:shapes="_x0000_i1124"> — дуга,противоположная по направлению дуге <img src="/cache/referats/15102/image095.gif" v:shapes="_x0000_i1125"><img src="/cache/referats/15102/image145.gif" v:shapes="_x0000_i1126"><img src="/cache/referats/15102/image022.gif" v:shapes="_x0000_i1127"><img src="/cache/referats/15102/image147.gif" v:shapes="_x0000_i1128">

т.е.орграф <img src="/cache/referats/15102/image022.gif" v:shapes="_x0000_i1131"> является нагруженным.При этом очевидно, что длина любого пути из <img src="/cache/referats/15102/image151.gif" v:shapes="_x0000_i1132"> в <img src="/cache/referats/15102/image153.gif" v:shapes="_x0000_i1133"> в орграфе <img src="/cache/referats/15102/image022.gif" v:shapes="_x0000_i1134"> равна либо 0, либобесконечности.

Алгоритм построениямаксимального потока в транспортной сети.

Важнымследствием теоремы Форда-Фалкерсона является Алгоритмпостроения максимального потока в транспортной сети.

Алгоритм:

Шаг 1.Полагаем i=0. Пусть <img src="/cache/referats/15102/image155.gif" v:shapes="_x0000_i1135"> — любой допустимыйпоток в транспортной сети D(например, полный, можно начинать с нулевого потока: <img src="/cache/referats/15102/image157.gif" v:shapes="_x0000_i1136">

Шаг 2. По сети D и потоку <img src="/cache/referats/15102/image159.gif" v:shapes="_x0000_i1137"> строим орграфприращений <img src="/cache/referats/15102/image161.gif" v:shapes="_x0000_i1138">

Шаг 3. Находим простую цепь<img src="/cache/referats/15102/image163.gif" v:shapes="_x0000_i1139"><img src="/cache/referats/15102/image151.gif" v:shapes="_x0000_i1140"> в <img src="/cache/referats/15102/image020.gif" v:shapes="_x0000_i1141"> в нагруженном орграфе <img src="/cache/referats/15102/image161.gif" v:shapes="_x0000_i1142"><img src="/cache/referats/15102/image159.gif" v:shapes="_x0000_i1143"> максимален, и работа алгоритмазакончена. В противном случае увеличиваем поток ввдоль цепи <img src="/cache/referats/15102/image163.gif" v:shapes="_x0000_i1144"> на максимальнодопустимую величину <img src="/cache/referats/15102/image169.gif" v:shapes="_x0000_i1145"><img src="/cache/referats/15102/image093.gif" v:shapes="_x0000_i1146"> величина <img src="/cache/referats/15102/image091.gif" v:shapes="_x0000_i1147"><img src="/cache/referats/15102/image097.gif" v:shapes="_x0000_i1148"><img src="/cache/referats/15102/image173.gif" v:shapes="_x0000_i1149"><img src="/cache/referats/15102/image149.gif" v:shapes="_x0000_i1150"> и <img src="/cache/referats/15102/image035.gif" v:shapes="_x0000_i1151"><img src="/cache/referats/15102/image175.gif" v:shapes="_x0000_i1152"> существует. Врезультате меняется поток в транспортной сети D, т.е. от потока <img src="/cache/referats/15102/image159.gif" v:shapes="_x0000_i1153"> мы перешли к потоку <img src="/cache/referats/15102/image177.gif" v:shapes="_x0000_i1154"> этом <img src="/cache/referats/15102/image179.gif" v:shapes="_x0000_i1155"><img src="/cache/referats/15102/image181.gif" v:shapes="_x0000_i1156"><img src="/cache/referats/15102/image031.gif" v:shapes="_x0000_i1157">

ПРАКТИЧЕСКАЯ ЧАСТЬ:

Задача о максимальном потоке.

Длязаданной транспортной сети определить величину максимального потока грузов,которые можно доставить в течение заданного времени из города Sв город t.Пропускные способности всех участков дорог считаются известными.

Этап 1.

Начнёмс процедуры расстановки пометок. Пометка источника S<img src="/cache/referats/15102/image183.gif" v:shapes="_x0000_i1158"> Далеерассмотрим те вершины, которые соединены с источником дугой. Это V, V, V. Пропустим по всейсети первоначальный нулевой поток <img src="/cache/referats/15102/image185.gif" v:shapes="_x0000_i1159"> Припишем около каждойдуги после значения пропускной способности значение первоначального потока.

Просмотрим вершину S, для этого пометим вершиныV, V, V.

Просмотрим вершину V, ставим метки <img src="/cache/referats/15102/image187.gif" v:shapes="_x0000_i1160"><img src="/cache/referats/15102/image189.gif" v:shapes="_x0000_i1161"><img src="/cache/referats/15102/image191.gif" v:shapes="_x0000_i1162"> <img src="/cache/referats/15102/image193.gif" v:shapes="_x0000_i1163">

Изменение потока:

Поэтому заменим величину первоначальногопотока:

Этап 2.

Просмотрим вершину V1, вершины V4 и V2 получаютметки <img src="/cache/referats/15102/image187.gif" v:shapes="_x0000_i1169"> и Просмотрим V3, V2 уже просмотрена,<img src="/cache/referats/15102/image207.gif" v:shapes="_x0000_i1170">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 является максимальным, а множество дуг <img src="/cache/referats/15102/image221.gif" v:shapes="_x0000_i1175"> составляют минимальныйразрез сети. Минимальный разрез на рисунке обозначен волнистой линией.

Заключение.

Бурноеразвитие дискретной математики обусловлено прогрессом компьютерной техники, необходимостьюсоздания средств обработки и передачи информации, а также представленияразличных моделей на компьютерах, являющихся по своей природе конечнымиструктурами.

Транспортной сетьюназывается конечный Связныйорграф G(V, E) безпетель, каждой дуге которого поставлено в соответствие некотороенеотрицательное число c(<img src="/cache/referats/15102/image002.gif" v:shapes="_x0000_i1176">), называемое пропускнойспособностью дуги, и существует:

1)ровно одна вершина <img src="/cache/referats/15102/image004.gif" v:shapes="_x0000_i1177">, в которую не заходит ни одна дуга, называемая источником или началом сети;

2)

ровно одна вершина <img src="/cache/referats/15102/image006.gif" v:shapes="_x0000_i1178">, из которой не выходит ни одной дуги; эта вершина называетсястоком или концом сети.

Списокиспользуемой литературы

1. А.М. Аллавердиев, И.В. Платонова «Прикладная математика.Элементы теории графов» М.2000

2. Лекциипо прикладной математике И.В. Платоновой

3. В.Н.Нефедов, В.А. Осипова «Курс дискретной математики» М. 1992

4. С.В.Судоплатов, Е.В. Овчинникова «Элементы дискретной математики» М. 2002

еще рефераты

Еще работы по математике

Реферат по математике

Решение задач линейной оптимизации симплекс – методом

20 Июня 2015

Реферат по математике

Расширения полей