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

Зміст

Вступ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.                                                                     (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.