Відомості до обчислення максимального потоку

У цьому розділі ми розглянемо ряд завдань, що зводяться до задачі обчисленні максимального потоку, і покажемо, що алгоритми з розділів 22.2 і 22.3 важливі в ширшому контексті. Ми можемо знімати різні обмеження на мережі і вирішувати інші мережеві завдання, ми можемо вирішувати інші завдання обробки мереж і графів, і ми можемо вирішувати завдання, які не належать до мережевих. У цьому розділі будуть розглянуті приклади такого використання - обчислення максимального потоку в якості загальної моделі вирішення завдання.

Ми також вивчимо взаємозв'язок між обчисленням максимального потоку і більш складними завданнями, щоб сформувати контекст для розгляду цих завдань в подальшому. Зокрема, завдання про максимальний потік являє собою спеціальний випадок задачі відшукання потоку мінімальної вартості, про яку піде мова в розділах 22.5 та 22.6. Крім того, ми покажемо, як формулювати завдання обчислення максимального потоку у вигляді задач лінійного програмування, які ми будемо розглядати в частині 8. Завдання відшукання потоку мінімальної вартості і лінійне програмування є більш загальні моделі рішення задач, ніж модель максимального потоку. І хоча зазвичай рішення задач про максимальний потік за допомогою спеціальних алгоритмів, описаних в розділах 22.2 та 22.3, менш трудомістким, ніж за допомогою алгоритмів для вирішення більш загальних задач, важливо знати про взаємозв'язок між моделями вирішення завдань при переході до більш складним моделям.

Ми будемо вживати термін стандартна задача про максимальний потік (standard maxflow problem) для версії завдання, яку ми вивчали досі (максимальний потік в st-мережах з обмеженою пропускною спроможністю ребер). Цей термін буде застосовуватися виключно для полегшення посилань в даному розділі. Спочатку ми розглянемо відомості, на прикладі яких переконаємося, що обмеження в стандартній задачі про максимальний потік несуттєві, тому що до стандартної задачі зводяться або еквівалентні кілька інших завдань про потоках. Будь-яку з еквівалентних завдань можна прийняти в якості "стандартної" завдання. Простим прикладом такого завдання, який вже згадувався як наслідок з леми 22.1, є завдання відшукання циркуляції в мережах, що дозволяє отримати максимальний потік в заданому ребрі. Потім ми розглянемо інші способи постановки задачі, в кожному разі відзначаючи їх зв'язок зі стандартною завданням.

Максимальний потік в мережах загального вигляду. Потрібно знайти потік в мережі, який максимізує сумарний відплив з її витоків (і, отже, приплив в її стоки). За угодою, в мережі, в якій немає витоків і / або стоків, потік вважається нульовим.

Лемма 22.14. Завдання про максимальний потік в мережах загального вигляду еквівалентна задачі про максимальний потік в st-мережах.

Доведення. Ясно, що алгоритм обчислення максимального потоку для мереж загального вигляду буде працювати і на st-мережах, тому потрібно лише перевірити, що спільне завдання зводиться до задачі про st-мережах. Для цього спочатку знайдемо витоки і стоки (користуючись, наприклад, методом для ініціалізації черзі з програми 19.8) і завершимо роботу з кодом повернення 0, якщо немає ні того, ні іншого. Потім додамо фіктивну вершину-витік s і ребра з неї в усі витоки мережі (пропускна здатність кожного такого ребра дорівнює відтоку з його кінцевої вершини), а також фіктивну вершину-стік t і ребра з кожного стоку мережі в неї (пропускна здатність кожного такого ребра дорівнює відтоку його початкової вершини). Це зведення показано на Мал. 22.31 . Будь максимальний потік в st-мережі безпосередньо відповідає максимальному потоку в вихідної мережі.

Мал.22.31.

Зведення задачі з декількома джерелами і стоками

У верхній мережі є три джерела (0, 1 і 2) і два стоку (5 і 6). Щоб знайти потік, який максимізує сумарний потік з витоків і в стоки, ми обчислюємо максимальний потік в st-мережі, представленої внизу. Це копія вихідної мережі, в яку додані витік 7 і стік 8. З вершини 7 в кожен вихідний витік проводимо ребро, пропускна здатність якого дорівнює сумарної пропускної спроможності ребер, що виходять з цього джерела. А в вершину 8 ведуть ребра з кожного вихідного стоку мережі, пропускна здатність яких дорівнює сумарної пропускної спроможності ребер, що входять в стоки вихідної мережі.

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

