Означення 1. Граф G = (V, E) називають дводольним, якщо його множину вершин V можна розбити на підмножини (їх називають долі) X i Y, що не перетинаються, а кожне ребро е = {x, у} з E сполучає вершини х з Х і y з Y. Такий граф будемо позначати (X, Y, E).

Розбиття V на X i Y неоднозначне. Надалі обмежимося розглядом дводольних графів, вважаючи, що таке розбиття стале.

Означення 2. Запровадимо такі поняття.

1. Сполукою пар (вершин) у графі називають довільну множину його pебер M, при якій кожна вершина графа інциндентна не більше, ніж одному ребру з M.

2. Сполуку пар M називають повною, якщо всі вершини графа є кінцями ребер M.

3. Сполуку пар М у графі G називають найбільшою (максимальною), якщо для довільної сполуки пар М' у графі G справджується нерівність: | M' | ≤ | M |. Інакше кажучи, найбільшу за кількістю ребер сполуку пар називають найбільшою.

4. Сполуку пар М у дводольному графі G = (X, Y, E) називають повною, якщо для довільного х з Х існує y з Y, при яких ребро {x, у} належить до М.

Повна сполука пар, якщо вона існує, є максимальною.

Для знаходження максимальної сполуки пар у дводольному графі G = (X, Y, E) можна модифікувати алгоритм Форда-Фалкерсона таким чином:

• кожне ребро графа перетворити на дугу, спрямовану з X в Y;
• долучити дві нові вершини а і z;
• вершину а (джерело) сполучити дугою з кожною вершиною з X;
• кожну вершину з Y сполучити дугою з вершиною z (стоком);
• кожній дузі приписати пропускну спроможність 1;
• здійснити пошук максимального потоку з джерела а до стоку z;
• за ребра сполуки пар взяти ті ребра початкового графа, яким відповідає потік 1.

• кажуть, що М сполучає вершину x з вершиною у, якщо {x, у} належить до M;

• вершини, що не належать жодному ребру сполуки пар, називають вільними (щодо М), а решту вершин — насиченими (щодо M).

Означення 4. Для даної сполуки nap М у графі G аргументальним чи М-черговим ланцюгом називають таку послідовність вершин і ребер:

• k — невід'ємне ціле парне число;₁
• вершини x₀, …, x_k, y₁, …, y_{k + 1} різні;
• вершини x₀ і y_{k + 1} — вільні, а решта вершин — насичені щодо сполуки пар М;
• ребра {y_j, x_j}, j = 1, 2, …, k – 1 належать до М, а решта ребер до М не належать.

Теорема 1 (Берж). Сполука пар M у дводольному графі G є максимальною тоді й лише тоді, коли в G не існує M-чергового ланцюга.

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

Означення 5. Нехай M — сполука пар у графі G. Графом M-чергових ланцюгів називають граф, усі вершини й ребра якого належать до M-чергових ланцюгів. Такий граф позначають G(M).

Алгоритм побудови графа М-чергових ланцюгів

Алгоритм для дводольного графа (X, Y, E) здійснюють за рівнями j = 0, 1, 2, …, використовуючи процес, схожий на пошук у ширину.

1. Граф рівня 0 містить усі вершини з X, що не є кінцями ребер з М.

2. На рівні з непарним номером j долучаємо нові вершини, сполучені з вершинами рівня (j – 1) ребром, що не належить до сполуки пар (це ребро також долучаємо у граф).

3. На рівні з парним номером j долучаємо нові вершини, сполучені з вершинами рівня (j – 1) ребром, що належить до сполуки пар (це ребро також долучаємо у граф).

4. Побудову (кроки 2–3) продовжуємо доти, поки до графа М-чергових ланцюгів можна долучити нові вершини.

Останній пункт можна модифікувати «… до побудови найкоротших М-чергових ланцюгів», щоб отримати граф таких ланцюгів.

Алгоритм Хопкрофта-Карпа
побудови максимальної сполуки пар

1. Утворюємо довільну сполуку пар M у графі G.

2. Будуємо граф найкоротших M-чергових ланцюгів.

3. Будуємо максимальну за вмістом множину {P₁, P₂, …, P_k}, що містить M-чергові ланцюги в G(M), що не мають спільних вершин. Інакше кажучи, для довільного M-чергового ланцюга P в G(M) існує j (1 ≤ j ≤ k), при якому ланцюги P и P_j містять принаймні одну спільну вершину.

4. Замінюємо M на симетричну різницю M і P_j при j = 1, 2, …, k.

5. Повторюємо кроки 2–4 доти, поки у графі G існує хоча б одна М-черговий ланцюг.

Поданий алгоритм втілено у програмі мовою Turbo Pascal 7.0 для розв'язання задачі про призначення.