Sebuah Pencocokan (Matching) dalam sebuah graf G = (V, E) adalah subset M dari E sisi-sisi dari G sehingga tidak ada dua dari antaranya bertemu dalam simpul yang sama.
Masalah Pencocokan dengan Kardinalitas Maksimum (Maximum Cardinality Matching, MCM) adalah masalah Pencocokan Graf dimana kita mencari sebuah pencocokan M yang berisikan sisi-sisi paling banyak. Sebuah varian yang mungkin adalam Pencocokan Sempurna (Perfect Matching) dimana semua |V| simpul-simpul berhasil dicocokkan (dengan asumsi |V| genap), yaitu kardinalitasnya dari M adalah |V|/2.
Sebuah Graf Bipartit adalah sebuah graf dimana simpul-simpulnya bisa dipartisi menjadi dua himpunan lepas U dan V sehingga setiap sisi dapat hanya menghubungkan sebuah simpul dalam U ke sebuah simpul dalam V.
Masalah Pencocokan Bipartit dengan Kardinalitas Maksimum (Maximum Cardinality Bipartite Matching, MCBM) adalah masalah MCM dalam Graf Bipartit, yang adalah jauh lebih mudah daripada masalah MCM dalam Graf Umum.
Masalah Pencocokan Graf (dan variasinya) muncul di beberapa aplikasi, seperti,
Dalam beberapa aplikasi, bobot sisi tidak seragam (1 unit) tetapi bervariasi, dan kita mungkin ingin mencari MCBM atau MCM dengan total bobot minimum (atau bahkan maksimum).
Visualisasi ini saat ini terbatas pada graf-graf tidak berbobot saja. Sehingga, kita saat ini tidak mendukung varian-varian masalah Pencocokan Graf variants yang berhubungan dengan graf-graf berbobot...
Rencananya adalah untuk menambahkan algoritma Hungarian (Kuhn-Munkres) untuk masalah MCBM berbobot pada bulan April 2024, tetaplah ikuti perkembangannya...
Untuk beralih antara mode MCBM tanpa bobot (default, karena ini jauh lebih populer) dan mode MCM berbobot, klik header yang sesuai.
Berikut adalah contoh mode MCM. Dalam mode MCM, Anda dapat menggambar Graf Umum, tidak harus Bipartit. Namun, graf-graf tersebut tidak berbobot (semua sisi memiliki bobot seragam 1).
Algoritma yang tersedia berbeda dalam kedua mode tersebut.
Anda dapat melihat visualisasinya di sini!
Pada awalnya, sisi-sisi memiliki warna abu-abu. Sisi-sisi yang sudah dicocokkan akan mendapat warna hitam. Sisi-sisi Bebas/Tercocokkan sepanjang jalur augmentasi akan memiliki warna Oranye/Biru Muda.
Ada tiga sumber berbeda untuk menspesifikasikan graf masukan:
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).
Masalah MCBM dapat dimodelkan (atau direduksikan) mejadi masalah Max Flow dalam waktu olinomial.
Bukalah laman visualisasi Max Flow dan lihatlah model graf flow dari masalah MCBM (pilih Modeling → Pencocokan Bipartit → all 1). Pada dasarnya, buatlah simpul sumber super s yang terhubung ke semua simpul di set kiri dan juga buat simpul tenggelam super t di mana semua simpul di set kanan terhubung ke t. Pertahankan semua sisi dalam graf aliran berarah dari sumber ke tenggelam dan dengan bobot unit 1.
Jika kita menggunakan salah satu algoritma Max Flow awal, yaitu algoritma Ford-Fulkerson sederhana, kompleksitas waktunya akan lebih ketat daripada O(mf × E) karena semua bobot sisi dalam graf aliran adalah bobot unit, sehingga mf ≤ V, yaitu, O(V × E) secara keseluruhan.
Jika kita menggunakan salah satu algoritma Max Flow tercepat, yaitu algoritma Dinic pada graf aliran ini, kita dapat menemukan Max Flow = MCBM dalam waktu O(√(V)E) — analisisnya akan dibahas nanti. Ini memungkinkan kita menyelesaikan masalah MCBM dengan V ∈ [1000..1500] dalam waktu yang diizinkan 1 detik dalam banyak kompetisi pemrograman.
Diskusi: Sisi-sisi dalam graf aliran harus berarah. Mengapa?
Kemudian buktikan bahwa reduksi ini benar.
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.
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!
Sayangnya, belum ada visualisasi algoritma MCBM berbobot (misalnya, Min-Cost-Max-Flow (mcmf) atau Hungarian/Kuhn-Munkres) di VisuAlgo. Namun, rencananya adalah untuk memiliki visualisasi ini pada akhirnya.
Untuk bagian ini, silakan merujuk ke CP4 Buku 2 Bab 9.25 dan 9.27.
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.
Kami belum menambahkan visualisasi-visualisasi untuk varian berbobot dari masalah MCBM dan MCM (untuk pekerjaan dimasa mendatang). Dari keduanya, kemungkinan besar MCBM berbobot akan ditambahkan dahulu daripada MCM berbobot.
Salah satu solusi dari masalah MCBM berbobot adalah algoritma Hungarian. Algoritma ini mempunyai nama lain: algoritma Kuhn-Munkres. Algoritma ini didasarkan dari Teorema Berge, tetapi penggunaannya sedikit berbeda.
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