Максимален мрежов поток. Алгоритъм за намиране на максимален поток

Повтаряме тази операция, докато дренажът бъде маркиран. Ако потокът остане немаркиран, тогава намереният поток е максимален и наборът от дъги, свързващи маркирани върхове с немаркирани, образуват минимален разрез.

3. Нека стоката бъде етикетирана (j+, ε(t)), Тогава f(j,t)замени с f(j,t)+ε(t). Ако запасът е маркиран (j-, ε(t)), Това f(j,t)замени с f(j,t)-ε(t). Да отидем на върха й. Ако йима белег (i+, ε(j)), тогава заместваме f(i,j)на f(i,j)+ε(t), и ако (i-, ε(j)), f(j,i)замени с f(j,i)-ε(t). Да отидем на върха аз. Повтаряме тази операция, докато стигнем до източника s.Промяната на потока спира, всички маркировки се изтриват и преминавате към стъпка 2

ПРИМЕР 3.14.

М 4 К

ЗАДАЧА. Намерете най-високия поток в мрежата

АЛГОРИТЪМ

Нека обозначим върха s= x 0 . Всички останали са x i.

Етап 1.

1. Изберете всеки път, чиито дъги не са наситени.

2. Увеличаваме количеството на потока по този път с единица, докато няма наситена дъга в него.

Продължаваме процеса на увеличаване на потока, докато се изгради пълният поток, т.е. всеки път ще съдържа поне една наситена дъга.

Етап 2.

2. Ако х i вече е маркиран връх, тогава маркираме (+i) всички немаркирани върхове, към които отиват ненаситени дъги от х i, а с индекс (–i) всички немаркирани върхове, от които отиват дъги с ненулев поток към х i.

3. Ако в резултат на този процес се маркира връх t, след това между sИ tима път, чиито всички върхове са маркирани с номерата на предишните върхове. Увеличаваме потока във всички дъги на този път с един ако, когато се движим от sдо tориентацията на дъгата съвпада с посоката на движение и се намалява с единица, ако дъгата има противоположна ориентация. Да преминем към стъпка 1.

4. Когато горната част tневъзможно е да се отбележи, че процесът е прекратен и полученият поток е най-големият поток в мрежата.

ЗАБЕЛЕЖКА. Можете да преминете към етап 2, без да завършите първия етап (вижте пример 3.16).

ПРИМЕР 3.15.

9

РЕШЕНИЕ:

Намерен е пълен поток по дадена транспортна мрежа. Наситените дъги са подчертани

В тази мрежа можете също да маркирате крайния връх и резултатът от маркирането ще бъде същият. Променяйки потока, получаваме мрежа, в която е невъзможно да се отбележи крайният връх, така че потокът в него е най-големият и равен на 10.

ПРИМЕР 3.16.

8 2 1

Открит е непълен поток в дадена транспортна мрежа

Нека да маркираме мрежата и да увеличим потока в нея според алгоритъма. получаваме

В тази мрежа можете също да маркирате крайния връх и резултатът от маркирането ще бъде същият. Променяйки потока, получаваме мрежа, в която е невъзможно да се отбележи крайният връх, така че потокът в него е най-големият и равен на 6.

Раздел IV. ДИНАМИЧНО ПРОГРАМИРАНЕ.

Динамичното програмиране се използва за намиране на оптимални многоетапни решения. Например дългосрочно планиране за подмяна на оборудването; дейност на индустрията в продължение на няколко години. Той използва принципа на оптималност, според който всяко ново частично решение трябва да бъде оптимално спрямо постигнатото състояние.

По-добре е да решавате едно много пъти проста задачаотколкото веднъж комплекс.

ЗАДАЧА 1. За най-изгодния маршрут между две точки.

Необходимо е да се изгради път, свързващ две точки A и B, от които втората е на североизток от първата. За простота, нека кажем, че очертаването на път се състои от поредица от стъпки и на всяка стъпка можем да се движим право на север или право на изток. Тогава всеки път е стъпаловидна прекъсната линия, чиито сегменти са успоредни на една от координатните оси. Разходите за изграждането на всяка от тези секции са известни.

ПРИМЕР 4.1. Намерете минималния път от А до Б.

