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

 

 

 

 

 

 

 

Рис.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

   u

 

                                            s                  t

 

 

   v

Рис.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]

x

1.1                            3,2