Дискретна математика - Раздел 2

Нека N = (G, а) - мрежа като един източник и един изтичане б. Да приемем, че N е мрежа диаграма на комуникационни линии, където върховете съответстват на комуникационни възлови точки, дъги - връзка със споменатата посока предаване на информация. Ако е - дъга мрежа N, стойността на (д) означава да се ограничи количеството на информацията, предавана чрез дъга е за определен период от време. Следващият въпрос. Това, което е максималният размер на информация може да се предава от А до точка Б, и как да го направя? Отговорът на този въпрос, и този раздел е посветен.

След по-горе тълкуване на мрежата се съгласявате ценят (д) покана пропускателна способност дъга д.

Централният концепцията на този раздел е, че на потока в мрежата.

Определение. Нека N = (G, а) - в мрежата, и - на източника и б - Stock тази мрежа. Поток през мрежата N е функция

отговаря на следните две условия:

1) й (д) £ а (д) за всеки дъга д Î Е,

2) в мрежата (G, й) на всеки възел с изключение на източника и източване outdegree равно indegree. J номера (е) се нарича стойността на потока през дъга напр.

Фиг. 6.16 е пример на поток през мрежата е показано на фиг. 6.15. Стойностите на й са показани в скоби.

Оферта. Нека J - тече през мрежата N = (G, а). След това количеството на потока през инцидента дъга към източника, е сумата от потоци чрез инцидента дъга да се оттича.

Доказателство. Нека V = 1, v2, ..., ил>, където v1 - източник, v2 - отток. Разглеждане на мрежа от N '= (G, J). Мрежовата N 'Половината сума резултат от всички върхове, равен на сбора от всички върхове indegree

защото за произволен брой дъга д й (е) да играе само веднъж в ляво и в точното количество. Тъй J - поток, тогава г - (VI) = R + (VI) от I = 3, ..., п. Това означава, че R - (v1) + R - (v2) = R + (v1) + R + (v2). От последното равенство получаваме R - (v1) = R + (v2), защото

Определение. Сумата, посочена в предходното изречение се нарича доказан количество поток. Фуражът е максимална. ако той има най-висока стойност (наред с всичко протича през даден на мрежата).

В J поток е означен с Уг й половина. Потокът е показано на фиг. 6,16, е на стойност 5. Този поток е най-много, тъй като стойността му за инцидента с дъги към канала е равна на сумата на капацитета на тези дъги. Мрежата може да има повече от максималния поток, като примера, показан на фиг. 6.17

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

Определение. Процеп мрежа N, с един източник и един изтичане, S е набор от дъги, така че всеки път от източника на канала преминава през дъга от S.

Определение. Bandwidth раздел е сумата от индивидуалните възможности на своите дъги членки. Разрезът се нарича минимално. ако тя има най-малък капацитет (между всички части на мрежата). Капацитетът на производителност на раздел S ще бъде означена с (S).

Например, за мрежата на фиг. 6.18 примери разрези са определени S1 =, S2 =, S3 =. Тези съкращения имат ленти, съответно, 7.6 и 6. прорезите S2 и S3 са минимални. Виждаме, че минималните съкращенията могат да бъдат няколко.

Оказва се, че за всяка стойност на максималната мрежата на потока съвпада с пропускателна способност на минималната разреза. Този резултат е получен от американските математици Форд и Folkersonom през 1955. Ние даваме доказателство, обаче, ние се отбележи, на първо място по брой подкрепящи факти.

Ако й - тече през мрежата N = (G, а), след това чрез G й ще означаваме подграф на графика G, съдържаща дъга, по която потокът ненулева (и само тези дъга).

Лема 1. За всеки й поток през мрежата N = (G, а) поток й съществува през същата мрежа, така че Уг й Уг = Уг у Уг и G Y - схема без подграф на G й.

Доказателство. Да предположим, че графика G J съдържа контура С минава по Е1 дъги, Е2, ... EL. Сред номера J (е1), к (е2), ..., к (EL) избира най-малко, нека да бъде броят на м. Да разгледаме функцията # 952 ;: E ® N È Определя, както следва:

Лесно е да се провери, че # 952; - поток през мрежата N, Уг й Уг = Уг # 952; Уг и G # 952; - подграф на G й. Ърл G # 952; вече не съдържа контур С. Повтаряйки процедурата толкова пъти, като в резултат се получи необходимата ш поток.

Лема 2. Нека J - ненулева поток през мрежа N с източника и изтичане и б. Тогава там е проста (а, б) - път минава покрай дъги с различна от нула поток.