Последната стъпка е да постигнете T.V. Преди последната стъпка можехме да сме на точки, откъдето да достигнем телевизия с една стъпка. Има две такива точки (системата може да бъде в едно от двете състояния). За всеки от тях има само една възможност за достигане до t.V: за един - движение на изток; за другия - на север. Нека запишем разходите 4 и 3 във всеки случай.

4

Сега нека оптимизираме предпоследната стъпка. След предишната стъпка можем да се окажем в една от трите точки: C 1, C 2, C 3.

За точка C 1 има само една контрола (нека я маркираме със стрелка) - преместете се на изток и разходите ще бъдат 2 (на тази стъпка) + 4 (на следващата стъпка) = 6. По същия начин, за позиция C 3 разходите ще бъдат 2+3=5. За t.C 2 има две контроли: отидете на изток или на север. В първия случай разходите ще бъдат 3+3=6, а във втория случай – 1+4=5. Това означава, че условният оптимален контрол е да се върви на север. Нека го маркираме със стрелка и въведем съответните разходи.

Отговор: x 1 =1; х 3 =0; х 3 =4; W=3,5

ОБОБЩЕН АЛГОРИТЪМ

1. Опишете системата. Тоест разберете какви параметри характеризират състоянието на контролираната система преди всяка стъпка. Важно е да можете правилно и „скромно“ да поставите задачата, без да я претоварвате с ненужни подробности, опростявайки максимално описанието на контролираната система.

2. Разделете операцията на стъпки (етапи). Тук трябва да се вземат предвид всички разумни ограничения, наложени на ръководството. Стъпката трябва да е достатъчно малка, така че процедурата за оптимизиране на стъпковия контрол да е доста проста; и стъпката в същото време не трябва да бъде твърде малка, за да не се правят ненужни изчисления, които усложняват процедурата за намиране на оптималното решение, но не водят до значителна промяна в оптимума целева функция.

3. Открийте набора от стъпкови контроли x i за всяка стъпка и ограниченията, наложени върху тях.

4. Определете какво усилване носи управлението x i на i-стъпката, ако преди това системата е била в състояние S, т.е. запишете функциите за изплащане:

w i =f i (S, x i)

5. Определете как се променя състоянието на системата под въздействието на управление x i on 1-ва стъпка, т.е. напишете функции за промяна на състоянието.

S / =φ i (S, x i)

6. Запишете основното повтарящо се уравнение за динамично програмиране, изразяващо условното оптимално усилване чрез вече известна функция

W i (S)= max(f i (S, x i)+W i+1 (φ i (S, x i)))

7. Произвеждайте условна оптимизацияпоследната стъпка, като правите различни предположения за това как е завършила предпоследната стъпка и за всяко от тези предположения намерете условния (избран въз основа на условието, че стъпката е завършила с нещо) оптимален контрол на последната стъпка.

W m (S) = max (f m (S, x m))

8. Извършете условна оптимизация, като започнете от предпоследната стъпка и завършите с първата стъпка (backing back).

9. Произвеждайте безусловна оптимизацияуправление, „четене“ на съответните препоръки на всяка стъпка: вземете намереното оптимално управление на първата стъпка и променете състоянието на системата, намерете оптималното управление за намереното състояние на втората стъпка и т.н. до последната стъпка.

ПРИНЦИП НА ОПТИМАЛНОСТ. Каквото и да е състоянието на системата преди следващата стъпка, е необходимо да се избере управление на тази стъпка, така че усилването на тази стъпка плюс оптималното усилване на всички следващи стъпки да е максимално.

Принципът на динамичното програмиране не предполага всяка стъпка да се оптимизира отделно, независимо от останалите. Какъв е смисълът да избираме контрол, чиято ефективност е максимална на една конкретна стъпка, ако тази стъпка ще ни лиши от възможността да печелим добре на следващите стъпки?

В практиката има случаи, когато една операция трябва да се планира за неопределено дълъг период от време. Моделът за такъв случай е контролиран процес с безкрайни стъпки, при който всички стъпки са равни. Тук печелившата функция и функцията за промяна на състоянието не зависят от номера на стъпката.

Раздел V. СИМУЛАЦИОННО МОДЕЛИРАНЕ

