Куны алгоритм - Хамгийн их хоёр хэсэгт тааруулалт¶

Бодлого¶

Бидэнд $n$ орой, $m$ ирмэг агуулсан хоёр хэсэгт граф $G$ өгөгдсөн. Хамгийн их тааруулалтыг ол, өөрөөр хэлбэл сонгосон ямар ч ирмэг өөр сонгосон ирмэгтэй орой хуваалцахгүй байхаар аль болох олон ирмэг сонго.

Алгоритмын тайлбар¶

Шаардлагатай тодорхойлолтууд¶

Тааруулалт $M$ гэдэг нь графын хосоороо зэргэлдээ биш ирмэгүүдийн олонлог юм (өөрөөр хэлбэл олонлогоос нэгээс олонгүй ирмэг граф $M$-ийн дурын оройтой инцидент байх ёстой). Тааруулалтын хүчин чадал гэдэг нь түүн дэх ирмэгийн тоо юм. Тааруулалтаас зэргэлдээ ирмэгтэй бүх орой (өөрөөр хэлбэл $M$-ээр үүсгэгдсэн дэд графт яг нэг зэрэгтэй орой) энэ тааруулалтаар ханасан гэж нэрлэгдэнэ.
Максимал тааруулалт гэдэг нь өөр ямар ч тааруулалтын дэд олонлог биш граф $G$-ийн тааруулалт $M$ юм.
Хамгийн их тааруулалт (хамгийн их хүчин чадалтай тааруулалт гэж бас нэрлэгддэг) гэдэг нь боломжит хамгийн олон ирмэг агуулах тааруулалт юм. Хамгийн их тааруулалт бүр нь максимал тааруулалт байна.
Энд $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$-ийн хувьд нэмэгдүүлэх зам байхгүй.

Баталгаа¶

Хоёр талт импликацийн хоёр талыг хоёуланг нь зөрчлөөр батална.

Тааруулалт $M$ хамгийн их $\Rightarrow$ тааруулалт $M$-ийн хувьд нэмэгдүүлэх зам байхгүй.

Өгөгдсөн хамгийн их тааруулалт $M$-ийн хувьд нэмэгдүүлэх зам $P$ байна гэж үзье. Энэ нэмэгдүүлэх зам $P$ заавал сондгой урттай байх ба $M$-д байхгүй ирмэг нь $M$-д мөн байгаа ирмэгийнхээ тооноос нэгээр илүү байна. Бид анхны тааруулалт $M$ дэх $P$-д мөн байгаагаас бусад бүх ирмэг, мөн $P$ дэх $M$-д байхгүй ирмэгүүдийг оруулан шинэ тааруулалт $M'$ үүсгэнэ. Энэ нь зөв тааруулалт болно, учир нь $P$-ийн эхлэлийн ба төгсгөлийн орой $M$-ээр ханаагүй бөгөөд бусад орой нь зөвхөн тааруулалт $P \cap M$-ээр ханасан байна. Энэ шинэ тааруулалт $M'$ нь $M$-ээс нэг ирмэгээр илүү байх тул $M$ хамгийн их байж чадахгүй байсан.

Албан ёсоор ямар нэг хамгийн их тааруулалт $M$-ийн хувьд нэмэгдүүлэх зам $P$ өгөгдсөн үед тааруулалт $M' = P \oplus M$ нь $|M'| = |M| + 1$ байх ба энэ нь зөрчил юм.
Тааруулалт $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$ маш өөр байх үед) энэ нь ажиллах хугацаанд мэдэгдэхүйц ялгаа болж хувирна.

Implementation¶

Standard implementation¶

Let us present here an implementation of the above algorithm based on depth-first traversal and accepting a bipartite graph in the form of a graph explicitly split into two parts. This implementation is very concise, and perhaps it should be remembered in this form.

Here $n$ is the number of vertices in the first part, $k$ - in the second part, $g[v]$ is the list of edges from the top of the first part (i.e. the list of numbers of the vertices to which these edges lead from $v$). The vertices in both parts are numbered independently, i.e. vertices in the first part are numbered $1 \ldots n$, and those in the second are numbered $1 \ldots k$.

Then there are two auxiliary arrays: $\rm mt$ and $\rm used$. The first - $\rm mt$ - contains information about the current matching. For convenience of programming, this information is contained only for the vertices of the second part: $\textrm{mt[} i \rm]$ - this is the number of the vertex of the first part connected by an edge with the vertex $i$ of the second part (or $-1$, if no matching edge comes out of it). The second array is $\rm used$: the usual array of "visits" to the vertices in the depth-first traversal (it is needed just so that the depth-first traversal does not enter the same vertex twice).

