Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

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

Зміст

Вступ3

1. Основні поняття теорії графів4

1.1 Графи. Види графів. Степінь вершини графа4

1.2 Представлення графів в пам’яті ЕОМ10

2. Задача про максимальний потік у мережі15

2.1. Поняття потоку у мережі. Розрізи15

2.2. Задача про максимальний потік в мережі22

2.2.1. Алгоритм Форда знаходження максимального потоку26

2.2.2. Алгоритм Едмондса– Карпа29

2.2.3. Алгоритм Дініца32

3. Практична частина35

3.1. Опис інтерфейсу програми та програмного коду35

3.2. Інструкція користувача36

3.3. Програмна реалізація алгоритмів36

3.4. Тестові приклади47

Висновки51

Список використаної літератури53

Вступ

Задача про максимальний потік у мережі вивчається вже більше 60 років. Інтерес до неї викликаний величезною практичною значимістю цієї проблеми. Методи розв'язання задачі застосовуються на транспортних, комунікаційних, електричних мережах, при моделюванні різних процесів фізики й хімії, у деяких операціях над матрицями, для розв'язку споріднених задач теорії графів, і навіть для пошуку Web-Груп в WWW. Дослідження даного задачі проводяться в багатьох найкрупніших університетів світу.

В середині XX століття, задача про максимальний потік розв’язувалася симплексним методом лінійного програмування, що було вкрай не ефективно. Форд і Фалкресон запропонували розглядати для розв'язку цього завдання орієнтовану мережу й шукати розв'язок за допомогою ітераційного алгоритму. Протягом 20 років, усі передові досягнення в дослідженні даного задачі базувалися на їхньому методі. В 1970р. Дініц, запропонував розв’язувати задачу з використанням допоміжних безконтурних мереж і псевдо-максимальних потоків, що набагато збільшило швидкодію розроблених алгоритмів. А в 1974 Карзанов покращив метод Дініца, увівши таке поняття як предпотік. Алгоритми Дініца та Карзанова, як і дослідження Форда й Фалкерсона, внесли величезний вклад у розв'язок даної проблеми. На основі їх методів 15 років досягалися найкращі оцінки швидкодії алгоритмів. В 1986р. з'явився третій метод, який також без роздумів можна віднести до фундаментальних. Цей метод був розроблений Голдбергом і Таряном, і одержав назву Push-relabel методу. Для знаходження максимального потоку, він використовує предпотоки та мітки,які змінюються під час роботи алгоритму. Push-relabel алгоритми дуже ефективні, і досліджуються дотепер . І, нарешті, в 1997р. Голдберг і Рао запропонували алгоритм, що привласнює дугам неодиничну довжину. Це найсучасніший із усіх відомих алгоритмів.

1. Основні поняття теорії графів

1.1. Графи. Види графів. Степені вершини графа.

Графом називається сукупність двох множин точок і ліній, між якими визначене відношення інцидентності, причому, кожен елемент інцидентний рівно двом елементам . Елементи множини називаються вершинами, а елементи множини - ребрами графа. Вершини і ребра графа називаються його елементами, тому найчастіше пишуть і .

Приклади графів наведено на рис.1.1.

Рис.1.1

Напрямлені ребра називають орієнтованими ребрами або дугами, перша по черзі вершина називається початком дуги, а друга – її кінцем. Граф, що містить напрямлені ребра, називається орієнтованим графом або орграфом рис.1.1.3, а граф, що не містить напрямлених ребер – неорієнтованим або н-графом рис.1.2.

Рис.1.2 Рис.1.3

Вершини сполучені ребром чи дугою називають суміжними, також суміжними називають ребра, що мають спільну вершину. Ребро (чи дуга) і її вершина називаються інцидентними. Ребро (u, v) з'єднує вершини u і v, дуга (u, v) починається у вершині u і закінчується у вершині v.

Графи, у яких не побудовані всі можливі ребра, називаються неповними графами.

Відмітимо, що якщо повний граф має n вершин, то кількість ребер буде дорівнювати :