Доказателство. Чрез Лема 1, може да се предположи, че графика G J = на (V, E й) не съдържа линии. Нека Va - набор от върховете на G й. достижим от връх а на. Тъй като графика G J не съдържа линии, след множеството Va съдържа най-малко един връх х, което е изтичане в графика G J на. Ясно е, че х ¹ добре. Ако х ¹ В, тогава графиката G има дъга с различна от нула поток, който акостира в х, и няма ръбове с различна от нула поток излъчвана от х. Това противоречи на определението на потока. Следователно, б Î Va. т.е. в графика G й е достъпен от Възлова точка В и. Това означава, че мрежата N има проста (а, Ь) - път, простираща се по дъги от ненулева поток.

Лема 3. Стойността на всеки поток през мрежата не надвишава капацитета на всеки участък от мрежата.

Доказателство. Нека J - тече през мрежата N = (G, а), S - точка на мрежата. Припомнете си, че скоростта на потока е обозначен с Уг й половина производителност и намаляване на способността - чрез (S).

Нека първо да приемем, че функцията J е цяло число. Въз основа на мрежата N и к поток. Ние конструира насочено графика G 'с няколко дъги. Наборът от върховете на графиката G 'е група от първоначални върховете на G. Ако е - (х, у) и дъгата на графика G J на ​​(е)> 0, тогава графика G' изобразяват й (е) от дъги, произтичащи от х и влизащи в у. Ако й (Е) = 0 или G не дъга от х до у, тогава в G ', също не е дъга от х до у. Фиг. 6.20 показва графика на G ', построена за мрежата N и потока (в скоби), както е показано на фиг. 6.19.

Лема 2 предполага, че графиката G 'съществува множество R Уг й половина прост (а, Ь) -paths, не две от които съдържа общо дъга. Ние означават с "множество от дъги на графиката G ', който е получен от крайната дъги S. Ясно е, че S S' - част от графиката G 'и, че броят на ръбове в S' е по-малка или равна на (S). Всеки от множеството писти Р включва най-малко една дъга на S ', където две различни пътеки не могат да съдържат същия дъгата на S ". Това означава, че броят на пътеките в P не надвишава броя на дъгите в S ", т.е. Уг й Уг = Уг P Уг £ Уг S 'и половина паунда (S).

Помислете сега случаят, когато й се рационални ценности. Нека м - най-малкото общо кратно на знаменателите на функция J. Тогава функция М · й е мрежа поток (G; m · а). Ясно е, че зададената S се нарязва и нова мрежа с пропускателна способност, равна на m · а (S). В предходния параграф, е доказано, че и половина m · й половина £ m · на (S). Следователно неравенство Уг й половина £ на (S).

В общия случай, т.е. когато всички позволени стойности на капацитет и потока се намалява до по-горе със следните твърдения. За всяка мрежа N = (G, а) с поток от к и процеп S и произволен брой д> 0, съществува рационално й поток 0 през същата мрежа, така че - д <½ j ½ – ½ j 0 ½

За по-нататъшно въвеждане на някои нотация. Нека N = (G, а) - мрежа като източник и изтичане В, D - множество мрежови възли, така че Î D, б Ï D. След това множеството от ребрата

обозначен с SD. Той е лесно проверено, че множеството от SD е разрез на мрежата. В този раздел ще се нарича D-изрязани. Ако X и Y - непразни набори от върховете, а й - поток през мрежата,

Лема 4. Нека N = (G, а) - мрежа като източник и изтичане б, J - тече през мрежата, D - множество мрежови възли, включващ съдържащ и б. след това

Доказателство. Чрез поток определение за х ¹ а и х ¹ б имаме равен

и за да се определи количеството на потока - равен

J (а, V) - й (V, а) = Уг й половина.

От тези уравнения това следва, че

Уг й Уг = (J (х, V) - й (V, х)) = J (D, V) - й (V, D).

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

Доказателство. Нека J - максималния поток в мрежа N = (G, а). Чрез Лема 3, докаже наличието на разреза достатъчно S така, че (S) = Уг й половина.

Можем да предположим, че G й - безплатно графика (виж Лема 1.).

Arc д се нарича наситен ако й (Е) = а (д). Letter D означават набор от върха, съдържаща: изтичане и върховете ф, за които има последователност

така че дъга (XI. XI + 1) ненаситен или чрез дъга (XI + 1. XI) се простира ненулева поток. Например мрежата, показана на Фиг. 6.21. D =. Имайте предвид, че Z Î D, въпреки че дъгата (Y, Z) на мрежата не.

Ние твърдим, че б Ï D. Ние приемаме, че това не е вярно, т.е. б Î D. След това е последователност от върховете

по-горе форма (т.е., или дъга (у, у, + 1) ненаситен или през дъга (у + 1, Yi) се простира ненулева поток). Нека д - положително число, което е по-малко от разликата на (д) - й (д) за всяко д ненаситен дъга и по-малко всяка различна от нула нетен поток през дъга.