A function $\textrm{try_kuhn}$ is a depth-first traversal. It returns $\rm true$ if it was able to find an augmenting path from the vertex $v$, and it is considered that this function has already performed the alternation of matching along the found chain.

Inside the function, all the edges outgoing from the vertex $v$ of the first part are scanned, and then the following is checked: if this edge leads to an unsaturated vertex $to$, or if this vertex $to$ is saturated, but it is possible to find an increasing chain by recursively starting from $\textrm{mt[}to \rm ]$, then we say that we have found an augmenting path, and before returning from the function with the result $\rm true$, we alternate the current edge: we redirect the edge adjacent to $to$ to the vertex $v$.

The main program first indicates that the current matching is empty (the list $\rm mt$ is filled with numbers $-1$). Then the vertex $v$ of the first part is searched by $\textrm{try_kuhn}$, and a depth-first traversal is started from it, having previously zeroed the array $\rm used$.

It is worth noting that the size of the matching is easy to get as the number of calls $\textrm{try_kuhn}$ in the main program that returned the result $\rm true$. The desired maximum matching itself is contained in the array $\rm mt$.

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() {
    //... reading the graph ...

    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);
}

We repeat once again that Kuhn's algorithm is easy to implement in such a way that it works on graphs that are known to be bipartite, but their explicit splitting into two parts has not been given. In this case, it will be necessary to abandon the convenient division into two parts, and store all the information for all vertices of the graph. For this, an array of lists $g$ is now specified not only for the vertices of the first part, but for all the vertices of the graph (of course, now the vertices of both parts are numbered in a common numbering - from $1$ to $n$). Arrays $\rm mt$ and are $\rm used$ are now also defined for the vertices of both parts, and, accordingly, they need to be kept in this state.

Improved implementation¶

Let us modify the algorithm as follows. Before the main loop of the algorithm, we will find an arbitrary matching by some simple algorithm (a simple heuristic algorithm), and only then we will execute a loop with calls to the $\textrm{try_kuhn}()$ function, which will improve this matching. As a result, the algorithm will work noticeably faster on random graphs - because in most graphs, you can easily find a matching of a sufficiently large size using heuristics, and then improve the found matching to the maximum using the usual Kuhn's algorithm. Thus, we will save on launching a depth-first traversal from those vertices that we have already included using the heuristic into the current matching.

For example, you can simply iterate over all the vertices of the first part, and for each of them, find an arbitrary edge that can be added to the matching, and add it. Even such a simple heuristic can speed up Kuhn's algorithm several times.

Please note that the main loop will have to be slightly modified. Since when calling the function $\textrm{try_kuhn}$ in the main loop, it is assumed that the current vertex is not yet included in the matching, you need to add an appropriate check.

In the implementation, only the code in the $\textrm{main}()$ function will change:

int main() {
    // ... reading the graph ...

    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);
}

Another good heuristic is as follows. At each step, it will search for the vertex of the smallest degree (but not isolated), select any edge from it and add it to the matching, then remove both these vertices with all incident edges from the graph. Such greed works very well on random graphs; in many cases it even builds the maximum matching (although there is a test case against it, on which it will find a matching that is much smaller than the maximum).

Тэмдэглэл¶

Куны алгоритм нь Кун-Мункресийн алгоритм гэж бас нэрлэгддэг Унгарын алгоритм-ын дэд програм юм.
Куны алгоритм $O(nm)$ хугацаанд ажиллана. Үүнийг хэрэгжүүлэхэд ерөнхийдөө энгийн боловч хамгийн их хоёр хэсэгт тааруулалтын бодлогод илүү үр ашигтай алгоритмууд байдаг — жишээ нь $O(\sqrt{n}m)$ хугацаанд ажилладаг Хопкрофт-Карп-Карзановын алгоритм.
Хамгийн бага оройн бүрхэлтийн бодлого нь ерөнхий графуудын хувьд NP-хэцүү юм. Гэвч Кёнигийн теорем хоёр хэсэгт графуудын хувьд хамгийн их тааруулалтын хүчин чадал хамгийн бага оройн бүрхэлтийн хүчин чадалтай тэнцүү болохыг өгдөг. Тиймээс бид хоёр хэсэгт графуудын хувьд хамгийн бага оройн бүрхэлтийн бодлогыг олон гишүүнт хугацаанд бодохын тулд хамгийн их хоёр хэсэгт тааруулалтын алгоритмуудыг ашиглаж болно.