Алгоритм Куна для максимального парування в дводольному графі

Задача

Задано дводольний граф $G$, що містить $n$ вершин і $m$ ребер. Знайти максимальне парування, тобто вибрати якомога більше ребер так, щоб жодне вибране ребро не мало спільної вершини з будь-яким іншим вибраним ребром.

Коли підходить цей алгоритм?

• Граф дводольний, а потрібно максимальне за потужністю парування (без ваг на ребрах)? (якщо ребра мають ваги і потрібне парування мінімальної/максимальної вартості → Угорський алгоритм)
• Не впевнені, що граф дводольний? (спершу → Перевірка на дводольність)
• Достатньо $O(VE)$? (для щільних графів зведення до максимального потоку дає швидші $O(E\sqrt{V})$)

Опис алгоритму

Необхідні означення

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

• Максимальне за включенням парування — це таке парування $M$ графа $G$, яке не є підмножиною жодного іншого парування.

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

• Шлях довжини $k$ тут означає простий шлях (тобто такий, що не містить повторюваних вершин чи ребер), який містить $k$ ребер, якщо не зазначено інше.

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

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

• Симетрична різниця (також відома як диз'юнктивне об'єднання) множин $A$ і $B$, що позначається $A \oplus B$, — це множина всіх елементів, які належать рівно одній з множин $A$ чи $B$, але не обом одночасно. Тобто $A \oplus B = (A - B) \cup (B - A) = (A \cup B) - (A \cap B)$.

Лема Берже

Цю лему довів французький математик Клод Берже у 1957 році, хоча її вже помітили данський математик Юліус Петерсен у 1891 році та угорський математик Денеш Кеніг у 1931 році.

Формулювання

Парування $M$ є найбільшим $\Leftrightarrow$ не існує збільшувального ланцюга відносно парування $M$.

Доведення

Обидві сторони цієї бі-імплікації доведемо від супротивного.

1. Парування $M$ є найбільшим $\Rightarrow$ не існує збільшувального ланцюга відносно парування $M$.

   Нехай існує збільшувальний ланцюг $P$ відносно даного найбільшого парування $M$. Цей збільшувальний ланцюг $P$ обов'язково матиме непарну довжину, маючи на одне ребро, що не належить $M$, більше, ніж кількість його ребер, які також належать $M$. Ми будуємо нове парування $M'$, включаючи до нього всі ребра початкового парування $M$, крім тих, що також належать $P$, а також ребра з $P$, які не належать $M$. Це коректне парування, бо початкова й кінцева вершини $P$ ненасичені паруванням $M$, а решта вершин насичені лише паруванням $P \cap M$. Це нове парування $M'$ матиме на одне ребро більше, ніж $M$, а отже, $M$ не могло бути найбільшим.

   Формально, для заданого збільшувального ланцюга $P$ відносно деякого найбільшого парування $M$ парування $M' = P \oplus M$ є таким, що $|M'| = |M| + 1$, — суперечність.

2. Парування $M$ є найбільшим $\Leftarrow$ не існує збільшувального ланцюга відносно парування $M$.

   Нехай існує парування $M'$ більшої потужності, ніж $M$. Розглянемо симетричну різницю $Q = M \oplus M'$. Підграф $Q$ уже не обов'язково є паруванням. Будь-яка вершина в $Q$ має максимальний степінь $2$, що означає: усі компоненти зв'язності в ньому є однією з трьох —

   • ізольована вершина
   • (простий) шлях, ребра якого почергово належать $M$ і $M'$
   • цикл парної довжини, ребра якого почергово належать $M$ і $M'$

   Оскільки потужність $M'$ більша за потужність $M$, то $Q$ має більше ребер з $M'$, ніж з $M$. За принципом Діріхле принаймні одна компонента зв'язності буде шляхом, що має більше ребер з $M'$, ніж з $M$. Оскільки будь-який такий шлях є чергуваним, його початкова й кінцева вершини ненасичені паруванням $M$, що робить його збільшувальним ланцюгом для $M$, а це суперечить припущенню.   $\blacksquare$

Алгоритм Куна

Алгоритм Куна — це пряме застосування леми Берже. По суті, його можна описати так:

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

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

Алгоритм зручніше описувати, якщо припустити, що вхідний граф уже розбитий на дві частки (хоча насправді алгоритм можна реалізувати так, щоб вхідний граф не був явно розбитий на дві частки).

