Довідка та теорія
Дводольний граф має дві групи вершин — тут лівий і правий стовпці — з ребрами лише між групами. Парування обирає ребра так, щоб жодна вершина не використовувалася двічі.
Доповнювальні шляхи
Доповнювальний шлях починається й закінчується у
неспарованих вершинах і чергує ребра
непарне → парне → непарне …. Перевертання кожного
ребра вздовж нього (парне ↔ непарне) додає рівно одне ребро до
парування.
Алгоритм
- Для кожної неспарованої лівої вершини шукати доповнювальний шлях.
- Якщо знайдено — перевернути; парування зростає на одиницю.
- Повторювати, доки доповнювального шляху не лишиться.
Чому це оптимально
Теорема Берджа: парування максимальне саме тоді, коли в нього немає доповнювального шляху. Тож коли пошук нічого не дає, парування доведено максимальне.
Кеніг і складність
За теоремою Кеніга максимальне парування дорівнює
мінімальному вершинному покриттю. Класичний метод доповнювальних
шляхів працює за O(V·E); Гопкрофт–Карп
покращує це до O(E·√V), доповнюючи багато
найкоротших шляхів за фазу.
Застосування
Призначення працівників на роботи, студентів на проєкти, нирок реципієнтам чи реклами на слоти — усе це парування у дводольному графі.
Часті питання
Що таке дводольний граф?
Граф, вершини якого розбиті на дві неперетинні множини (ліву й праву), тож кожне ребро з'єднує ліву вершину з правою. Жодне ребро не з'єднує дві вершини з одного боку.
Що таке парування?
Набір ребер без спільних кінців, тож кожна вершина має щонайбільше одного партнера. Максимальне парування має найбільшу можливу кількість ребер.
Що таке доповнювальний шлях?
Шлях між двома неспарованими вершинами, що чергує непарні й парні ребра. Перевертання його ребер збільшує розмір парування рівно на одиницю.
Як знаходять максимальне парування?
Багаторазово шукають доповнювальний шлях від кожної неспарованої лівої вершини й перевертають його. Коли жодного не лишається, теорема Берджа гарантує максимальність.
Що таке теорема Берджа?
Парування максимальне тоді й лише тоді, коли воно не має доповнювального шляху. Саме тому алгоритм може зупинитися, щойно пошук зазнає невдачі.
Що таке досконале парування?
Парування, що спаровує кожну вершину, не лишаючи жодної неспарованою. Воно потребує рівних за розміром боків і ребер, що дозволяють повне призначення.
Як це пов'язано із задачею про призначення?
Призначення працівників на роботи, студентів на проєкти чи органів реципієнтам — це парування у дводольному графі: кожна сумісна пара є ребром.
Що таке угорський метод і Гопкрофта–Карпа?
Обидва використовують доповнювальні шляхи. Угорський метод також розв'язує зважене призначення на мінімальну вартість; Гопкрофт–Карп знаходить багато найкоротших шляхів за фазу для часу O(E·√V).
Чи має значення порядок пошуку?
Підсумковий розмір парування завжди той самий, але конкретні вибрані ребра й кількість кроків можуть різнитися залежно від порядку обробки.
Де застосовують парування у дводольному графі?
У плануванні робіт і змін, розміщенні реклами, обміні нирками, призначенні шкіл та інтернатур, мережевих потоках і будь-якому паруванні з обмеженнями сумісності.