 |
|
АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология |
Мережі, потоки в мережах. Теорема Форда - Фалкерсона
Мережею називається зв'язаний граф (звичайно, не орграф і не мультиграф), у якому задані “пропускні здатності” ребер, тобто числа qij. Ці числа більші або рівні нулю, причому qij = 0 тоді й тільки тоді, коли немає ребра, що з'єднує вершини i й j. Таким чином, можна вважати, що пропускні здатності ребер задані для будь-якої пари вершин. У дискретній математиці пропускні здатності ребер, як і всі виникаючі константи, вважаються цілими числами (або раціональними, тому що раціональні числа відрізняються від цілих тільки одиницями вимірювання). Помітимо, що мережі мають величезні додатки, зокрема, “мережі планування” (мається на увазі планування виробництва деяких нових, досить складних виробів), де “пропускні здатності” ребер – це час, за яке потрібно з декількох вузлів виробу (вершин графа) одержати інший (більше складний) вузол. Набагато більший інтерес представляє мережі зв'язку, де пропускні здатності ребер – це звичайно “кількість одночасних повідомлень”, які можуть передаватися між комп’ютерами (вершинами графа). Потоком у мережі між вершиною t (джерелом) і s (стоком) називається набір чисел сij, (тобто кількість умовного “вантажу”, перевезеного з вершини з номером i у вершину з номером j), що задовольняють чотирьом умовам: 1) числа сij £ 0, причому якщо сij > 0, то сji = 0 (немає зустрічних перевезень); 2) числа cij £ qij (відповідних пропускних здатностей ребер); 3) якщо вершина з номером i – проміжна (не збігається із джерелом і стоком), то
тобто кількість “вантажу”, що вивозиться із вершини i, дорівнює кількості “вантажу”, ввезеного в цю вершину; 4) кількість “вантажу”, що вивозиться із джерела t, повинне дорівнювати кількості вантажу, ввезеного в стік s:
Число А називається величиною даного потоку або просто потоком між t й s. Нехай є деякий перетин між вершинами t й s. Тоді величиною перетину називається сума пропускних здатностей ребер, що входять у цей перетин. Перетин називається мінімальним (максимальним), якщо його величина мінімальна (максимальна). Теорема Форда – Фалкерсона (1955). Максимальний потік між вершинами t й s дорівнює величині мінімального перетину між цими вершинами. Доказ цієї теореми є конструктивним (тобто показує, як знайти потрібний максимальний потік). 1. Доведемо спочатку, що будь-який потік між вершинами t й s менше або дорівнює величині будь-якого перетину. Нехай даний деякий потік і деякий перетин. Величина даного потоку складається з величин “вантажів”, перевезених по всіх можливих шляхах з вершини t в s. Кожен такий шлях зобов'язаний мати загальне ребро з даним перетином. Тому що по кожному ребру перетину сумарно не можна перевести “вантажу” більше, ніж його пропускна здатність, тому сума всіх вантажів менше або дорівнює сумі всіх пропускних здатностей ребер даного перетину. Твердження доведене. Звідси необхідно, що будь-який потік був менше або дорівнював величині мінімального перетину, а значить і максимальний потік менше або дорівнює величині мінімального перетину. 2. Доведемо тепер зворотну нерівність. Нехай є деякий потік cij (якийсь потік завжди існує, наприклад, нульовий, коли всі cij = 0). Будемо позначати вершини графа, причому вважаємо, що всі позначені вершини утворять множину Y. Позначки вершин здійснюються від джерела. Кожна позначка вершини (якщо ця вершина може бути позначена) складається із двох чисел: перше - це “+” або “-” номер вершини (з Y), з якої зв'язана нова позначувана вершина, і друге - (обов'язково повинне бути позитивним) - це фактично та добавка до потоку, що може бути додатково “довезена” у цю вершину із джерела в порівнянні з вихідним потоком. Більш точно, множина позначених вершин Y утвориться в такий спосіб: джерело t належить Y і його позначка (0,¥); друге число, умовно говорячи, дорівнює нескінченності – що для дискретної математики означає, що це настільки велике число, як нам знадобиться; якщо вершина належить Y і cij < qij (дуга (i,j) – пряма й ненасичена), то вершина j також належить Y і позначка вершини j дорівнює (+i, dj), де dj>0 дорівнює dj= min {di, qij – cij}. Помітимо, що тут число di – це друге число вже позначеної вершини i, а знак + перед номером i означає, що дуга, що зв'язує вершини (i, j) є прямій (і ненасиченої); якщо вершина до належить Y і сjk > 0 (зворотна дуга), то вершина з номером j також повинна належати Y й її позначка дорівнює (– до, dj), де знак мінус означає, що вершина j пов'язана із уже позначеною вершиною до зворотною дугою, dj= min{dk, qjk+cjk}, причому очевидно, що j також строго більше нуля. Таким чином, побудова множини Y є індуктивним, тобто нова вершина додається в Y, якщо вона пов'язана з деякою вершиною вже вхідної в Y або прямій ненасиченою дугою, або зворотною дугою. Після того як побудова множини Y закінчена (до нього не можна додати нових вершин), можливі 2 випадки. 1. Стік (тобто вершина з номером s) не входить у множину вершин Y. Тоді позначимо множину вершин, що не входять в Y через Z. Наш граф за умовою є зв'язковим, тому з Y, в Z ідуть деякі ребра. За правилами побудови Y всі ці ребра є прямими насиченими дугами (рис. 3.13). Ребра, що йдуть із множини Y в Z, утворять перетин між вершинами t й s. Видно також, що сума пропускних здатностей ребер цього перетину (а всі ці ребра є прямими, насиченими) дорівнює потоку з t в s. Виходить, даний потік є максимальним (тому що він дорівнює величині деякого перетину), а даний перетин є мінімальним.
Рисунок 3.13 – Граф з насиченими дугами 2. Вершина s також входить в Y, і нехай друге число її позначки s > 0. Тоді, мабуть, що між вершинами t й s існує ланцюг (що складається зі спрямованих ребер - прямих і зворотних дуг), що з'єднує ці вершини Схематично це може бути представлено t ® ·®· ··® ·®· ··®·®s Помітимо, що дуга, що виходить із джерела, і дуга, що входить у стік, повинні бути обов'язково прямими. Додамо d s до cij для прямих дуг цього ланцюга (по побудові видно, що отримане число буде менше або дорівнює qij) і віднімемо це d s з cij для зворотних дуг (може вийти негативне число, але воно обов'язково буде за абсолютною величиною менше qij, тому що по побудові d s £ cij+qij, а це означає, що зворотна дуга міняє напрямок, стає прямою дугою і його “навантаження” буде дорівнює модулю числа Тому що щораз величина потоку збільшується, принаймні, на 1 (пропускні здатності ребер є цілими числами), а величина максимального потоку обмежена (величиною мінімального перетину), те ця процедура не може тривати нескінченно й, виходить, на якомусь кроці одержимо потік, для якого вершина s не входить в Y, тобто потік є максимальним і величина його дорівнює величині мінімального перетину. Теорема доведена. Теорема Форда - Фалкерсона фактично є алгоритмом знаходження максимального потоку між двома вершинами (або доказом того, що цей потік є максимальним). Примітка. Якщо в даному графі із пропускними здатностями ребер (тобто мережі) є кілька джерел і кілька стоків, то описаний вище алгоритм можна застосувати в такий спосіб. Уводимо нове джерело й новий стік, причому нове джерело з'єднуємо ребрами з усіма джерелами, а новий стік - з усіма стоками, при цьому пропускні здатності нових ребер уважаємо як завгодно більшими числами, так що ці дуги в будь-якому можливому потоці були б ненасиченими (нагадаємо, що ребра, що йдуть із джерела й ребра, що йдуть у стік завжди є прямими дугами). Після цього для нового графа вирішуємо задачу про максимальний потік (з одного нового джерела в один новий стік). Вирішивши її, стираємо всі уведені ребра й вершини.
Дата добавления: 2015-09-27 | Просмотры: 1085 | Нарушение авторских прав |
,
.
. Тоді нові числа для дуг, що входять у наш ланцюг, а також “старі” cij для всіх дуг, що не входять у наш ланцюг, утворять новий потік з вершини t у вершину s. Крім того, величина нового потоку в порівнянні зі старим збільшилася на ds > 0. Для нового потоку знову проведемо ту ж процедуру й т.д.