Това ръководство е предназначено за студенти, които посещават курсове по дискретна математика и/или теория на графите.

С негова помощ ще усвоите темата "Максимален поток и минимален разрез в мрежата."

• Директно от това ръководство можете да изчислите своя ID, дори ако нямате MATLAB на вашия компютър.=|Ако имате MATLAB, отидете на тази страница: там имате възможност да се намесите в изчислителния скрипт (програма). Тук проблемът с максималния поток в мрежата се решава чрез свеждането му до проблем с линейно програмиране.Нека въведем следната нотация:
• п=|V| − размер на графа (брой върхове);
• м д Директно от това ръководство можете да изчислите своя ID, дори ако нямате MATLAB на вашия компютър.× п| − кардиналност на графа (брой ребра); А− матрица на инцидентност на мрежов орграф с размер аз; всеки елемент от него a ik=1 ако от А- горната част излиза азк a ik-i дъга; А=−1, ако е в
• sвлиза тия връх
• t-i дъга; И
• =0 в други случаи; във всяка колона на такава матрица има точно една единица, една минус една, а останалите са нули;− номер на изходния връх на мрежата; само дъги трябва да излизат от този връх, а всеки друг връх трябва да бъде достъпен от източника; − s м − номер на върха на поглъщане на мрежата; само дъги трябва да влизат в този връх, а дренажът трябва да бъде достъпен от всеки друг връх;
• =0 в други случаи; във всяка колона на такава матрица има точно една единица, една минус една, а останалите са нули;а − t s м ;
• мтрябва да съдържа само единици, т.к само дъги трябва да излизат от източника; t м -ти ред от матрицата на инцидентност на диграфа на мрежата s; tтрябва да съдържа само минус единици, защото само дъги трябва да влизат в канала;
• ул − матрица на инцидентност на мрежовия орграф пс изхвърлените от него та иредове; a ikд
• − колонен вектор на дължина − матрица на инцидентност на мрежовия орграф пс изхвърлените от него ; във всеки негов елемент e k a ikще бъде величината на входящия поток

та дъга;

c

c k

• ≥0 задава пропускателната способност та ита дъга. та и = ; във всеки негов елементТогава проблемът с максималния мрежов поток може да се формулира като проблем с линейно програмиране:
• Общият поток, напускащ източника (1), е максимизиран. Освен това във всеки междинен връх входящият поток е равен на изходящия поток (2), а капацитетът на дъгите е ограничен (3).
• ако има два такива компонента, тогава изхвърлените дъги дават минимален разрез;
• ако се появят повече от две свързани компоненти, тогава диграфът на мрежата има няколко минимални срязвания (съответният проблем с линейното програмиране е изроден).

За изроден проблем, първият минимален разрез, най-близо до източника, е конструиран на тази страница.

За да използвате тази страница правилно, вашият браузър трябва да поддържа скриптове Java Script. Включете ги.

Въведете първоначалните данни в полетата за въвеждане по-долу. В първата област трябва (по-точно можете) да въведете координатите на върховете, за да начертаете диграф на мрежата. Те са посочени под формата на матрица Директно от това ръководство можете да изчислите своя ID, дори ако нямате MATLAB на вашия компютър.×2: в първата колона − хта координати, във втората − г-е. Числата могат да бъдат зададени като цели числа, с десетична точка или в експоненциална форма. Разделете числата с интервали. Общо количестволинии в тази област за въвеждане определя размера на диграфа Директно от това ръководство можете да изчислите своя ID, дори ако нямате MATLAB на вашия компютър.− брой върхове. Тези начални данни (координати на върха) не са задължителни: ако не са посочени, диграфът на мрежата ще бъде изчертан като правилен Директно от това ръководство можете да изчислите своя ID, дори ако нямате MATLAB на вашия компютър.-gon и броят на върховете ще се определя от максималния брой на върховете в следващата област за въвеждане.

В следващата област за въвеждане лявата страна− задължително за попълване. Той определя структурата на мрежовия диграф. пВсяка дъга в диграфа свързва два върха. Номерата на тези върхове са посочени под формата на матрица ×2 от лявата страна на втората зона за въвеждане. На всеки ред първо се посочва 1-вият връх (опашка, източник) на дъгата, а след това чрез интервал се посочва 2-ри връх (върх, изтичане) на дъгата.Тези колони трябва да съдържат Директно от това ръководство можете да изчислите своя ID, дори ако нямате MATLAB на вашия компютър.естествени числа пот 1 до