Дійсно, кількість ребер у повному графі з n вершинами визначається як число неупорядкованих пар, складених із всіх n точок-ребер графа, тобто як число сполучень із n елементів по 2.

Степенем вершини називається кількість ребер, інцидентних цій вершині. Вершина степеня 0 називається ізольованою. Граф, що складається тільки з ізольованих вершин, називається нуль-графом .У графі з петлями петля дає внесок в 2 одиниці у степінь вершини.

Рис.1.6

На рис.1.6: , ,, , .

Вершина називається непарною,якщо степінь цієї вершини непарний, парною - якщо степінь цієї вершини парний.

Теорема.1.1 Сума степенів вершин графа завжди парний:, де - кількість ребер графа. [4]

Теорема 1.2 У будь-якому графі кількість вершин непарного степеня парна. [4]

Сформулюємо деякі закономірності, властиві визначеним графам.

Закономірність 1 Степені вершин повного графа однакові, і кожна з них на 1 менше числа вершин цього графа.

Закономірність 2. Сума степенів вершин графа число парне, рівне подвоєному числу ребер графа. Ця закономірність справедлива не тільки для повного, але й для будь-якого графа.

Закономірність 3. Число непарних вершин будь-якого графа число парне.

Закономірність 4. Неможливо побудувати граф з непарним числом непарних вершин.

Закономірність 5. Якщо всі вершини графа парні, то можна не відриваючи олівець від паперу, проводячи по кожному ребру лише один раз, накреслити цей граф.

Закономірність 6. Граф, який містить всього дві непарні вершини, можна накреслити не відриваючи олівець від паперу, при цьому рух треба почати з однієї з непарних вершин і завершити в іншій.

Нехай G – неоріентований граф.

Маршрутом (шляхом) у графі називається така послідовність ребер , у якій кожні два сусідніх ребра і мають спільну вершину. Іншими словами маршрут – це сукупність ребер, які об'єднані разом вершинами так, що можна рухатися по них уздовж графа.

Рис.1.7

На рис.1.7. початок маршруту – це вершина , інцидентна ребру і не інцидентна ребру . Кінець маршруту – це вершина інцидентна ребру і не інцидентна . Якщо ребра , ( , ) - кратні, то необхідно додатково вказувати, яку із двох інцидентних вершин вважати початком (кінцем) маршруту.

Маршрут довжини - це послідовність, що містить ребер. Іншими словами, довжиною маршруту називається кількість ребер у ньому;

Приклад 1.2 Визначити можливі маршрути (і їхню довжину) з вершини в у графі, зображеному на рис.1.8.

Рис.1.8

Розв’язування: з вершини у ведуть, наприклад, шляхи:

1) - довжини 2; 5) - довжини 6;

2) - довжини 4; 6) - довжини 6;

3) - довжини 4; 7) - довжини 8;

4) - довжини 6; 8) - довжини 10.

Шляхи: 6), 8) не є простими.

Маршрут, у якому збігаються початок і кінець - і - називається циклічним.

Маршрут, який містить різні ребра (вершини) називається ланцюгом, а циклічний маршрут – циклом.

Дві вершини v₁ і v₂ у графі називаються зв'язними (незв'язними), якщо в ньому існує (не існує) маршрут, що веде з v₁ в v₂ .

Граф називається зв'язним, якщо кожні дві його вершини зв'язні; якщо ж у графі знайдеться хоча б одна пара незв'язаних вершин, то граф називається незв'язним. На рис.1.9,(1) – граф незв’язний, а на рис.1.9,(2) –зв’язний.

Рис.1.9

Теорема 1.3 Якщо існує маршрут з вершини в графа , то існує простий ланцюг, що з'єднує вершини і . [2]

Наслідок Граф є зв'язним тоді і тільки тоді, коли між будь-якими двома його вершинами існує простий ланцюг. [2]

Теорема 1.4 Кожний неорієнтований граф розкладається єдиним способом в пряму суму своїх зв’язних компонент. [4]

Теорема 1.5. Якщо в кінцевому графі G рівно дві вершини v₁і v₂ мають непарну локальну степінь, то вони зв'язні. [2]