Алгоритм переглядає всі вершини $v$ першої частки графа: $v = 1 \ldots n_1$. Якщо поточна вершина $v$ уже насичена поточним паруванням (тобто якесь суміжне з нею ребро вже вибране), то пропускаємо цю вершину. Інакше алгоритм намагається наситити цю вершину, для чого запускає пошук збільшувального ланцюга, що починається з цієї вершини.

Пошук збільшувального ланцюга виконується за допомогою спеціального обходу в глибину чи в ширину (зазвичай для простоти реалізації використовують обхід у глибину). Спочатку обхід у глибину перебуває в поточній ненасиченій вершині $v$ першої частки. Переглянемо всі ребра з цієї вершини. Нехай поточне ребро — це ребро $(v, to)$. Якщо вершина $to$ ще не насичена паруванням, то нам пощастило знайти збільшувальний ланцюг: він складається з єдиного ребра $(v, to)$; у цьому випадку ми просто включаємо це ребро до парування й припиняємо пошук збільшувального ланцюга з вершини $v$. Інакше, якщо $to$ вже насичена деяким ребром $(to, p)$, то підемо вздовж цього ребра: таким чином ми спробуємо знайти збільшувальний ланцюг, що проходить ребрами $(v, to),(to, p), \ldots$. Для цього просто переходимо до вершини $p$ у нашому обході — тепер ми намагаємося знайти збільшувальний ланцюг з цієї вершини.

Отже, цей обхід, запущений з вершини $v$, або знайде збільшувальний ланцюг і тим самим наситить вершину $v$, або не знайде такого збільшувального ланцюга (а отже, цю вершину $v$ не можна наситити).

Після того як усі вершини $v = 1 \ldots n_1$ переглянуто, поточне парування буде найбільшим.

Час роботи

Алгоритм Куна можна розглядати як серію з $n$ запусків обходу в глибину/ширину на всьому графі. Тому весь алгоритм виконується за час $O(nm)$, що в найгіршому випадку дорівнює $O(n^3)$.

Однак цю оцінку можна трохи покращити. Виявляється, для алгоритму Куна важливо, яку частку графа обрано першою, а яку — другою. Справді, у описаній вище реалізації обхід у глибину/ширину запускається лише з вершин першої частки, тож увесь алгоритм виконується за час $O(n_1m)$, де $n_1$ — кількість вершин першої частки. У найгіршому випадку це $O(n_1 ^ 2 n_2)$ (де $n_2$ — кількість вершин другої частки). Це показує, що вигідніше, коли перша частка містить менше вершин, ніж друга. На дуже незбалансованих графах (коли $n_1$ і $n_2$ дуже відрізняються) це призводить до суттєвої різниці в часі роботи.

Реалізація

Стандартна реалізація

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

Тут $n$ — кількість вершин у першій частці, $k$ — у другій частці, $g[v]$ — це список ребер з вершини першої частки (тобто список номерів вершин, до яких ведуть ці ребра з $v$). Вершини в обох частках нумеруються незалежно, тобто вершини першої частки нумеруються $1 \ldots n$, а вершини другої — $1 \ldots k$.

Далі є два допоміжні масиви: $\rm mt$ і $\rm used$. Перший — $\rm mt$ — містить інформацію про поточне парування. Для зручності програмування ця інформація зберігається лише для вершин другої частки: $\textrm{mt[} i \rm]$ — це номер вершини першої частки, з'єднаної ребром з вершиною $i$ другої частки (або $-1$, якщо з неї не виходить ребро парування). Другий масив — $\rm used$: звичайний масив «відвідувань» вершин в обході в глибину (він потрібен лише для того, щоб обхід у глибину не заходив до однієї й тієї самої вершини двічі).

Функція $\textrm{try\_kuhn}$ — це обхід у глибину. Вона повертає $\rm true$, якщо їй вдалося знайти збільшувальний ланцюг з вершини $v$, і вважається, що ця функція вже виконала чергування парування вздовж знайденого ланцюга.

Усередині функції переглядаються всі ребра, що виходять з вершини $v$ першої частки, а потім перевіряється таке: якщо це ребро веде до ненасиченої вершини $to$, або якщо ця вершина $to$ насичена, але збільшувальний ланцюг можна знайти, рекурсивно запустившись з $\textrm{mt[}to \rm ]$, то ми кажемо, що знайшли збільшувальний ланцюг, і перед поверненням з функції з результатом $\rm true$ чергуємо поточне ребро: перенаправляємо ребро, суміжне з $to$, на вершину $v$.