Общият брой на числата във всяка от тези колони определя кардиналността на диграфа − брой дъги. , Изчислете Нека е даден насочен граф G= в която посоката на всяка дъга vÎV Vозначава посоката на потока (например поток от автомобили), капацитетът на всяка дъга е равен на tИ s d(v). tНа много върхове sдва върха са подчертани t. Вертекс s .

е източникът на потока, - източване. Необходимо е да се определи максималния поток, който може да бъде прекаран от върха V Нека означим с x(v)

количеството поток, движещ се по дъга (6. 1)

v . Очевидно е, че 0 £ x(v) £ d(v) , vÎV .

На всеки връх)iÎE\(t,s)

(x(v)| iÎV + (i)) - (x(v)| iÎV - (i))=0.(6.2)

За върха t

(x(v)| iÎV + (i)) -(x(v)¦ iÎV - (i))=-Q,(6.3)

за връх s

(x(v)| iО V + (i)) -(x(v)¦ i О V - (i))= Q.(6.4)

величина Qе големината на потока, който напуска върха tи влиза в горната част s.

Трябва да се определи

Q ® макс(6.5)

при ограничения (6.1-6.4).

Количества Q, x(v), vÎV,удовлетворяващи ограничения (6.1-6.4), ще наречем поток в мрежата и ако те максимизират стойността Q, след това максималния поток. Лесно се вижда, че стойностите Q=0, x(v)=0, vÎV, са поток в мрежата.

Задача (6.1-6.5) е задача за линейно програмиране и може да бъде решена с помощта на алгоритми на симплексния метод.

Нека разделим множеството от върхове E на две несвързани части E1 и E2 по такъв начин, че tÎE1, sÎE2. По разрез V(E1,E2), отделяне tИ sще извикаме комплекта V(E1,E2)ÌVтака че за всяка дъга v О V(E1,E2)или h1(v)ОE1И h2(v)ОE2, или h1(v)ОE2И h2(v)ОE1.

Нека разделим комплекта V(E1,E2)на две части V(E1,E2,+),V(E1,E2,-)както следва:

V(E1,E2,+)=(vÎV(E1,E2)| h1(v)ÎE1И h2(v)ОE2)

V(E1,E2,-)= (vÎV(E1,E2)| h2(v)ÎE1И h1(v)ОE2)

Ще наричаме пропускателната способност на разреза

Q(E1,E2) = (x(v)| vÎV(E1,E2,+))-(x(v)| vÎV(E1,E2,-))

Вярно е следното

Теорема 1. (Относно максимален поток и минимално разрязване).

Във всяка мрежа максималният поток от източника е ада запасите sравна на минималната производителност Q(E1,E2)сред всички съкращения V(E1,E2), разделяйки върховете tИ s.

Имайте предвид, че при максимален поток

x(v)=d(v) , vÎV(E1,E2,+),

x(v)=0, vÎV(E1,E2,-).

Нека Q, x(v), vÎV, -някакъв мрежов поток, последователност

t=i(0),v(1),i(1),v(2),i(2),...,v(k),i(k)=s,

е верига, свързваща върховете tИ s. Нека зададем на тази верига посоката на движение от върха tдо s. Арк v(j)от тази верига се нарича права, ако нейната посока съвпада с посоката на движение от tдо s, и обратното в противен случай. Ще наречем тази верига път нарастващ поток, ако за прави дъги Нека означим свериги x(v)< d(v) и за обратно x(v) > 0. През тази верига може да бъде прекаран допълнителен поток рот tдо sразмер q = min(q1,q2),Къде q1=min (d(v) -x(v)), минимумът се взема за всички прави дъги на веригата, q1=min (x(v)), минимумът се взема по всички обратни дъги на веригата.

Теорема 2.

Поток Q, x(v), vÎV, е максимално, ако и само ако няма начин да се увеличи потокът.