Нехай - орієнтований граф

Послідовність ребер, у якому кінець кожного попереднього орієнтованого ребра збігається з початком наступного , називається шляхом або орієнтованим маршрутом.

Для графа, зображеного на рис.1.10, наведемо приклади орієнтованих маршрутів з вершини до вершини : ; ; - довжини 3; - довжини 5.

Рис.1.10

Орієнтованим ланцюгом називається шлях, кожне ребро якого зустрічається не більше одного разу.

Контуром називається шлях, початок і кінець якого збігаються.

Приклад 1.3 Для графа, зображеного на рис.1.11,(1), приклади: орієнтованого ланцюга - ; контуру - ; циклу - . Для графа, зображеного на рис.1.11,(2), приклади: простого орієнтованого ланцюга - ; простого циклу - .

(1) Рис.1.11 (2)

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

Орієнтований граф називається зв'язним, якщо його співвіднесений граф є зв'язним.

Якщо для деякої пари вершин орграфа не існує маршрута , який їх з’єднує, то такий орграф називають незв’язним.

Основою орієнтованого графа D = (v, a), називається граф G = (v, e), де e=a, тобто впорядковані пари вершин заміняються на неупорядковані.

Транспортною мережею називається скінченний зв'язний орграф G(v, e) без петель, кожній дузі якого поставлено у відповідність деяке невід’ємне число , що називається пропускною здатністю дуги, і існує:

1) рівно одна вершина , у яку не заходить жодна дуга, називається джерелом або початком мережі;

2) рівно одна вершина , з якої не виходить ні однієї дуги; ця вершина називається стоком або кінцем мережі.

1.2 Представлення графів в пам'яті ЕОМ

Одним зі способів задання графа є задання кожної з множин V і

Е за допомогою переліку їх елементів.

Приклад 1.4 Граф , і , – це граф із чотирма вершинами і п'ятьма ребрами. А граф , і – граф із п'ятьма вершинами і сімома ребрами.

Граф зручно зображати за допомогою рисунка на площині, який називають діаграмою графа . Вершинам графа ставляться у бієктивну відповідність точки площини; точки, що відповідають вершинам і з'єднуються лінією (відрізком або кривою) тоді і тільки тоді, коли v і w суміжні вершини. Зрозуміло, що діаграма графа змінюватиме свій вигляд у залежності від вибору відповідних точок на площині.

Приклад 1.5 На рис.1.12 зображені діаграми графів і з попереднього прикладу.

Рис.1.12

Але наведені способи не є придатними для представлення графів в пам'яті ЕОМ. Для задання графа в пам'яті ЕОМ необхідно занумерувати вершини і ребра, а також задати відношення інцидентності. Відношення інцидентності будемо описувати трьома способами: матрицею інцидентності,

матрицею суміжності, списком ребер графа. Опишемо докладно кожний з перерахованих способів.

Матриця інцидентності - це матриця розміром , де вертикально

вказуються вершини , а горизонтально - ребра . На перетині -того і -того рядків число дорівнює:

а) у випадку неорієнтованого графа

б) у випадку орієнтованого графа

Матриця суміжності – це квадратна матриця розміром , де

вертикально і горизонтально вказуються вершини графа і На

перетинанні –того і –того рядків число дорівнює:

числу ребер, що з'єднують ці вершини у випадку неорієнтованого

графа;

числу ребер з початком в –ій вершині і кінцем в –ій вершині у випадку орієнтованого графа.

Список ребер графа – це таблиця, що складається із трьох рядків. У

першому перераховані всі ребра; у другому і третьому – інцидентні їм вершини:

- у випадку неорієнтованого графа порядок вершин у рядку довільний;

- у випадку орієнтованого графа першою записується вершина, де

починається ребро (другий рядок); вершина, де закінчується ребро, записується у третій рядок.

Для нумерації вершин і ребер графа використовують різний символьний запис: римські, арабські цифри, латинські букви.

Якщо графи рівні, то їх матриці суміжності і інцидентності, а також список ребер, однакові.