Головна програма спочатку вказує, що поточне парування порожнє (список $\rm mt$ заповнюється числами $-1$). Потім вершина $v$ першої частки шукається через $\textrm{try\_kuhn}$, і з неї запускається обхід у глибину, попередньо обнуливши масив $\rm used$.

Варто зауважити, що розмір парування легко отримати як кількість викликів $\textrm{try\_kuhn}$ у головній програмі, що повернули результат $\rm true$. Саме шукане найбільше парування міститься в масиві $\rm mt$.

C++

int n, k;
vector<vector<int>> g;
vector<int> mt;
vector<bool> used;

bool try_kuhn(int v) {
    if (used[v])
        return false;
    used[v] = true;
    for (int to : g[v]) {
        if (mt[to] == -1 || try_kuhn(mt[to])) {
            mt[to] = v;
            return true;
        }
    }
    return false;
}

int main() {
    //... читання графа ...

    mt.assign(k, -1);
    for (int v = 0; v < n; ++v) {
        used.assign(n, false);
        try_kuhn(v);
    }

    for (int i = 0; i < k; ++i)
        if (mt[i] != -1)
            printf("%d %d\n", mt[i] + 1, i + 1);
}

Python

import sys

# try_kuhn — це рекурсивний обхід у глибину завглибшки до n,
# тож піднімаємо стандартний ліміт рекурсії Python (типово 1000)
sys.setrecursionlimit(1 << 20)

n: int           # кількість вершин першої частки
k: int           # кількість вершин другої частки
g: list[list[int]]  # списки суміжності для вершин першої частки
mt: list[int]    # mt[i] — вершина першої частки, парована з i-ю вершиною другої частки
used: list[bool]


def try_kuhn(v: int) -> bool:
    if used[v]:
        return False
    used[v] = True
    for to in g[v]:
        if mt[to] == -1 or try_kuhn(mt[to]):
            mt[to] = v
            return True
    return False


def main() -> None:
    global mt, used
    # ... читання графа ...

    mt = [-1] * k
    for v in range(n):
        used = [False] * n
        try_kuhn(v)

    for i in range(k):
        if mt[i] != -1:
            print(mt[i] + 1, i + 1)

TypeScript

let n: number; // кількість вершин першої частки
let k: number; // кількість вершин другої частки
let g: number[][]; // списки суміжності для вершин першої частки
let mt: number[]; // mt[i] — вершина першої частки, парована з i-ю вершиною другої частки
let used: boolean[];

function tryKuhn(v: number): boolean {
  if (used[v]) {
    return false;
  }
  used[v] = true;
  for (const to of g[v]) {
    if (mt[to] === -1 || tryKuhn(mt[to])) {
      mt[to] = v;
      return true;
    }
  }
  return false;
}

function main(): void {
  // ... читання графа ...

  mt = new Array(k).fill(-1);
  for (let v = 0; v < n; v++) {
    used = new Array(n).fill(false);
    tryKuhn(v);
  }

  for (let i = 0; i < k; i++) {
    if (mt[i] !== -1) {
      console.log(mt[i] + 1, i + 1);
    }
  }
}

Go

var (
    n    int   // кількість вершин першої частки
    k    int   // кількість вершин другої частки
    g    [][]int // списки суміжності для вершин першої частки
    mt   []int // mt[i] — вершина першої частки, парована з i-ю вершиною другої частки
    used []bool
)

func tryKuhn(v int) bool {
    if used[v] {
        return false
    }
    used[v] = true
    for _, to := range g[v] {
        if mt[to] == -1 || tryKuhn(mt[to]) {
            mt[to] = v
            return true
        }
    }
    return false
}

func main() {
    // ... читання графа ...

    mt = make([]int, k)
    for i := range mt {
        mt[i] = -1
    }
    for v := 0; v < n; v++ {
        used = make([]bool, n)
        tryKuhn(v)
    }

    for i := 0; i < k; i++ {
        if mt[i] != -1 {
            fmt.Println(mt[i]+1, i+1)
        }
    }
}

Повторимо ще раз, що алгоритм Куна легко реалізувати так, щоб він працював на графах, про які відомо, що вони дводольні, але явного розбиття їх на дві частки не дано. У цьому випадку доведеться відмовитися від зручного поділу на дві частки й зберігати всю інформацію для всіх вершин графа. Для цього масив списків $g$ тепер задається не лише для вершин першої частки, а для всіх вершин графа (звісно, тепер вершини обох часток нумеруються в спільній нумерації — від $1$ до $n$). Масиви $\rm mt$ і $\rm used$ тепер також визначаються для вершин обох часток і, відповідно, їх потрібно підтримувати в такому стані.