Предложеният алгоритъм за решаване на проблема с максималния поток в мрежа се основава на намирането на начин за увеличаване на потока от t. Вертекс s, което от своя страна се основава на процеса на подреждане на етикети на върхове. Да кажем това

връх азотбелязани със знак q(i)>0, а дъгата с права дъга също е известна v(i), през който идва този поток, или е маркиран с , ако някакъв допълнителен поток от величина q(i)>0, а обратната дъга също е известна v(i), през които е влязъл този поток;

връх i се разглежда, ако всички негови съседни върхове са маркирани.

Ако връх s е маркиран, тогава е намерен път за увеличаване на потока с величина р, която се минава по тази пътека. За да опишем алгоритъма ни е необходим и масив SPW, който съдържа номерата на маркираните върхове в реда, в който са били маркирани. C1- число в масива SPWгледан връх, C2- номерът на последния маркиран връх в този масив.

Идеята на този алгоритъм е да намери пътища от край до край с положителни потоци от източника до приемника.

Да разгледаме ребро (i, j) с (начален) капацитет. По време на изпълнението на алгоритъма части от този капацитет се „отнемат“ от потоци, преминаващи през дадено ребро, в резултат на което всяко ребро ще има остатъчен капацитет. Запис - Оставаща честотна лента. Мрежа, в която всички ръбове имат остатъчен капацитет, ще се нарича остатъчна.

За произволен възел j, получаващ поток от възел i, ние дефинираме етикет, където е стойността на потока, протичащ от възел j към възел i. За да намерим максималния поток, изпълняваме следните стъпки.

За всички ръбове задаваме остатъчния капацитет, равен на първоначалния капацитет, т.е. нека приравним =. Нека присвоим и маркираме възел 1 с етикет. Приемаме i=1.

Наборът от възли j, до които можете да отидете от възел I по ръб с положителен остатъчен капацитет >0 за всички j. Ако изпълняваме етап 3, в противен случай преминаваме към 4.

В намираме възел k такъв, че. Нека поставим и маркираме възел k с етикет. Ако k=n, се намира път от край до край и отиваме на етап 5, в противен случай задаваме i=k и се връщаме на етап 2.

Връщане назад. Ако i=1, не е възможен път от край до край и се преминава към 6. Ако, намираме означения възел r непосредствено предшестващ възел i и го премахваме от набора от възли, съседни на възел r. Задаваме i=r и се връщаме към етап 2.

Дефиниция на остатъчна мрежа. Нека обозначим с набор от възли, през които p_th намерен път от край до край от изходния възел (възел 1) до възел мивка (възел n) преминава тогава максималният поток, преминаващ по този път

Остатъчният капацитет на ръбовете, които образуват пътя от край до край, намалява с известно количество в посоката на потока и се увеличава със същото количество в обратната посока.

това. за край (i, j), включен в пътека от край до край, текущият остатъчен капацитет се променя:

1) ако потокът преминава от възел i към j,

2) ако потокът преминава от възел j към i.

а) при m открити пътища от край до край, максималният поток се изразява чрез

б) Имайки стойностите на началния и крайния капацитет на ръба (i, j), можем да изчислим оптималния поток през този ръб, както следва. Нека го поставим. Ако >0, потокът, преминаващ през ръб (i, j), е равен. Ако >0, тогава потокът е равен. (случаят, когато и >0, и >0 е невъзможен).

Пример 1. Намерете максималния поток в мрежата Фиг. 1

Итерация 1. =

3) k=3, тъй като. Присвояваме и маркираме възел 3 с етикет. i=3 и връщане към 2)

5) k=5 и. Маркираме възел 5 с етикет. Получаваме проходен път.

6) определяме пътя от край до край чрез етикети, започвайки от възел 5 и завършвайки с възел 1: . И. Ние изчисляваме остатъчните мощности по пътя:

Итерация 2.

1) и маркирайте възел 1 с етикет. i=1

2") (така че възел 5 не е включен в

3") k=4 и маркирайте възел 4 с етикет. i=4 и връщане към 2)

2""") (тъй като възли 1 и 3 са маркирани, те не са включени в)

3""") k=5 и. Маркираме възел 5 с етикет. Получава се път от край до край. Отидете на 5)

Итерация 3.

1) и маркирайте възел 1 с етикет. i=1