Приклад 1.6 Задати матрицями інцидентності і суміжності, а також списком ребер, неорієнтований граф, зображений на рис.1.13.

Рис.1.13.

Розв 'язання:

Матриця інцидентності Матриця суміжності

Тут

Як бачимо, у кожному стовпці матриці інцидентності є тільки два елементи, відмінних від нуля (або один, якщо ребро– петля).

Матриця суміжності симетрична щодо головної діагоналі.

Список ребер є найбільш компактним способом завдання графів.

Кожний із наданих способів однозначно описує граф, зображений на рис.1.13.

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

Як відзначалося вище, всі розглянуті способи задання графів однозначно визначають граф. Виникає питання: чи можливо відновити граф по заданих матрицях інцидентності, суміжності або списку ребер? Очевидна позитивна відповідь.

По матриці інцидентності число ребер і вершин визначається з розмірності матриці: число ребер графа дорівнює числу стовпців , а число вершин - числу рядків матриці.

Список ребер

По матриці суміжності число вершин визначається з розмірності матриці. Як було відзначено, матриця суміжності н-графа симетрична щодо головної діагоналі, і кількість ребер визначається верхнім правим трикутником матриці, розташованим над головною діагоналлю, включаючи останню. Тобто, число ребер н-графа дорівнює сумі елементів, розташованих на головній діагоналі і у верхньому правому трикутнику. У матриці суміжності орграфа симетрія відсутня, а число ребер дорівнює сумі всіх елементів матриці суміжності.

Список ребер є скороченим варіантом матриці інцидентності.

Кількість ребер очевидна, а кількість вершин дорівнює максимальному номеру всіх перерахованих вершин зі списку.

Тобто, матриця інцидентності і список ребер по суті, еквівалентні, то знаючи матрицю інцидентності можна записати список ребер, і навпаки.

Побудова матриці інцидентності за списком ребер. Кожен рядок списку ребер відповідає рядку в матриці інцидентности з тим же номером. Для неорієнтованого графа в кожному рядку списку ребер зазначені номери елементів матриці інцидентности, рівні 1 (всі інші елементи - нулі). Для орієнтованого графа першою вказується вершина, що відповідає початку ребра (у матриці інцидентности - елемент -1), а другий - відповідному кінцю ребра (у матриці інцидентности - елемент 1). При збігу елементів у рядку списку ребер, у відповідному рядку матриці інцидентности записується число, відмінне від -1, 0, 1, наприклад, 2. Така ситуація відповідає наявності у графі петель.

Приклад 1.7 Побудувати матрицю інцидентності неорієнтованого графа за списком ребер:

Список ребер

Розв'язання:

Матриця інцидентності, відповідно до списку ребер, має вигляд:

2. Задача про максимальний потік у меРежі

2.1. Поняття потоку у мережі. Розрізи

Нехай кожній дузі деякої мережі поставлене у відповідність невід’ємне (дійсне) число . Це число ми будемо називати пропускною спроможністю дуги ; Інтуїтивно пропускну спроможність можна уявляти собі як максимальну кількість деякого товару, яке може бути доставлене з в за одиницю часу. Функція c, що відображає множину в множину невід’мних чисел, називається функцією пропускної спроможності.

Нехай і два різні вузли з . Стаціонарний потік величини із в в мережі є функція , яка відображає множину в множину невід’ємних чисел, яка задовільняє лінійним рівнянням і нерівностям:

(2.1)

для всіх . (2.2)

Ми називатимемо джерелом, стоком, а решта вузлів проміжними. Таким чином, якщо чистий потік з вузла визначити як число , то рівняння (2.1) можна виразити, говорячи, що чистий потік з джерела дорівнює , чистий потік з стока дорівнює (або чистий потік у стік рівний ), а чистий потік з будь-якого проміжного вузла дорівнює нулю. Рівняння останнього типу ми будемо називати рівнянням збереження.

Величину потоку ми позначатимемо символом . Відзначимо, що потік з в величини є потік величини з в .

