Дискретна математика - розділ 2
Нехай N = (G, a) - мережа, що має одне джерело a і один стік b. Припустимо, що мережа N представляє собою схему ліній зв'язку, де вершин відповідають вузли зв'язку, дуг - лінії зв'язку з зазначеним напрямком передачі інформації. Якщо е - дуга мережі N, то величина a (е) означає обмеження кількості інформації, що передається по дузі е за деякий проміжок часу. Виникає наступне питання. Яку найбільшу кількість інформації можна передати з а в b і як це зробити? Відповіді на поставлене питання і присвячений цей параграф.
Дотримуючись наведеної вище інтерпретації мережі, домовимося величину a (е) називати пропускною спроможністю дуги е.
Центральним поняттям параграфа є поняття потоку в мережі.
Визначення. Нехай N = (G, a) - мережу, а - джерело і b - стік цієї мережі. Потоком через мережу N називається функція
задовольняє двом умовам:
1) j (е) £ a (е) для будь-якої дуги е Î Е,
2) в мережі (G, j) у будь-який вершини, крім джерела і стоку, полустепені результату дорівнює полустепені заходу. Число j (е) називається значенням потоку через дугу е.
На рис. 6.16 наведено приклад потоку через мережу, зображену на рис. 6.15. Значення функції j вказані в дужках.
Пропозиція. Нехай j - потік через мережу N = (G, a). Тоді сума потоків через дуги, інцідентние джерела, дорівнює сумі потоків через дуги, інцідентние стоку.
Доведення. Нехай V = 1, v2, ..., vn>, причому v1 - джерело, v2 - стік. Розглянемо мережу N '= (G, j). У мережі N 'сума полустепені результату всіх вершин дорівнює сумі полустепені заходу всіх вершин
оскільки для будь-якої дуги е число j (е) бере участь рівно один раз, як в лівій, так і в правій сумі. Так як j - потік, то r - (vi) = r + (vi) для i = 3, ..., n. Це означає, що r - (v1) + r - (v2) = r + (v1) + r + (v2). З останнього рівності отримуємо рівність r - (v1) = r + (v2), тому що
Визначення. Сума, про яку йдеться в доведеному вище пропозиції називається величиною потоку. Потік називається максимальним. якщо він має найбільшу величину (серед усіх потоків через цю мережу).
Величину потоку j будемо позначати через ½ j ½. Потік, наведений на рис. 6.16, має величину 5. Цей потік є максимальним, оскільки його значення на дугах, інцидентних стоку, дорівнює сумі пропускних спроможностей цих дуг. Мережа може мати кілька максимальних потоків, як показує приклад, наведений на рис. 6.17
При вивченні максимальних потоків в мережі використовується поняття розрізу.
Визначення. Розрізом мережі N, що має одне джерело і один стік, називається безліч дуг S таке, що будь-який шлях з джерела в стік проходить через дугу з S.
Визначення. Пропускною спроможністю розрізу називається сума пропускних спроможностей входять до нього дуг. Розріз називається мінімальним. якщо він має найменшу пропускну здатність (серед всіх розрізів даної мережі). Пропускну здатність розрізу S будемо позначати через a (S).
Так, наприклад, для мережі на рис. 6.18 прикладами розрізів будуть безлічі S1 =, S2 =, S3 =. Ці розрізи мають пропускні спроможності відповідно 7,6 і 6. Розрізи S2 і S3 є мінімальними. Ми бачимо, що мінімальних розрізів може бути кілька.
Виявляється, що для будь-якої мережі величина максимального потоку збігається з пропускною спроможністю мінімального розрізу. Цей результат був отриманий американськими математиками Фордом і Фолкерсоном в 1955 році. Ми наведемо його доказ, однак перш за все зазначимо ряд допоміжних фактів.
Якщо j - потік через мережу N = (G, a), то через G j будемо позначати суграфом графа G, що містить дуги, по яких проходить ненульовий потік (і тільки такі дуги).
Лемма 1. Для будь-якого потоку j через мережу N = (G, a) існує потік j через ту ж мережу такий, що ½ j ½ = ½ y ½ і G y - бесконтурний підграф графа G j.
Доведення. Припустимо, що граф G j містить контур С, що проходить по дугам е1, е2, ..., Еl. Серед чисел j (e1), j (e2), ..., j (el) виберемо найменше, нехай це буде число m. Розглянемо функцію # 952;: E ® N È , Яка визначається наступним чином:
Легко перевірити, що # 952; - потік через мережу N, ½ j ½ = ½ # 952; ½ і G # 952; - підграф графа G j. Граф G # 952; вже не містить контуру С. Повторюючи цю процедуру необхідну кількість разів, в результаті отримуємо необхідний потік y.
Лемма 2. Нехай j - ненульовий потік через мережу N з джерелом а й стоком b. Тоді існує простий (a, b) - шлях, який проходить по дугам з ненульовим потоком.
Доведення. В силу леми 1 можна вважати, що граф G j = (V, E j) не містить контурів. Нехай Va - безліч вершин графа G j. досяжних з вершини а. Оскільки граф G j не містить контурів, то безліч Va містить хоча б одну вершину х, яка є стоком в графі G j. Ясно, що х ¹ а. Якщо х ¹ b, то в графі G існують дуги з ненульовим потоком, що заходять в х, і не існує дуг з ненульовим потоком, що виходять з х. Це суперечить визначенню потоку. Отже, b Î Va. тобто в графі G j вершина b досяжна з а. Це означає, що в мережі N існує простий (a, b) - шлях, який проходить по дугам з ненульовим потоком.
Лема 3. Величина будь-якого потоку через мережу не перевищує пропускну здатність будь-якого розрізу цієї мережі.
Доведення. Нехай j - потік через мережу N = (G, a), S - розріз цієї мережі. Нагадаємо, що величину потоку ми позначаємо через ½ j ½ а пропускну здатність розрізу - через a (S).
Припустимо спочатку, що функція j приймає цілочисельні значення. Виходячи з мережі N і потоку j. побудуємо орграф G 'з кратними дугами. Безліч вершин графа G 'збігається з безліччю вершин вихідного графа G. Якщо е - (x, y) -дуга графа G і j (е)> 0, то в графі G' зображуємо j (е) дуг, що виходять з х і заходять в y. Якщо ж j (е) = 0 або в G немає дуги з х в y, то в G 'теж немає дуги з х в y. На рис. 6.20 зображений граф G ', побудований для мережі N і потоку (в дужках), представлених на рис. 6.19.
З леми 2 випливає, що в графі G 'знайдеться безліч Р з ½ j ½ простих (a, b)-шляхом, ніякі два з яких не містять загальної дуги. Позначимо через S 'безліч дуг графа G', які вийшли з дуг розрізу S. Ясно, що S '- розріз графа G' і що кількість дуг в S 'менше або дорівнює a (S). Кожен із шляхів безлічі Р містить хоча б одну дугу з S ', причому два різних шляхи не можуть містити одну і ту ж дугу з S'. Це означає, що число шляхів у Р не перевищує число дуг в S ', тобто ½ j ½ = ½ Р ½ £ ½ S '½ £ a (S).
Розглянемо тепер випадок, коли функція j приймає раціональні значення. Нехай m - найбільша спільне кратне всіх знаменників значень функції j. Тоді функція m · j буде потоком в мережі (G; m · a). Ясно, що безліч S буде розрізом і в новій мережі з пропускною спроможністю, рівною m · a (S). У попередньому абзаці було доведено, що ½ m · j ½ £ m · a (S). Звідси випливає нерівність ½ j ½ £ a (S).
Загальний випадок, тобто коли допускаються будь-які значення пропускних спроможностей і потоків, зводиться до розглянутого вище за допомогою наступного твердження. Для будь-якої мережі N = (G, a) з потоком j і розрізом S і будь-якого числа e> 0 існує раціональний потік j 0 через ту ж мережу, такий що - e <½ j ½ – ½ j 0 ½ Для подальшого введемо ряд позначень. Нехай N = (G, a) - мережа, що має джерело а й стік b, D - безліч вершин мережі, таке, що a Î D, b Ï D. Тоді безліч ребер позначимо через SD. Легко перевіряється, що безліч SD є розрізом мережі. Цей розріз будемо називати D-розрізом. Якщо X і Y - непусті безлічі вершин мережі, а j - потік через мережу, то Лемма 4. Нехай N = (G, a) - мережа, що має джерело a і стік b, j - потік через цю мережу, D - безліч вершин мережі, що містить a і не містить b. тоді Доведення. За визначенням потоку для x ¹ a і x ¹ b маємо рівність а за визначенням величини потоку - рівність j (a, V) - j (V, a) = ½ j ½. З цих рівностей випливає, що ½ j ½ = (j (x, V) - j (V, x)) = j (D, V) - j (V, D). Теорема. У будь-якій мережі величина максимального потоку дорівнює пропускній здатності мінімального розрізу. Доведення. Нехай j - максимальний потік в мережі N = (G, a). В силу леми 3 досить довести існування розрізу S такого, що a (S) = ½ j ½. Можна вважати, що G j - бесконтурний граф (див. Лему 1). Дугу e назвемо насиченою, якщо j (e) = a (e). Позначимо буквою D безліч вершин мережі, що містить стік a і все вершини u, для яких існує послідовність така, що дуга (xi. xi + 1) ненасичених або через дугу (xi + 1. xi) проходить ненульовий потік. Наприклад, для мережі, зображеної на рис. 6.21. D =. Відзначимо, що z Î D, хоча дуги (y, z) в мережі немає. Доведемо, що b Ï D. Припустимо, що це не так, тобто b Î D. Тоді існує послідовність вершин зазначеного вище виду (тобто або дуга (yi, yi + 1) ненасичені, або через дугу (yi + 1, yi) проходить ненульовий потік). Нехай e - позитивне число, яке менше різниці a (e) - j (e) для будь-якої ненасиченої дуги e і менше будь-якого ненульового потоку через дуги мережі. Змінимо значення потоку j на дугах кола наступним чином. Якщо дуга (yi, yi + 1) ненасичені, то покладемо j '(yi + 1, yi + 1) = j (yi, yi + 1) + e. Якщо ж ця дуга насичена, то нехай j '(yi + 1, yi) = j (yi + 1, yi) - e. Для інших дуг e значення потоку залишимо тим самим: j '(e) = j (e). Неважко переконатися, що j '- потік через мережу N. Дійсно, обмеження j' (e) £ a (e) виконується для будь-якої дуги e з побудови j '. Якщо через вершину v не проходить ланцюг (*), то сумарний потік через v дорівнює нулю, оскільки це справедливо для j. Нехай v = yi для деякого i Î . Можливі чотири випадки визначаються насиченістю або ненасиченістю дуг (yi-1, yi) і (yi, yi + 1). (Нам буде зручно відсутню дугу вважати насиченою) Розглянемо лише один із них: дуга (yi-1, yi) ненасичені, а дуга (yi, yi + 1) насичена. Позначимо буквою А безліч вершин, з яких виходять дуги, що заходять в yi. буквою B безліч вершин мережі, в які заходять дуги, що виходять з yi. тоді оскільки j - потік. При переході від j до j 'складові в правій частині не зміняться, а в лівій зміняться два доданків: j (yi-1, yi) заміняться на j (yi-1, yi) + e. а j (yi + 1, yi) - на j (yi + 1, yi) - e. але вся сума залишиться колишньою. Отже, рівність (**) збережеться і при переході від j до j '. Ми довели, що j '- потік через мережу N. Але його величина дорівнює ½ j ½ + e. що суперечить максимальності потоку j. Таким чином, b Ï D. якщо u Î D і існує дуга, що заходить в u з вершини v, з ненульовим потоком, то v Î D. Це означає, що j (, D) = 0. Розглянемо розріз SD. Тоді з леми 4 випливає, що ½ j ½ = a (SD), оскільки a (SD) = j (D,). Оскільки на кресленні розріз мережі побудувати простіше, ніж знайти потік через мережу, то теорему Форда-Фолкерсона в разі простих мереж можна використовувати для знаходження максимальних потоків в мережі. Однак для більш-менш складної мережі, навіть якщо знайдена величина максимального потоку, сам потік побудувати важко. Наведемо тому алгоритм, що вирішує завдання побудови максимального потоку для мереж з цілочисельними пропускними здатностями. Відзначимо, що в процесі роботи алгоритму можуть виникати мережі, в яких немає ні джерела, ні стоку. Дана мережа (G, a), a - джерело, b - стік мережі, a: E ® N. Крок 1. Якщо не існує шляху з джерела в стік, то покласти j = 0 і перейти до кроку 4, інакше вибрати непорожня множина T непересічних по дугах шляхів з a в b. Якщо e1, e2, ..., ek - шлях з T, тобто послідовність дуг, то покласти j (e1) = j (e2) = ... = j (ek) = min. Для дуг e, через які не проходять шляхи з T, покласти j (e) = 0. В результаті отримуємо ненульовий потік j через мережу (G, a). Крок 2. Виходячи з мережі (G, a) і потоку j побудувати мережу (G ', a') наступним чином. Граф G 'буде мати ті ж вершини, що і граф G. Якщо e - дуга графа G і a (e) - j (e) ¹ 0, то e - дуга графа G' і a '(e) = a (e ) - j (e). Якщо e - дуга графа G і j (e) ¹ 0, то вводимо дугу зворотній орієнтації, ніж e, і вважаємо a '() = j (e). У разі, коли виникають кратні дуги e1 і e2. то вводимо замість них одну дугу e і вважаємо a '(e) = a' (e1) + a '(e2). Крок 3. Якщо в мережі (G ', a') не існує шляху з a в b, то перейти до кроку 4, інакше в мережі (G ', a') побудувати ненульовий потік j 'так, як це наказано кроком 1. для мережі (G, a) покласти j = j + j 'і перейти до кроку 2. Крок 4. Видати j. Кінець роботи алгоритму. На прикладі мережі, зображеної на рис 6.22, проілюструємо роботу алгоритму. Як безлічі T на першому кроці алгоритму вибрано безліч з двох шляхів: a, v1, v4, b і a, v2, v5, b. На рис. 6.23 представлена мережа (G ', a') отримана після виконання кроку 2 з мережі на рис. 6.22 із зазначеним (в дужках) потоком j '. Як безлічі T для побудови потоку j 'взято безліч, що складається з однієї колії: a, v3, v5, v2, v6, b. Потік j + j 'для мережі (G, a) зображено на рис. 6.24. Цим завершено один прохід алгоритму. Звернемо увагу на те, що для e = (v2, v5) (j + j ') (e) = j (e) - j' () = 1. Мережа побудована на кроці 2 другого проходу алгоритму, вже не має (a, b) - шляхів (див.рис. 6.25). Отже, на рис. 6.24 зображений максимальний потік.Алгоритм знаходження максимального потоку
Схожі статті