Лемма 22.15. Завдання обчислення максимального потоку в транспортній мережі з обмеженнями на пропускну здатність вершин еквівалентна стандартної задачі про максимальний потік.

Доведення. Тут також можна скористатися будь-яким алгоритмом, який вирішує завдання з обмеженнями на пропускні спроможності, для вирішення стандартної завдання (встановивши пропускну здатність в кожній вершині більше, ніж її приток або її відтік), тому досить довести зводиться до стандартної задачі. Для заданої транспортної мережі з обмеженими пропускними здатностями побудуємо стандартну транспортну мережу з двома вершинами u і u *, відповідними кожної вихідної вершині u. При цьому всі ребра, що входять у вихідну вершину, йдуть в u, всі вихідні ребра виходять з u *, а пропускна здатність ребра uu * дорівнювати пропускній здатності вихідної вершини. Це побудова показано на Мал. 22.32 . Потоки в ребрах виду u * -v при будь-якому максимальний потік в перетвореної мережі дають максимальний потік у вихідній мережі, який повинен задовольняти обмеженням на пропускну здатність вершин через наявність ребер виду uu *.

Мал.22.32.

Видалення пропускних спроможностей вершин

Щоб вирішити задачу обчислення максимального потоку в мережі, показаної вгорі, і щоб потік через кожну вершину не перевищував пропускної здатності, заданої в масиві capV, індексованих іменами вершин, ми будуємо стандартну мережу, показану внизу. Для кожного ребра uv з'єднуємо нову вершину u * (де u * означає v + V) з кожною вершиною u, додаємо ребро, пропускна здатність якого дорівнює пропускній здатності вершини u, і включаємо ребро u * -v. Пари uu * обведені овалами. Будь потік в нижній мережі безпосередньо відповідає потоку у верхній мережі, який задовольняє обмеженням на пропускні спроможності вершин.

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

Ациклічні мережі. Потрібно знайти максимальний потік в ациклической мережі. Ускладнює чи наявність циклів в транспортній мережі задачу обчислення максимального потоку?

Ми вже стикалися з багатьма прикладами завдань обробки орграфов, які істотно ускладнюються при наявності в Орграф циклів. Мабуть, найбільш наочний з них - завдання обчислення найкоротших шляхів у зважених орграфа, коли ваги ребер можуть приймати негативні значення (див. "Найкоротші шляхи" ) - яка легко вирішується за лінійний час при відсутності циклів і NP-важка, якщо цикли допускаються. Як не дивно, завдання про максимальний потік в ациклічних мережах не стає простіше.

Лемма 22.16. Завдання обчислення максимального потоку в ациклічних мережах еквівалентна стандартної задачі про максимальний потік.

Доведення. Тут також досить показати, що стандартна задача зводиться до ациклической задачі. Для будь-якої вихідної мережі з V вершинами і E ребрами збудує мережу з 2V + 2 вершинами і E + 3V ребрами, яка не тільки не містить циклів, але і володіє простою структурою.

Нехай u * означає u + V. Побудуємо двочастковий граф, в якому кожній вершині u вихідної мережі сответ-обхідних дві вершини u і u *, а кожному ребру uv вихідної мережі відповідає ребро uv * з такою ж пропускною здатністю. Потім додамо в цей двочастковий граф витік s і стік t, а для кожної вершини u вихідного графа - ребро su і ребро u * -t, пропускна здатність кожного з яких дорівнює сумарної пропускної спроможності ребер, що виходять з вершини u у вихідній мережі. Крім того, додамо ребра з u в u * з пропускною спроможністю X + 1, де X - сумарна пропускна здатність ребер вихідної мережі. Це побудова показано на Мал. 22.33 .

Щоб показати, що будь-який максимальний потік в вихідної мережі відповідає максимальному потоку в перетвореної мережі, розглянемо замість потоків перетину. Для будь-якого заданого st-перетину розміру з в вихідної мережі ми покажемо, як побудувати st-перетин розміру c + X в перетвореної мережі. А для будь-якого заданого мінімального перетину розміру c + X в перетвореної мережі ми покажемо, як побудувати st-перетин розміру з в вихідної мережі. Таким чином, якщо задано мінімальний переріз в перетвореної мережі, то відповідне йому перетин в перетвореної мережі також є мінімальним. Більш того, наш побудова дає потік, величина якого дорівнює пропускній здатності мінімального перетину, тобто це максимальний потік.

