💞 Двочасткове паросполучення
Збільшувальні шляхи (Хопкрофт–Карп)
Керування
Статистика
Розмір паросполучення
0
Максимум можливий
6
Стан
Готово
Довідка та теорія

Двочасткове паросполучення з'єднує вершини з двох непересічних множин — L (кандидати) та R (вакансії) — ребрами, що йдуть лише між цими множинами. Паросполучення — це набір ребер без спільних кінців; мета — знайти паросполучення максимального розміру.

Збільшувальні шляхи

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

Чому переключення допомагає

Заміна статусу зіставлене/незіставлене для кожного ребра на збільшувальному шляху перетворює обидва його кінці на зіставлені вершини, залишаючи кожну внутрішню вершину зіставленою (лише з іншим сусідом). Чистий ефект — +1 до розміру паросполучення. Паросполучення є максимальним точно тоді, коли жодного збільшувального шляху не існує — це лема Берже.

Складність Хопкрофта–Карпа

Пошук одного збільшувального шляху одним DFS з кожної незіставленої вершини коштує O(E), а може знадобитися до V пошуків, що дає загалом O(V·E). Хопкрофт–Карп натомість знаходить максимальний пакет найкоротших, вершинно-неперетинних збільшувальних шляхів за кожну фазу (один BFS для визначення довжини найкоротшого шляху, потім DFS для видобування неперетинних шляхів), потребуючи лише O(√V) фаз — загалом O(E√V).

Теорема Кеніга

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

Про двочасткове паросполучення

Автор: Команда MySimulator · Редакційна перевірка: Редакція MySimulator

Оновлено: 11 липня 2026 р.

Двочастковий граф розділяє свої вершини на дві непересічні множини — тут це кандидати ліворуч і вакансії праворуч — а ребра з'єднують лише вершини з різних множин, ніколи всередині однієї. Паросполучення — це підмножина ребер, у якій жодна вершина не зустрічається двічі; максимальне паросполучення — це найбільша така підмножина, можлива для даного графа. Класичний спосіб збільшити паросполучення — повторно шукати збільшувальний шлях: маршрут, що починається і закінчується в незіставлених вершинах і чергує незіставлені та зіставлені ребра. Переключення кожного ребра вздовж цього шляху збільшує розмір паросполучення рівно на одиницю, а паросполучення є доведено максимальним саме тоді, коли жодного збільшувального шляху більше не існує. Виконання такого пошуку з кожної незіставленої вершини по одному разу займає O(V·E) часу; алгоритм Хопкрофта–Карпа покращує це до O(E√V), знаходячи за одну фазу кілька найкоротших шляхів замість одного. Окрім теорії графів, двочасткове паросполучення моделює розподіл робочих завдань, розподіл курсів і задачі стабільного паросполучення, що лежать в основі систем розподілу до шкіл та лікарняних резидентур.

Часті запитання

Що таке збільшувальний шлях у двочастковому паросполученні?

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

Чому переключення збільшувального шляху збільшує розмір паросполучення на одиницю?

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

Наскільки швидший алгоритм Хопкрофта–Карпа порівняно з наївним підходом?

Наївний підхід — повторний пошук одного збільшувального шляху методом DFS з кожної незіставленої вершини — у найгіршому випадку потребує O(V·E) часу, оскільки може знадобитися до V шляхів, а кожен пошук коштує O(E). Натомість Хопкрофт–Карп на кожній фазі одним проходом BFS+DFS знаходить максимальний набір найкоротших, вершинно-неперетинних збільшувальних шляхів, тому потребує лише O(√V) фаз — загалом O(E√V), що дає суттєве прискорення на великих графах.

Які реальні задачі розв'язуються за допомогою двочасткового паросполучення?

Двочасткове паросполучення лежить в основі розподілу завдань і посад (зіставлення працівників із сумісними ролями), вступу до університетів і розподілу лікарів-резидентів по лікарнях (попередник алгоритму стабільного паросполучення Гейла–Шеплі), а також задач мережевого потоку, як-от планування та розподіл ресурсів, де максимізація кількості зіставлених пар безпосередньо максимізує ефективне використання обмежених ресурсів.