3) k=2 и маркирайте възел 2 с етикет. i=2 и връщане към 2)

3") k=3 и. Маркирайте възел 3 с етикет. i=3 и се върнете към 2)

2") (тъй като) отидете на 4)

4) етикетът на възел 3 показва номера на предишния възел. При тази итерация възел 3 не се взема предвид в бъдеще; етикетът му е зачеркнат. и се върнете към 2)

2""") (тъй като възел 3 е премахнат от възможния път от край до край)

3""") и. Маркираме възел 5 с етикет. Получава се път от край до край. Отидете на 5)

5) i. Ние изчисляваме остатъчните мощности по пътя:

Итерация 4. При тази итерация пътят с

Итерация 5. При тази итерация пътят с

Итерация 6: Не са възможни нови пътища от край до край, тъй като всички ръбове, произхождащи от възел 1, имат нулев остатъчен капацитет. Отидете на 6), за да определите решението

6) максималният обем на потока в мрежата е равен на единици.

Стойностите на потока за различни ръбове се изчисляват чрез изваждане на последните стойности на остатъчния капацитет от първоначалните стойности на капацитета.

Резултати от изчислението: табл. 1

Графично последователно изпълнение на алгоритъма за намиране на максимален поток (пример 1)

д) е) Няма преминаващи пътеки

ориз.

Първоначалните данни за транспортната система, например в завода, показани на фиг. 2, може да се посочи и чрез таблица (Таблица 2).

Таблица 2. Изходни данни за задачата за максимален поток

Очевидно максималният капацитет на транспортната система не надвишава 6, тъй като не повече от 6 единици товар могат да бъдат изпратени от начална точка 0, а именно 2 единици до точка 1, 3 единици до точка 2 и 1 единица до точка 3 , След това е необходимо да се гарантира, че всичките 6 единици товар, напускащи точка 0, са достигнали крайната точка 4. Очевидно 2 единици товар, пристигнали в точка 1, могат да бъдат изпратени директно до точка 4. Товарът, който е пристигнал в точка 2, ще трябва да бъдат разделени: 2 единици незабавно се изпращат към точка 4, а 1 единица - към междинна точка 3 (поради ограничения капацитет на участъка между точки 2 и 4). До точка 3 е доставен следният товар: 1 единица от точка 0 и 1 единица от точка 3. Изпращаме ги до точка 4. Така че максималната пропускателна способност на въпросната транспортна система е 6 единици товар. В този случай вътрешните секции (клонове) между точки 1 и 2, както и между точки 1 и 3, не се използват напълно - по него се изпращат 2 единици товар пропускателна способност от 3 единици. Решението може да бъде представено под формата на таблица (Таблица 3)

Таблица 3. Решаване на проблема с максималния поток

Задача за линейно програмиране за максимизиране на потока.Нека формулираме проблема с максималния поток от гледна точка на линейното програмиране. Нека X KM е обемът на превоза от точка K до точка M. Съгласно фиг. 2 K = 0,1,2,3, M = 1,2,3,4, като транспортирането е възможно само до точката с по-висок номер. Това означава, че има общо 9 променливи X KM, а именно X 01, X 02, X 03, X 12, X 13, X 14, X 23, X 24, X 34. Проблемът с линейното програмиране, насочен към максимизиране на потокът има формата:

X 01 + X 02 + X 03 = F (0)

X 01 + X 12 + X 13 + X 14 = 0 (1)

X 02 - X 12 + X 23 + X 24 = 0 (2)

X 03 - X 13 - X 23 + X 34 = 0 (3)

X 14 - X 24 - X 34 = - F (4)

X км? 0, K, M = 0, 1, 2, 3, 4

Тук F е целевата функция, условие (0) описва влизането на стоки в транспортната система. Условия (1) - (3) определят балансовите отношения за възли 1-3 на системата. С други думи, за всеки от вътрешните възли входящият поток от стоки е равен на изходящия поток, стоките не се натрупват вътре в системата и не се „раждат“ в нея. Условие (4) е условието за “излизане” на товарите от системата. Заедно с условие (0) това представлява балансова връзка за системата като цяло („вход“ е равен на „изход“). Следните девет неравенства поставят ограничения върху капацитета на отделните „клонове“ на транспортната система. След това се посочва неотрицателността на обемите на трафика и целевата функция. Ясно е, че последното неравенство следва от формата на целевата функция (връзка (0) или (4)) и неотрицателността на обемите на трафика. Последното неравенство обаче носи някои обща информация- през системата може да премине или положителен обем товар, или нулев (например, ако има движение в кръг в рамките на системата), но не и отрицателен (няма икономически смисъл, а формален математически модел„не знае“ за това).

