Misalkan G adalah graf bipartit dengan partisi (X,Y). Dalam algoritma, kita dapat membentuk sebuah matching M yang menyatukan tiap simpul dalam himpunan X, atau sebaliknya menentukan sebuah matching tidak ada.
Algoritma bermula dari matching sembarang M. Jika M saturates tiap simpul di X, maka M adalah matching yang diharapkan. Jika tidak, kita pilih sebuah M-unsaturated simpul u di X dan secara sistematik mencari lintasan M-augmenting yang bermula di u. Jika lintasan tersebut ada, maka lintasan ini akan digunakan untuk membangun matching yang lebih besar dari M.
Sebaliknya, himpunan Z dari simpul-simpul akhir dari semua lintasan M-alternating bermula di u ditemukan, dan dalam bukti dari teorema Hall, himpunan S = Z ∩ X memenuhi │N(S)│<│S│ sehingga matching yang menyatukan semua simpul di X ada.
Pencarian dari lintasan M-augmenting bermula dari u dengan membentuk pohon M-alternating H yang berakar di u. Yaitu, H adalah pohon pada graf G dengan kriteria sebagai berikut :
1. u ϵ V(H) dan
2. Untuk setiap v ϵ V(H), (u,v)-lintasan unik pada H adalah lintasan M-alternating.
Misalkan S = V(H) ∩ X dan T=V(H) ∩ Y. Pohon M-alternating H tumbuh pada dua kondisi yaitu :
(i) Semua simpul S – {u}adalah M-saturated dan matched dalam M ke simpul pada T, atau
(ii) T mengandung sebuah simpul M-unsaturated simpul y berbeda dari u.
Pada saat kasus (ii) dipenuhi, kita akan memiliki simpul M-augmenting (u,y), yang digunakan untuk memperbesar matching M. Pada kasus (i), kita memiliki T ⊆ N(S). Jika T = N(S), maka │N(S)│=│S│ – 1 < │S│, dan G tidak mempunyai T ≠ N(S), maka terdapat simpul yϵN(S)-T yang bertetangga kesebuah simpul x di S. Jika y adalah M-unsaturated, maka sisi xy akan ditambahkan ke pohon H, menghasilkan kasus (ii). Sebaliknya, jika y M-saturated, maka terdapat sisi yzϵM. Kita sekarang dapat menambahkan xy dan yz ke pohon H, menghasilkan kasus (ii).
Tidak ada komentar:
Posting Komentar