Покращена реалізація

Модифікуємо алгоритм так. Перед головним циклом алгоритму ми знайдемо довільне парування якимось простим алгоритмом (простим евристичним алгоритмом), і лише потім виконаємо цикл з викликами функції $\textrm{try\_kuhn}()$, яка покращить це парування. У результаті алгоритм працюватиме помітно швидше на випадкових графах — бо в більшості графів за допомогою евристики легко знайти парування достатньо великого розміру, а потім покращити знайдене парування до найбільшого за допомогою звичайного алгоритму Куна. Таким чином, ми заощадимо на запуску обходу в глибину з тих вершин, які ми вже включили до поточного парування за допомогою евристики.

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

Зверніть увагу, що головний цикл доведеться трохи модифікувати. Оскільки під час виклику функції $\textrm{try\_kuhn}$ у головному циклі припускається, що поточна вершина ще не включена до парування, потрібно додати відповідну перевірку.

У реалізації зміниться лише код у функції $\textrm{main}()$:

C++

int main() {
    // ... читання графа ...

    mt.assign(k, -1);
    vector<bool> used1(n, false);
    for (int v = 0; v < n; ++v) {
        for (int to : g[v]) {
            if (mt[to] == -1) {
                mt[to] = v;
                used1[v] = true;
                break;
            }
        }
    }
    for (int v = 0; v < n; ++v) {
        if (used1[v])
            continue;
        used.assign(n, false);
        try_kuhn(v);
    }

    for (int i = 0; i < k; ++i)
        if (mt[i] != -1)
            printf("%d %d\n", mt[i] + 1, i + 1);
}

Python

def main() -> None:
    global mt, used
    # ... читання графа ...

    mt = [-1] * k
    used1 = [False] * n
    # Евристика: жадібно беремо для кожної вершини перше вільне ребро
    for v in range(n):
        for to in g[v]:
            if mt[to] == -1:
                mt[to] = v
                used1[v] = True
                break
    for v in range(n):
        if used1[v]:
            continue
        used = [False] * n
        try_kuhn(v)

    for i in range(k):
        if mt[i] != -1:
            print(mt[i] + 1, i + 1)

TypeScript

function main(): void {
  // ... читання графа ...

  mt = new Array(k).fill(-1);
  const used1: boolean[] = new Array(n).fill(false);
  // Евристика: жадібно беремо для кожної вершини перше вільне ребро
  for (let v = 0; v < n; v++) {
    for (const to of g[v]) {
      if (mt[to] === -1) {
        mt[to] = v;
        used1[v] = true;
        break;
      }
    }
  }
  for (let v = 0; v < n; v++) {
    if (used1[v]) continue;
    used = new Array(n).fill(false);
    tryKuhn(v);
  }

  for (let i = 0; i < k; i++) {
    if (mt[i] !== -1) {
      console.log(mt[i] + 1, i + 1);
    }
  }
}

Go

func main() {
    // ... читання графа ...

    mt = make([]int, k)
    for i := range mt {
        mt[i] = -1
    }
    used1 := make([]bool, n)
    // Евристика: жадібно беремо для кожної вершини перше вільне ребро
    for v := 0; v < n; v++ {
        for _, to := range g[v] {
            if mt[to] == -1 {
                mt[to] = v
                used1[v] = true
                break
            }
        }
    }
    for v := 0; v < n; v++ {
        if used1[v] {
            continue
        }
        used = make([]bool, n)
        tryKuhn(v)
    }

    for i := 0; i < k; i++ {
        if mt[i] != -1 {
            fmt.Println(mt[i]+1, i+1)
        }
    }
}

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

Зауваження

• Алгоритм Куна є підпрограмою в угорському алгоритмі, також відомому як алгоритм Куна-Манкреса.
• Алгоритм Куна працює за час $O(nm)$. Загалом його просто реалізувати, проте для задачі максимального дводольного парування існують ефективніші алгоритми — як-от алгоритм Гопкрофта-Карпа-Карзанова, який працює за час $O(\sqrt{n}m)$.
• Задача про мінімальне вершинне покриття є NP-складною для загальних графів. Однак теорема Кеніга стверджує, що для дводольних графів потужність максимального парування дорівнює потужності мінімального вершинного покриття. Отже, ми можемо використовувати алгоритми максимального дводольного парування, щоб розв'язувати задачу про мінімальне вершинне покриття за поліноміальний час для дводольних графів.

Задачі для практики

• Kattis - Gopher II
• Kattis - Borders

Відеоматеріали