Для будь-якого заданого перетину вихідної мережі, яке відокремлює витік від стоку, нехай S - безліч вершин витоку, а T - безліч вершин стоку. Побудуємо перетин перетвореної мережі, поміщаючи вершини з S в безліч, що містить вершину s, вершини з T - в безліч, що містить вершину t, і поміщаючи для всіх u вершини u і u * в одну і ту ж частину перетину, як показано на Мал. 22.33 . Для кожної вершини u в безлічі ребер перетину міститься або su, або u * -t, а uv * міститься у великій кількості ребер перетину тоді і тільки тоді, коли ребро uv міститься в безлічі ребер перетину вихідної мережі. Отже, загальна пропускна спроможність перетину дорівнює пропускної спроможності перетину в вихідної мережі плюс Х.

Нехай задано будь мінімальне st-перетин перетвореної мережі, і нехай S * є безліч вершини s, а T * - безліч вершини t. Нам потрібно побудувати перетин з тієї ж пропускною здатністю, і щоб вершини u і u * входили в один і той же безліч для всіх u - тоді відповідність з попереднього абзацу дасть розтин у вихідній мережі, що і завершить доказ. По-перше, якщо u міститься в S *, а t міститься в T *, то uu * має бути перехресним ребром, але це неможливо: uu * не може належати ніякому мінімального перетину, оскільки перетин, що складається з усіх ребер, які відповідають ребрам вихідного графа, має меншу вартість. По-друге, якщо u міститься в T *, а u * міститься в S *, то su має належати цьому перетину, тому що це єдине ребро, що з'єднує s і u. Але ми можемо побудувати перетин тієї ж вартості, замінивши всі ребра, спрямовані з u, на su і перемістивши u в S *.

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

Мал.22.33.

Зведення до ациклической мережі