Сума от потоци през инцидентни дъги Нека означим с, е равно на сумата от потоците през инцидентните дъги w; тази сума се нарича стойност на потока. Ще се интересуваме преди всичко от потоци, които имат възможно най-голям магнитуд - така наречените максимални потоци. IN общ случайедна мрежа може да има няколко различни максимални потоци, но техните стойности трябва да са еднакви. (4)

Изследването на максималните потоци през мрежа N = (V,D,a) е тясно свързано с концепцията за разрез, т.е. такова множество A от дъги на орграф D, което има свойството, че всяка проста верига от Нека означим с. Вертекс минава през дъгата, принадлежаща на A. Капацитетът на разрез е сумата от капацитетите на дъгите, принадлежащи му. Разрезите, които имат най-малката възможна производителност, се наричат ​​минимални разрези.

Големината на нито един поток не надвишава пропускателната способност на който и да е разрез и следователно големината на всеки максимален поток не надвишава пропускателната способност на който и да е минимален разрез. Не е ясно обаче веднага, че двамата последни числавинаги равни един на друг; Този резултат е получен от американските математици Форд и Фулкерсън през 1955 г. и е наречен теорема за максималния поток и минималния разрез.

Теорема (за максималния поток и минималния разрез). Във всяка мрежа размерът на всеки максимален поток е равен на капацитета на всеки минимален разрез.

Теоремата за максимален поток и минимално изрязване ви позволява да проверите дали даден поток е максимален или не, но само за сравнително прости мрежи. Разбира се, на практика трябва да се справяме с големи и сложни мрежи и като цяло е трудно да се намери максимален поток чрез прост избор. Нека опишем един алгоритъм за намиране на максималния поток във всяка мрежа с целочислена пропускателна способност.

Стъпка 1. Първо, нека изберем поток, който има ненулева стойност (ако такъв поток съществува). Например, ако N е мрежата, показана на фиг. 29.3, тогава потокът, показан на фиг. 29.4. Струва си да се отбележи, че колкото по-голяма е стойността на първоначалния поток, който сме избрали, толкова по-лесни ще бъдат следващите стъпки.

Стъпка 2. Въз основа на N изграждаме нова мрежа N’, като променяме посоката на потока в противоположната. По-точно, всяка дъга a, за която (a) = 0, остава в N' с първоначалния си капацитет и всяка дъга a, за която , се заменя с дъга a с капацитет и противоположна дъга с капацитет (a). Мрежа N' в нашия пример е показана на фиг. 29.5. Вертекс Нека означим свече не е източник, а поглътител.

Стъпка 3. Ако в мрежа N’ можем да намерим ненулев поток от Нека означим с c, тогава може да се добави към оригиналния поток и да се получи нов поток с по-голяма стойност в N. Сега можете да повторите стъпка 2, като използвате новата нишка N’ вместо N’, когато конструирате мрежата. Повтаряйки тази процедура, в крайна сметка ще стигнем до мрежа N', която не съдържа ненулеви потоци; тогава съответният поток ще бъде максималният поток. Например на фиг. 29.5 има ненулев поток, в който протича през дъгите ( v,u), (u,z), (z,x), (x,y) И ( y,) са равни на единица, а потоците през останалите дъги са равни на нула. Добавяйки този поток към потока на фиг. 29.4, получаваме потока, показан на фиг. 29,6; повтаряйки стъпка 2, е лесно да се покаже, че това е максималният поток.

Използвана литература:

(1) http://pgap.chat.ru/zap/zap264.htm#0

(2) Асанов М.О., Барански В.А., Расин В.В. Дискретна математика: матроидни графи, алгоритми

(3) Basaker R., Saati T. Крайни графики и мрежи.

(4) Уилсън Р. Въведение в теорията на графите