Приклад потоку із в зображений на рис.2.1, де передбачається, що пропускні спроможності дуг настільки великі, що жодна з них не перевищується. Величина цього потоку дорівнює 3.

Рис.2.1

Якщо даний потік , то число ми називатимемо дуговим потоком або потоком по дузі . Кожен дуговий потік входить рівно в два з рівнянь (2.1) і має коефіцієнт 1 в рівнянні, відповідному вузлу , і коефіцієнт -1 в рівнянні, відповідному вузлу . Якщо до мережі додати особливу дугу , допустивши, якщо потрібно, кратні дуги, то ненегативну величину потоку можна розуміти як «поворотний потік» по дузі і всі рівняння (2.1) розглядати як рівняння збереження.

Ще декілька зауважень. Оскільки і задовольняють умовам (2.1) і (2.2), питання про існування потоку не виникає. Далі, ми припускаємо, що це деяка підмножина множини всіх впорядкованих пар , , і функція пропускної спроможності не заперечна на . Але ми могли б вважати, що складається зі всіх таких впорядкованих пар, а функція поза . Так само ми могли б припускати, що пропускна спроможність строго позитивна, виключивши з дуги, на яких вона рівна нулю. Нарешті, система рівнянь (2.1) надмірна, оскільки, складаючи всі рядки її матриці, ми одержуємо нульовий вектор. Таким чином, ми можемо, не порушуючи спільності, відкинути одне з рівнянь цієї системи. Ми вважаємо за краще, зберегти взаємно однозначну відповідність між рівняннями і вузлами.

Нехай перелік всіх дуг даної мережі, причому дуга має пропускну спроможність , і нехай множина всіх направлених ланцюгів з у . Складемо матрицю інциденций , розміру , дуг по відношенню до ланцюгів, вважаючи

(2.3)

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

, i=1, . . . , m. (2. 4)

Називатимемо потоком з у у формі дуги-ланцюга, а ланцюговим потоком або потоком по ланцюгу . Величина потоку є число (2. 5)

У разі, коли потрібно розрізняти два поняття потоку з у , введені нами, ми будемо функцію , що відображає множину дуг в множину ненегативних чисел і задовольняє при деякому умовам (2.1) і (2.2), називати потоком з у у формі вузли-дуги.

Вивчимо відносини між цими двома формами інтуїтивного поняття потоку. Нехай множина всіх вузлів і матриця інциденций вузли-дуги, введена раніше. Таким чином,

(2.6)

Тоді

Звідки випливає, що

(2.7)

Якщо потік з в в формі вузли-дуги і якщо поставити

(2.8)

То буде потоком з у у формі вузли-дуги і . Насправді, через (2.4) і (2.8), а на підставі (2.7)

Але це рівняння (2.1) для функції і p

З другого боку, ми можемо почати з потоку у формі вузла-дуги, що має величину , і одержати з нього потік у формі дуги-ланцюга, що має величину . Інтуїтивною підставою для цієї нерівності служить те, що у формулюванні вузли-дуги допускається потік по ланцюгах з у .

Існують різні способи отримання такого потоку дуги-ланцюга з даного потоку вузли-дуги . Один з них полягає в наступному. Покладемо (2.9)

де . (2.10)

Коротше кажучи, візьмемо перший ланцюг і наскільки можливо зменшимо на дугах ланцюга ; це дасть потік . Потім повторимо цю операцію для і і так поступатимемо до тих пір, поки не переберемо всі ланцюги. Оскільки

то звідси витікає, що це потік у формі вузли-дуги з у , що має величину . Крім того, для всіх і для деякої дуги . Тому потік у формі вузли-дуги рівний нулю на деякій дузі кожного ланцюга з у . Як показує наступна лема, звідси витікає, що .

Лема 2.1 Якщо потік вузли-дуги з у , що має величину , то існує такий ланцюг з у , що на всіх її дугах .[3]

Теорема 2.2 Якщо потік дуги-ланцюга з у , то функція , яка визначається формулою (2.8), це потік вузли-дуги з у і . З другого боку, якщо це потік вузли-дуги з у , то функція , яка визначається формулами (2.9) і (2.10), це потік дуги-ланцюга з у і . [6]

