A Matching in a graph G = (V, E) is a subset of edges M of a graph G = (V, E) such that no two edges share a common vertex.
Maximum Cardinality Matching (MCM) problem is a Graph Matching problem where we seek a matching M that contains the largest possible number of edges. A desirable but rarely possible result is Perfect Matching where all |V| vertices are matched (assuming |V| is even), i.e., the cardinality of M is |V|/2.
A Bipartite Graph is a graph whose vertices can be partitioned into two disjoint sets U and V such that every edge can only connect a vertex in U to a vertex in V.
Maximum Cardinality Bipartite Matching (MCBM) problem is the MCM problem in a Bipartite Graph, which is a lot easier than MCM problem in a General Graph.
Graph Matching problems (and its variants) arise in various applications, e.g.,
In some applications, the weights of edges are not uniform (1 unit) but varies, and we may then want to take MCBM or MCM with minimum (or even maximum) total weight.
This visualization support both unweighted and weighted MCBM, but only works for unweighted MCM.
We do not have immediate plan to add support for weighted MCM and only rely on Dynamic Programming with Bitmask for small graphs solution.
To switch between the unweighted MCBM (default, as it is much more popular), weighted MCBM, and unweighted MCM mode, click the respective header.
Here is an example of MCM mode. In MCM mode, one can draw a General, not necessarily Bipartite graphs. However, the graphs are unweighted (all edges have uniform weight 1).
The available algorithms (and example graphs) are different in each mode.
You can view the visualisation here!
For Bipartite Graph visualization, we will mostly layout the vertices of the graph so that the two disjoint sets (U and V) are clearly visible as Left (U) and Right (V) sets. When you draw your input bipartite graph, you can choose to re-layout your bipartite graph into this easier-to-visualize form. However, you do not have to visualize Bipartite Graph in this form, e.g., you can click to load an example grid graph and notice that vertices {0,1,2,3} can form set U and vertices {4,5,6,7,8} can form set V. There is no odd-length cycle in this grid graph.
For General Graph, we do not (and usually cannot) re-layout the vertices into this Left Set and Right Set form.
Initially, edges have grey color. Matched edges will have black color. Free/Matched edges along an augmenting path will have Orange/Light Blue colors, respectively.
There are four different sources for specifying an input graph:
Ada beberapa algoritma-algoritma Pencocokan Bipartit dengan Kardinalitas Maksimum (Max Cardinality Bipartite Matching, MCBM) di visualisasi ini, ditambah satu lagi di visualisasi Aliran Maks (Max Flow):
Catatan 1: Meskipun memungkinkan, kita tidak akan menggunakan Algoritma Pencocokan O(V3) oleh Edmonds jika masukannya dijamin adalah sebuah Graf Bipartit (karena algoritma tersebut terlalu pelan).
Catatan 2: Meskipun memungkinkan, kita juga tidak akan menggunakan Algoritma O(V3) oleh Kuhn-Munkres jika masukannya dijamin adalah sebuah Graf Bipartit Tak Berbobot (karena algoritma tersebut terlalu pelan).
The MCBM problem can be modeled (or reduced into) as a Max Flow problem in polynomial time.
Go to Max Flow visualization page and see the flow graph modeling of MCBM problem (select Modeling → Bipartite Matching → all 1). Basically, create a super source vertex s that connects to all vertices in the left set and also create a super sink vertex t where all vertices in the right set connect to t. Keep all edges in the flow graph directed from source to sink and with unit weight 1.
If we use one of the earliest Max Flow algorithm, i.e., a simple Ford-Fulkerson algorithm, the time complexity will be tighter than O(mf × E) as all edge weights in the flow graph are unit weight so mf ≤ V, i.e., so O(V × E) overall.
If we use one of the fastest Max Flow algorithm, i.e., Dinic's algorithm on this flow graph, we can find Max Flow = MCBM in O(√(V)E) time — the analysis is omitted for now. This allows us to solve MCBM problem with V ∈ [1000..1500] in a typical 1s allowed runtime in many programming competitions.
Discussion: Must the edges in the flow graph be directed or can they be undirected? Explain.
Sebenarnya, kita bisa berhenti di sini, yaitu, ketika diberikan masalah MCBM (atau yang terkait), kita bisa langsung menguranginya menjadi masalah Max Flow dan menggunakan algoritma Max Flow (yang tercepat).
Namun, ada algoritma Pencocokan Graf yang jauh lebih sederhana yang akan kita lihat dalam beberapa slide berikutnya. Algoritma ini didasarkan pada sebuah teorema penting dan dapat diimplementasikan sebagai variasi mudah dari algoritma DFS standar.
Jalur Augmentasi adalah jalur yang dimulai dari simpul bebas (tidak dipasangkan) u dalam graf G (perhatikan bahwa G tidak harus graf bipartit, meskipun jalur augmentasi, jika ada, jauh lebih mudah ditemukan dalam graf bipartit), bergantian melalui sisi yang tidak dipasangkan (atau bebas/'f'), dipasangkan (atau 'm'), ..., sisi tidak dipasangkan ('f') dalam G, hingga berakhir di simpul bebas lain v. Pola dari jalur augmentasi apa pun adalah fmf...fmf dan memiliki panjang ganjil.
Jika kita membalik status sisi sepanjang jalur augmentasi tersebut, yaitu dari fmf...fmf menjadi mfm...mfm, kita akan menambah jumlah sisi dalam set pencocokan M sebanyak 1 unit dan menghilangkan jalur augmentasi ini.
Pada tahun 1957, Claude Berge mengusulkan theorem berikut:
Pencocokan M dalam graf G adalah maksimum jika dan hanya jika tidak ada lagi jalur augmentasi dalam G.
Diskusi: Dalam kelas, buktikan kebenaran teorema Berge!
Dalam praktiknya, kita bisa menggunakannya apa adanya.
Pembuktian mengklaim jika dan hanya jika, sehingga ada dua bagian:
arah maju dan arah mundur.
Pembuktian arah maju lebih mudah:
M∈G adalah maksimum → tidak ada jalur augmentasi dalam G terhadap M.
Pembuktian arah mundur sedikit lebih sulit:
M∈G adalah maksimum ← tidak ada jalur augmentasi dalam G terhadap M.
Pembuktian dengan kontradiksi:
Andaikan M∈G adalah pencocokan maksimum tetapi G masih memiliki jalur augmentasi terkait dengan pencocokan M.
Sekarang, jalur augmentasi ini: fmf...fmf (yang memiliki panjang ganjil) dapat dibalik menjadi pencocokan lain M' yang menghapus sisi yang sebelumnya dicocokkan (yang 'm') dan mengambil sisi lain yang bebas (yang 'f') sepanjang jalur augmentasi. Dengan demikian, |M'| = |M|+1.
Ini bertentangan dengan pernyataan bahwa M adalah pencocokan maksimum.
Jadi, jika M∈G adalah maksimum → tidak ada lagi jalur augmentasi terkait dengan pencocokan M di G.
Bagian ini biasanya sulit dipahami dalam satu kali baca. Harap baca dengan cermat.
Kami menggunakan pembuktian dengan kontradiksi lagi:
Misalkan tidak ada jalur augmentasi di G terkait dengan M tetapi M∈G tidak maksimum,
yaitu, ada M' yang lebih besar dari M.
Pertama, kita ambil selisih simetris dari M' dan M untuk menghasilkan graf baru G' yang memiliki simpul yang sama dengan G, tetapi hanya memiliki sisi yang terlibat dalam M' atau M (tetapi tidak keduanya).
Mari kita amati graf baru G' ini. Perhatikan bahwa G' hanya akan terdiri dari simpul-simpul dengan degree 0 (simpul terisolasi, kita abaikan), degree 1 (titik akhir dari jalur augmentasi), atau degree 2 (di tengah jalur augmentasi, simpul yang menghubungkan sisi di M dan sisi lain di M'). Graf dengan degree tidak lebih dari 2 hanya dapat terdiri dari jalur atau siklus.
Pada jalur dan siklus, kita memiliki dua sub-kemungkinan: panjang ganjil atau genap.
Jika G' mengandung jalur dengan panjang genap (seperti yang ditunjukkan saat ini), itu tidak membantu pembuktian ini (karena ini menyiratkan |M| = |M'|, yaitu M' tidak lebih besar dari M).
Kita dapat memiliki siklus dengan panjang genap (seperti yang ditunjukkan saat ini di latar belakang) tetapi ini tidak membantu dengan pembuktian ini (karena ini menyiratkan |M| = |M'|, yaitu, M' tidak lebih besar dari M).
Kita tidak akan memiliki siklus dengan panjang ganjil karena sisi-sisi dalam G' hanya berasal dari M dan M' (gambar sebuah segitiga yang merupakan siklus dengan panjang ganjil terkecil dan yakinkan diri Anda bahwa setelah menetapkan satu sisi ke M dan sisi lainnya ke M', kita tidak dapat menetapkan sisi ketiga dari segitiga ke M atau M' — situasi yang sama berlaku untuk siklus panjang ganjil yang lebih panjang lainnya).
Terakhir, kita dapat memiliki jalur dengan panjang ganjil di mana jalur dimulai dan diakhiri dengan sisi dari 'M' yang lebih besar dan sisi dalam M sedikit berada di dalam, pola fmf...fmf. Sekarang apa ini? Ini adalah jalur augmentasi terhadap M. Kita sebelumnya mengklaim bahwa tidak ada jalur augmentasi dalam G terhadap M, jadi sekali lagi kita tiba pada kontradiksi.
Kesimpulan keseluruhan: Teorema Berge benar dan merupakan bagian integral dari algoritma Augmenting Path (Plus) dan juga nanti: algoritma Kuhn-Munkres (Hungarian) dan Edmonds' Matching.
Ingatlah kembali bahwa Teorema Berge menyatakan:
Sebuah pencocokan dalam graf adalah maksimum jika dan hanya jika tidak ada lagi jalur augmentasi di .
Algoritma Jalur Augmentasi (pada Graf Bipartit) adalah implementasi sederhana O(V*(V+E)) = O(V2 + VE) = O(VE) dari teorema tersebut (modifikasi dari DFS): Temukan dan kemudian hilangkan jalur augmentasi dalam Graf Bipartit G.
Klik untuk memvisualisasikan algoritma ini pada kasus uji khusus yang disebut X̄ (X-bar).
Pada dasarnya, Algoritma Jalur Augmentasi ini memindai semua vertex pada set kiri (yang awalnya adalah vertex bebas) satu per satu. Misalkan di set kiri adalah vertex bebas, algoritma ini akan secara rekursif (melalui modifikasi DFS) pergi ke vertex di set kanan:
vi match, vis; // variabel global
int Aug(int L) { // perhatikan kemiripan dengan algoritma DFS
if (vis[L]) return 0; // L telah dikunjung, return 0
vis[L] = 1;
for (auto& R : AL[L])
if ((match[R] == -1) || Aug(match[R])) { // modifikasi utama
match[R] = L; // status dibalik
return 1; // ditemukan 1 pencocokan
}
return 0; // Jalur Augmentasi tidak ditemukan
}
// pada int main(), buat graf bipartitnya
// gunakan sisi-sisi terarah dari himpunan kiri (dengan ukuran VLeft) ke himpunan kanan
int MCBM = 0;
match.assign(V, -1);
for (int L = 0; L < VLeft; ++L) { // coba semua simpul kiri
vis.assign(VLeft, 0);
MCBM += Aug(L); // temukan jalur augmentasi mulai dari L
}
printf("Found %d matchings\\n", MCBM);
Anda bisa melihat implementasi penuh di situs pendamping buku Competitive Programming: mcbm.cpp | py | java | ml.
Jika kita diberikan graf bipartit Komplet KN/2,N/2, dengan V = N/2+N/2 = N dan E = N/2×N/2 = N2/4 ≈ N2, maka Algoritma Jalur Augmentasi yang dibahas sebelumnya akan berjalan dalam O(VE) = O(N×N2) = O(N3).
Ini hanya OK untuk V ∈ [400..500] dalam waktu 1 detik yang diizinkan dalam banyak kompetisi pemrograman.
Cobalah Algoritma Jalur Augmentasi Standar pada , yaitu adalah sebuah graf bipartit yang hampir komplet K5,5
Algoritmanya terasa buruk, terutama untuk iterasi-iterasi belakang...
Jadi, apakah kita harus menghindar menggunakan algoritma Jalur Augmentasi ini?
Ide kunci dari Algoritma Hopcroft-Karp (HK) (ditemukan pada tahun 1973) identik dengan algoritma Max Flow Dinic, yaitu memprioritaskan jalur augmentasi terpendek (dalam hal jumlah sisi yang digunakan) terlebih dahulu. Itu saja, jalur augmentasi dengan 1 sisi diproses terlebih dahulu sebelum jalur augmentasi yang lebih panjang dengan 3 sisi, 5 sisi, 7 sisi, dll (panjangnya selalu bertambah 2 karena sifat jalur augmentasi dalam Graf Bipartit).
Algoritma Hopcroft-Karp memiliki kompleksitas waktu O(√(V)E) — analisis diabaikan untuk sekarang. Ini memungkinkan kita untuk menyelesaikan masalah MCBM dengan V ∈ [1000..1500] dalam waktu 1 detik yang diizinkan dalam banyak kompetisi pemrograman — rentang yang mirip dengan menjalankan algoritma Dinic pada graf aliran pencocokan bipartit.
Cobalah Algoritma HK pada yang sama sebelumnya. Anda akan melihat bahwa Algoritma HK dapat menemukan MCBM dalam waktu yang jauh lebih cepat daripada Algoritma Jalur Augmentasi standar O(VE) sebelumnya.
Karena algoritma Hopcroft-Karp pada dasarnya juga merupakan algoritma Dinic, kita anggap keduanya sebagai 'hampir setara'.
Namun, kita sebenarnya bisa membuat Algoritma Jalur Augmentasi yang telah dibahas sebelumnya untuk menghindari perilaku kasus terburuk O(VE) dengan melakukan preprosessing acak O(V+E) (untuk menghindari kasus uji yang merugikan) sebelum menjalankan algoritma sebenarnya.
Langkah praproses tambahan O(V+E) ini sederhana: Untuk setiap vertex pada set kiri, cocokkan dengan vertex tetangga yang tidak dicocokkan secara acak pada set kanan. Dengan cara ini, kita menghilangkan banyak Jalur Augmentasi yang sepele (satu-sisi) yang terdiri dari vertex bebas u, sisi yang tidak dicocokkan (u, v), dan vertex bebas v.
Coba Algoritma Jalur Augmentasi Plus pada yang sama sebelumnya. Perhatikan bahwa langkah praproses ini sudah menghilangkan banyak jalur augmentasi sepele 1-sisi, sehingga Algoritma Jalur Augmentasi yang sebenarnya hanya perlu melakukan sedikit pekerjaan tambahan.
Seringkali, pada Graf Bipartit yang dihasilkan secara acak, langkah pre-processing greedy yang diacak telah mengambil sebagian besar pencocokan.
Namun, kita dapat membuat kasus uji seperti: Graf Contoh, Kasus Korner, Pembunuh AP Greedy Acak untuk membuat randomisasi menjadi se-tidak-efektif mungkin. Untuk setiap kelompok 4 simpul, ada 2 pencocokan. Pemrosesan greedy acak memiliki kemungkinan 50% membuat kesalahan per kelompok (tetapi karena setiap kelompok hanya memiliki Jalur Augmentasi yang pendek, perbaikannya tidak 'panjang'). Cobalah kasus ini untuk melihat sendiri.
Waktu kompleksitas kasus terburuk tidak lagi O(VE) tetapi sekarang O(kE) dengan k merupakan bilangan bulat kecil, jauh lebih kecil dari V, k bisa sekecil 0 dan paling banyak V/2 (setiap pencocokan maksimal, seperti pada kasus ini, memiliki ukuran setidaknya setengah dari pencocokan maksimum). Dalam eksperimen kami, kami memperkirakan k adalah "sekitar √(V)" juga. Versi Algoritma Jalur Augmentasi Plus ini juga memungkinkan kami untuk menyelesaikan masalah MCBM dengan V ∈ [1000..1500] dalam waktu yang diizinkan 1 detik di banyak kompetisi pemrograman.
Jadi, ketika menghadapi masalah MCBM (Maximum Cardinality Bipartite Matching), jalur mana yang harus kita ambil?
Diskusi: Diskusikan kedua rute tersebut!
NEW FOR 2025. We have just added Min-Cost-Max-Flow (mcmf) in maxflow visualization and Hungarian/Kuhn-Munkres visualization in this VisuAlgo page.
However, these features are still experimental.
Do report to Prof Halim if you encounter technical issue(s).
Ketika pencocokan graf diterapkan pada graf umum (masalah MCM), menemukan Jalur Augmentasi menjadi jauh lebih sulit. Faktanya, sebelum Jack Edmonds menerbitkan paper terkenalnya yang berjudul "Paths, Trees, and Flowers" pada tahun 1965, masalah MCM ini dianggap sebagai masalah optimisasi (NP-)hard.
Ada dua algoritma Pencocokan Kardinalitas Maksimum (MCM) dalam visualisasi ini:
Dalam Graf Umum (seperti graf yang ditunjukkan di latar belakang yang memiliki |MCM| = 4), kita mungkin memiliki siklus panjang ganjil. Augmenting Path tidak terdefinisi dengan baik dalam graf semacam itu, sehingga kita tidak dapat dengan mudah mengimplementasikan teorema Claude Berge seperti yang kita lakukan dengan Graf Bipartit.
Jack Edmonds menyebut jalur yang dimulai dari simpul bebas u, bergantian antara sisi bebas, dipasangkan, ..., sisi bebas, dan kembali ke simpul bebas yang sama u sebagai Blossom. Situasi ini hanya mungkin terjadi jika kita memiliki siklus panjang ganjil, yaitu, dalam Graf tak-Bipartit. Sebagai contoh, anggap sisi 1-2 telah dipasangkan dalam graf yang ditunjukkan di latar belakang, maka jalur 3-1=2-3 adalah blossom.
Edmonds kemudian mengusulkan Algoritma Blossom shrinking/contraction and expansion untuk menyelesaikan masalah ini. Untuk detail tentang cara kerja algoritma ini, baca CP4 Bagian 9.28 karena visualisasi algoritma pencocokan Edmonds saat ini di VisuAlgo masih 'agak terlalu sulit untuk dipahami' oleh pemula, coba . Dalam kelas langsung di NUS, langkah-langkah ini akan dijelaskan secara verbal.
Algoritma ini dapat diimplementasikan dalam O(V^3).
Algoritma Pencocokan Edmonds Plus O(V^3)
Sama seperti Algoritma Jalur Augmentasi Plus untuk masalah MCBM, kita juga dapat melakukan langkah preprocessing acak untuk menghilangkan sebanyak mungkin 'pencocokan sepele' sebelumnya. Ini mengurangi jumlah pekerjaan Algoritma Pencocokan Edmonds, sehingga menghasilkan kompleksitas waktu yang lebih cepat — analisis akan datang.
We have not added the visualization(s) for weighted variant of MCM problem. They are for future work.
The Hungarian (Kuhn-Munkres) algorithm visualization for weighted MCBM is very new and requires users testing, thus do report if you encounter technical issue(s).
Untuk memperkuat pemahaman Anda tentang masalah Graf Matching ini, variasinya, dan berbagai solusi yang mungkin, silakan coba menyelesaikan sebanyak mungkin dari masalah kompetisi pemrograman yang tercantum di bawah ini:
Untuk menyelesaikan soal-soal lomba programming tersebut, anda dapat menggunakan dan/atau memodifikasi implementasi kami untuk Algoritma Jalur Augmentasi (dengan Preprocessing Greedy Acak): mcbm.cpp | py | java | ml