Кожна вершина u верхній мережі відповідає двом вершинам u і u * (де u * означає u + V) нижньої мережі, а кожне ребро uv верхньої мережі відповідає ребру uv * нижньої мережі. Крім того, в нижній мережі є ребра uu * без пропускних спроможностей, джерело s з ребрами, провідними в кожну вершину, що не зазначену зірочкою, і стік t, в який ведуть ребра з кожної вершини, поміченої зірочкою. Сірі і білі вершини (і ребра, що з'єднують сірі вершини з білими) ілюструють прямий взаємозв'язок перетинів в обох мережах (див. Текст).

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

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

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

напрямків ребрах, яке задовольняє умові: потік в кожному ребрі не перевищує його пропускну здатність, а сумарний потік в кожну вершину дорівнює сумарному потоку з цієї вершини. Завдання про неорієнтованому максимальний потік ( Мал. 22.34 ) Полягає в тому, щоб знайти циркуляцію, яка максимізує потік в заданому напрямку в заданому ребрі (тобто з деякою заданою вершини s в іншу задану вершину t). Мабуть, це завдання більш природно, ніж стандартна задача, відповідає моделі трубопроводу для перекачування рідин: вона дозволяє протікати рідини по трубах в обох напрямках.

Мал.22.34.

Зведення задачі про неорієнтованих мережах

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

Лемма 22.17. Завдання про максимальний потік для неорієнтованих st-мереж зводиться до задачі про максимальний потік для st-мереж.

Доведення. Нехай дана неорієнтована мережу. Побудуємо орієнтовану мережу з тими ж вершинами, в якій кожному ребру вихідної мережі відповідають два різноспрямованих ребра з пропускними здатностями, рівними пропускної здатності неориентированного ребра. Зрозуміло, що будь-який потік в вихідної мережі відповідає потоку такої ж потужності, що і в реформованій мережі. Зворотне також вірно: якщо в неориентированной мережі через ребро uv протікає потік f, а через ребро vu протікає потік g, то якщо , Можна помістити потік величини f- g в ребро uv орієнтованої мережі, а в іншому випадку помістити потік величини g -f в ребро vu. Отже, будь-який максимальний потік в орієнтованої мережі є максимальним потоком в неориентированной мережі: це побудова дає потік, а будь-який потік більшої величини в орієнтованої мережі буде відповідати деякому потоку більшої величини в неориентированной мережі; проте такого потоку не існує.

Це доказ не стверджує, що завдання про максимальний потік в неориентированной мережі еквівалентна стандартної задачі. Тобто не виключено, що обчислення максимальних потоків в неорієнтованих мережах може мати меншу трудомісткість, ніж обчислення максимальних потоків в стандартних мережах (див. Вправу 22.81).

Отже, ми можемо обробляти мережі з декількома стоками і джерелами, неорієнтовані мережі, мережі з обмеженими пропускними здатностями вершин і багато інших видів мереж (див., Наприклад, вправа 22.79), використовуючи алгоритми обчислення максимального потоку для st-мереж, розглянуті в двох попередніх розділах. Більш того, лема 22.16 стверджує, що всі ці завдання можна вирішити навіть за допомогою алгоритму, який працює тільки на ациклических мережах.

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

Допустимий потік. Припустимо, що кожній вершині транспортної мережі присвоєно вагу, який можна розглядати як пропозицію (якщо він позитивний) або як попит (якщо негативний), а сума ваг всіх вершин мережі дорівнює нулю. Будемо вважати потік допустимим (feasible), якщо різниця між припливом і відтоком кожної вершини дорівнює вазі цієї вершини (пропозицією, якщо різниця позитивна, і попиту, якщо негативна). Нехай дана така мережа, і потрібно визначити, чи можливі допустимі потоки. На рис. 22.35 Мал. 22.35 наведено приклад завдання про допустимому потоці.

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

Лемма 22.18. Завдання про допустимому потоці зводиться до задачі про максимальний потік.

Доведення. Нехай поставлена ​​задача про допустимому потоці. Побудуємо мережу з тими ж вершинами і ребрами, але без ваг у вершин. Замість цього додамо вершину витоку s, ребра з якої ведуть в кожну вершину пропозиції з вагою, рівним пропозицією відповідної вершини, і додамо вершину стоку t, в яку веде ребро з кожної вершини з попитом (так що вага такого ребра позитивний). Вирішимо задачу про максимальний потік на цій мережі. У вихідній мережі є допустимий потік тоді і тільки тоді, коли всі ребра, що виходять з джерела, і всі ребра, що ведуть у стік, заповнені при такому потоці до їх пропускних спроможностей. на Мал. 22.36 наведено приклад такого відомості.

Мал.22.35.

допустимий потік

У задачі про допустимому потоці на додаток до пропускних здібностей ребер задані величини пропозиції і попиту. Необхідно знайти такий потік, при якому відтік дорівнює сумі поставки і припливу в вершинах пропозиції, і приплив дорівнює сумі відтоку і попиту в вершинах попиту. Зліва представлена ​​задача про допустимому потоці, а правіше - три її рішення.

Розробка класів, які реалізують відомості розглянутого вище виду, може виявитися складним завданням для програмістів - головним чином тому, що оброблювані об'єкти представлені складними структурами даних. Чи потрібно будувати нову мережу, щоб звести ще одну задачу до стандартної задачі про максимальний потік? Деякі із завдань вимагають для свого вирішення додаткових даних - таких як пропускні спроможності вершин або пропозицію або попит - тому побудова стандартної мережі без цих даних може виявитися виправданим. Використання покажчиків на ребра грає тут важливу роль: якщо скопіювати ребра мережі, а потім обчислити максимальний потік, то що потім робити з результатом? Перенесення обчисленого потоку (вага кожного ребра) з однієї мережі в іншу, коли обидві мережі представлені списками суміжності - аж ніяк не тривіальне дію. Коли використовуються покажчики на ребра, нова мережа містить копії покажчиків, а не ребер, що дозволяє переслати значення потоків безпосередньо в мережу клієнта. Програма 22.6 являє собою реалізацію, яка демонструє деякі з цих моментів в класі для вирішення завдань пошуку відповідного потоку за допомогою відомості відповідно до леми 22.16.

Мал.22.36.

Зведення задачі про допустимому потоці

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

Канонічним прикладом завдання про потоках, яку неможливо вирішити за допомогою моделі максимального потоку, і яка буде розглянута в розділах 22.5 та 22.6, є розширення завдання про допустимому потоці. Додати другу зміну ваг ребер, які будуть інтерпретуватися як вартості, визначимо через них вартості потоків і поставимо задачу знайти допустимий потік мінімальної вартості. Ця модель формалізує загальну задачу розподілу товарів. Ми хочемо не тільки знати, чи можна транспортувати товари, але і яка мінімальна вартість розвезення.

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

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

Для стислості ми будемо далі називати цю задачу просто завданням двудольного зіставлення (bipartite matching), крім випадків, в яких потрібно відрізнити її від інших подібних завдань. Вона формалізує завдання працевлаштування, яка була згадана на початку цього розділу. Вершини відповідають здобувачам і роботодавцям, а ребра - відношенню "взаємної зацікавленості в працевлаштуванні". Рішення завдання двудольного зіставлення призводить до максимально можливого працевлаштування. на Мал. 22.37 показаний двочастковий граф, що моделює задачу з Мал. 22.3 .

Без графів дуже важко шукати пряме рішення задачі про дводольному зіставленні. Наприклад, ця задача зводиться до наступного комбінаторної головоломці: "знайти максимальне підмножина з безлічі пар цілих чисел (взятих з непересічних множин), щоб ні в одній парі не було однакових чисел". Приклад, наведений на Мал. 22.37 , Відповідає рішенню цієї головоломки для пар 0-6, 0-7, 0-8, 1-6 і т.д. Це завдання на перший погляд здається простою, проте, як видно на прикладі завдання пошуку Гамільтона шляху з "Види графів і їх властивості" (І багатьох інших завдань), будь-якої примітивний систематичний перебір пар до виникнення суперечності може зажадати експоненціального часу. Тобто існує занадто багато підмножин пар, щоб можна було перевірити всі варіанти; рішення цього завдання має бути досить розумним, щоб використовувати лише деякі з них. Рішення головоломок зіставлення начебто тільки що описаної або розробка алгоритмів, які здатні ефективно вирішувати будь-яку таку головоломку - дуже непрості завдання, що дозволяють продемонструвати можливості і користь моделі мережевих потоків, яка надає розумний спосіб побудови двудольного зіставлення.

Програма 22.6. Рішення завдання про допустимому потоці зведенням до задачі про максимальний потік

Даний клас вирішує завдання про допустимому потоці за допомогою зведення її до задачі про максимальний потік, використовуючи побудова, представлене на Мал. 22.36 . Конструктор приймає в якості аргументів мережу і вектор sd, індексований іменами вершин. Якщо значення sd [i] позитивно, то воно являє пропозицію в вершині i, а якщо негативно, то попит.

Як показано на Мал. 22.36 , Конструктор будує новий граф з тими ж ребрами, але з двома додатковими вершинами s і t. Ребра з s ведуть в вузли з пропозицією, а ребра з вершин з попитом ведуть в вершину t. Потім він знаходить максимальний потік і перевіряє, чи заповнені всі додаткові ребра до їх пропускних спроможностей.

#include "MAXFLOW.cc" template <class Graph, class Edge> class FEASIBLE {const Graph & G; void freeedges (const Graph & F, int v) {typename Graph :: adjIterator A (F, v); for (EDGE * e = A.beg ();! A.end (); e = A.nxt ()) delete e; } Public: FEASIBLE (const Graph & G, vector <int> sd): G (G) {Graph F (GV () + 2); for (int v = 0; v <GV (); v ++) {typename Graph :: adjIterator A (G, v); for (EDGE * e = A.beg ();! A.end (); e = A.nxt ()) F.insert (e); } Int s = GV (), t = GV () + 1; for (int i = 0; i <GV (); i ++) if (sd [i]> = 0) F.insert (new EDGE (s, i, sd [i])); else F.insert (new EDGE (i, t, -sd [i])); MAXFLOW <Graph, Edge> (F, s, t); freeedges (F, s); freeedges (F, t); }};
Мал. 22.37. дводольні зіставлення

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

Лемма 22.19. Завдання про дводольному зіставленні зводиться до задачі про максимальний потік.

Доведення. Для заданої задачі двудольного зіставлення побудуємо екземпляр завдання про максимальний потік: проведемо всі ребра з одного безлічі в інше, додамо витік, з якого ребра ведуть в усі елементи одного безлічі, і стік, в який ведуть ребра з елементів іншого безлічі. Щоб перетворити отриманий орграф в мережу, призначимо кожному ребру пропускну здатність, що дорівнює 1. Це побудова показано на Мал. 22.38 .

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

Например, на Мал. 22.38 алгоритм обчислення максимального потоку з використанням розширюють шляхів може використовувати шляхи s-0-6-t, s-1-7-t, s-2-8-t, s-4-9-t, s-5-10-t і s-3-6-0-7-1-11-t для обчислення зіставлення 0-7, 1-11, 2-8, 3-6, 4-9 і 5-10. Отже, існує спосіб працевлаштування всіх студентів в задачі, показаної на Мал. 22.3 .

Мал.22.38.

Зведення задачі про дводольному зіставленні

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