З теореми 2.2 випливає, що всі дуги, інцидентні джерелу, направлені з джерела, а всі дуги, інцидентні стоку, направлені в стік.

Функцію , яка визначається для потоку формулами (2.9) і (2.10), ми називатимемо розкладом ланцюга потоку . Розклад ланцюга потоку , взагалі кажучи, залежатиме від вибору порядку ланцюгів. Наприклад, якщо на рис.2.2

s t

Рис.2.2

ми візьмемо на всіх дугах і покладемо , , , , то , . Але якщо ці ланцюги розглянути в зворотному порядку, то це приведе до значень , .

Щоб спростити позначення, домовимося про наступне. Якщо і підмножини множини , то символом позначатимемо множину всіх дуг, що ведуть з у , і для будь-якої дійсної функції , визначеної на , покладемо

. (2.11)

Подібним же чином для функції , яка визначена на деякій множині вузлів з , покладемо . (2.12)

Множина, що складається з одного елементу, позначатимемо так само, як цей елемент. Так, якщо містить єдиний вузол , то ми писатимемо , і т.д.

Об'єднання, перетини і різниці множин відповідно позначатимуться за допомогою символів , і \. Так, множина вузлів, що містяться у або у або і у і ; множина вузлів, що містяться і у і у V, а множна вузлів, що містяться у , але що не містяться у . Символом ми користуємося для позначення теоретико-множинного включення, а символом для власного включення. Доповнення множин позначаються межею над відповідною буквою. Наприклад, доповнення множини у є .

Таким чином, якщо , , , то

, (2.13)

. (2.14)

Тому, якщо і не перетинаються, то

Зауважимо, що , , і

Для розв’язання задачі про максимальний потік в мережі важливим є множина дуг, які називаються розрізами. Розріз в мережі , відділяючий вузли і , це множина дуг , де , а . Число називається пропускною спроможністю розрізу .

Наприклад, множина дуг в мережі, зображеній на рис.2.2, це розріз, який відділяє і , причому тут .

Відзначимо, що будь-який ланцюг з у містить принаймні одну дугу кожного розрізу . Дійсно, нехай ланцюг, причому і . Оскільки , а , то знайдеться таке , що і . Тому дуга є елементом розрізу . Звідси випливає, що якщо з мережі виключити всі дуги якого-небудь розрізу, то в новій мережі не залишиться жодного ланцюга з у , і величина максимального потоку по цій мережі буде рівна нулю.

Оскільки всякий розріз блокує всі ланцюги з у , інтуїтивно ясно, що величина довільного потоку не може перевищувати пропускної спроможності будь-якого розрізу. Тепер ми доведемо це твердження, грунтуючись на (2.1) і (2.2)

Лема 2.2 Нехай потік з у в мережі величини . Якщо розріз, що відділяє і , то [6]

(2.15)

Доведення. Рівність в (2.15) фактично доведено в лемі 2.1. Ми його тут доведемо знову, користуючись позначеннями, введеними в попередньому пункті. Оскільки потік, мають місце співвідношення

Складемо ті з них, які відносяться до всіх . Оскільки і , ми одержимо

Користуючись тим, що , знаходимо

і рівність в (2.15) доведено. Зважаючи на те що і в силу (2.2) ; звідси негайно слідує і нерівність в (2.15).

Кажучи стисло, рівність в (2.15) виражає той факт, що величина потоку з у рівна чистому потоку через будь-який розріз, що відділяє і .

2.2. Задача про максимальний потік у мережі

Сформулюємо і доведемо основний результат про максимальний потік у мережі.

Теорема 2.3(Форда-Фалкерсона). (Теорема про максимальний потік і мінімальний розріз.) Для будь-якої мережі максимальна величина потоку з у рівна мінімальній пропускній спроможності розрізу, що відділяє і . [2]

1.1 3,2

Алгоритмы поиска максимального потока 📙 Курсовая → 🆔 6389