Променете стойността на J поток на дъги следва верига. Ако дъгата (у, у, + 1) ненаситен, ние се й '(у + 1, Yi + 1) = J (у, у, + 1) + напр. Ако тази дъга е наситен, нека й '(у + 1, ил) = J (у + 1, ил) - д. За друга стойност поток д дъги оставят непроменени: J "(д) = J (д).

Лесно е да се провери, че й "- поток през N. мрежа Всъщност ограничаването й" (д) £ а (д) се отнася и за всяко д дъга да се изгради й ". Ако връх V не минава верига (*), а общият дебит през V е нула, тъй като това се отнася и за к. Нека V = ай за някои аз Î , Има четири случаи, определени чрез насищане или ненаситени дъги (у-1, Yi) и (у, у, + 1). (Това ще бъде удобно да се помисли за липсващата дъгата наситени) Помислете само един от тях: дъгата (ай-1, ай) ненаситен и дъгата (ай, ай + 1) е запълнен. Ние означаваме с A множеството от върховете на които са с изглед към дъгата, влизащи в у,. писмо Б набор от върховете на мрежата, която получава на дъгата излиза от ай. след това

като й - поток. В прехода от к да й "термини в дясната страна, не се променя, и двата термина се извършва в лявата промяната: к (у-1, ай) се заменят със к (у-1, ай) + Е. и к (у + 1, ил) - за к (у + 1, ил) - д. но цялата сума ще остане същата. Ето защо, уравнението (**) продължи и през прехода от к да й ". Ние сме доказали, че й "- тече през N. мрежа, обаче, стойността му е равна на ½ й ½ + Е. което противоречи максимална J на ​​потока. По този начин, б Ï Г.

Ако ф Î D и има дъга от влизането върховете Ф Х, с различна от нула поток, а след това срещу Î D. Това означава, че й (, D) = 0. Помислете за SD разрез. След Лема 4 че Уг й Уг = а (SD), като (SD) = J (D,).

Както и в секцията за теглене на мрежата, за да се изгради по-лесно от намирането на поток през мрежата, на Ford-Folkersona теорема за прости мрежи може да се използва за определяне на максималния поток в мрежата. Въпреки това, за повече или по-сложна мрежа, дори ако стойността на максималния поток се озова сам трудно да се изгради на потока. Ето защо ние представяме решаването на проблема с изграждането на максималния дебит за мрежи с целочислени ленти алгоритъм. Имайте предвид, че по време на алгоритъма може да възникне мрежи, където няма източник или източване.

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

Dana мрежа (G, а), - източник, б - наличност мрежа,: E ® Н.

Етап 1. Ако няма път от източника на изтичане, после J = 0 и преминете към стъпка 4, или изберете непразни набор T несвързани дъги от пътеки от а до Ь. Ако Е1, Е2, ..., Ек - по пътя на T, която е последователност от дъги, после й (е1) = J (е2) = ... = J (Ek) = мин. За дъги д, след които не тръгнат по пътя на Т, сложи й (е) = 0. Резултатът е ненулев й поток през мрежата (G, а).

Етап 2. Въз основа на мрежата (G, а) и на потока й за изграждане на мрежа (G ', а'), както следва. G Ърл "ще имат същите върховете като графиката G. Ако е - дъга графика G и (д) - й (д) ¹ 0, д - дъга графиката G" и "(Е) = А (Е ) - й (д). Ако е - Arc граф и G J (д) ¹ 0, тогава ще се въведе дъга обратна ориентация от Е, и поеме "() = J (д). В случая, когато има Е1 и Е2 множество дъги. тогава можем да ги въведе в един дъга, вместо д и да поема "(е) = а" (е1) + една "(е2).

Стъпка 3, а след това преминете към стъпка 4, в противен случай мрежата (G ', а') да се изгради не нулев поток й "Ако мрежата (G", а "), няма път от А до точка Б, както е предписано в точка 1. за мрежа (G, а) набор J = J + J "и преминете към стъпка 2.

Стъпка 4. За да се издадат й. Край на алгоритъм.

На примера на мрежата, показана на Фигура 6.22 илюстрира алгоритъм. Тъй като набор Т в първия етап на алгоритъма е избран от множество от два начина: а, v1, v4, В и А, v2, v5 Ь.

Фиг. 6.23 показва мрежа (G ', а'), получен след етап 2 на мрежата от фиг. 6.22 с определен (в скоби) поток й. Тъй като набор T за конструиране й поток "взети комплект, състоящ се от един път: а, V3, V5, V2, v6, б. Поток J + J "на мрежата (G, а) на фиг. 6.24. Това преминаване алгоритъм е завършена. Отбелязваме, че за д = (v2, v5) (к + J) (д) = J (д) - J '() = 1.

Мрежата конструирана в етап 2 на второто преминаване на алгоритъма вече има (а, Ь) - пътища (виж Фигура 6.25.). Поради това, на фиг. 6.24 показва максималния поток.