BAB III MATCHING
Sebelum membahas lebih jauh mengenai optimal assignment problem dan cara penyelesaiannya, pada bab ini akan dibahas mengenai definisi matching dan matching pada graf bipartit, karena penyelesaian optimal assignment problem akan menggunakan penerapan matching pada graf bipartit.
3.1
Definisi Matching Misalkan G=(V,E) adalah graf sederhana dan bukan graf kosong. Maka,
matching M didefinisikan sebagai himpunan bagian yang tidak kosong dari rusuk E(G) sedemikian hingga tidak ada dua rusuk dari
M yang saling ajasen di G.
Selanjutnya simpul-simpul ujung dari matching M disebut matched di bawah M. Untuk lebih jelasnya, perhatikan Gambar 3.1. M ={e1,e6,e7} adalah salah satu contoh matching yang dapat dibuat pada graf G.
Gambar 3.1 21
22
Jika M adalah suatu matching, maka suatu simpul vi dikatakan saturated oleh matching M atau matching M saturates terhadap simpul vi jika ada sebuah rusuk dari matching M menempel pada simpul vi tersebut. Sebaliknya jika tidak ada maka simpul vi disebut unsatured M. Pehatikan Gambar 3.1, v1 dan v2 disebut saturated oleh M, sebaliknya pada Gambar 3.2, v1 disebut unsaturated karena tidak ada matching M yang menempel pada v1.
Gambar 3.2
Matching M disebut matching sempurna jika setiap simpul pada G saturated oleh matching M. Pada Gambar 3.1 semua simpul saturated oleh matching M, maka graf pada Gambar 3.1 merupakan contoh matching sempurna. Sedangkan pada Gambar 3.2 ada satu simpul yaitu v1 yang tidak saturated oleh matching M, maka graf pada Gambar 3.2 bukan contoh matching sempurna.
23
Dari sebuah graf G, bisa saja diperoleh lebih dari satu matching M. Suatu matching M disebut matching maksimum jika untuk setiap matching pada graf G tidak terdapat matching M' dengan
. Sehingga setiap matching sempurna
adalah matching maksimum. Namun sebaliknya, jika M adalah matching maksimum belum tentu M merupakan matching sempurna. Gambar 3.1 merupakan matching sempurna sekaligus matching maksimum dan Gambar 3.2 merupakan contoh matching maksimum tetapi bukan matching sempurna. Misalkan M adalah matching dan P adalah lintasan pada graf G. lintasan P disebut M-alternating jika rusuk-rusuk pada P terbentang dalam M dan berada pada E(G)\M, dengan kata lain rusuknya bergantian antara M dan E(G)\M. Selanjutnya Lintasan P disebut M-augmenting jika lintasan ini M-alternating dan simpul awal serta simpul akhir dari lintasan P merupakan M-unsaturated. Untuk lebih jelasnya perhatikan Gambar 3.3.
24
Gambar 3.3 Pada Gambar 3.3, yang merupakan contoh lintasan M-alternating yaitu v1e1 v4e2v2e3v6e6v5e7v3. Sedangkan v8e9v6e3v2e5v5e7v3e8v7 merupakan contoh lintasan Maugmenting karena simpul awalnya yaitu v8 dan simpul akhirnya yaitu v7 merupakan simpul yang berada pada E(G)\M dan unsaturated M. Misalkan M adalah matching pada graf G, dan terdapat matching lain, sebut saja
dengan
menunjukan perbedaan simetris M dan
diperoleh suatu graf H=G(
. Maka dapat
) yang merupakan graf yang direntang oleh rusuk
dengan menghapus semua rusuk
dan rusuk (G\M)
(G\
). Untuk
lebih jelasnya perhatikan contoh 3.1.
Contoh 3.1: Diberikan graf G yang memuat matching M dan matching Gambar 3.4. Akan dicari H= G(
).
seperti pada
25
Gambar 3.4 Rusuk yang menghubungkan simpul v5 dan simpul v8 merupakan anggota anggota matching M sekaligus anggota matching
(
). Maka, rusuk tersebut
dihapus. Rusuk yang menghubungkan simpul v5 dan simpul v11 serta rusuk yang menghubungkan simpul v6 dan simpul v8 bukan anggota matching M sekaligus bukan anggota matching diperoleh H= G(
((G\M)
(G\
)), oleh karena itu dihapus. Selanjutnya
) seperti Gambar 3.5.
26
Gambar 3.5 H=G(
)
Lemma 3.1: Misalkan M dan (
), dengan
adalah dua matching yang berbeda pada G, H = G
menunjukkan beda simetris dari M dan
. Setiap komponen
dari H pasti berkaitan dengan salah satu dari ketiga bentuk di bawah ini: 1. Simpul terisolasi. 2. Siklus (M, M’)-alternating dengan orde genap. 3. Lintasan (M, M’)-alternating. (Junming Xu, 2003: 232-233)
Bukti:
27
Misalkan V adalah himpunan simpul dan E adalah himpunan rusuk pada graf G dengan M dan
adalah dua matching yang berbeda, maka akan terdapat tiga
kasus: 1. Simpul yang berinsiden dengan rusuk
atau rusuk (G\M)
tetapi tidak berinsiden dengan matching M maupun
(G\
, maka pada graf H
simpul tersebut merupakan simpul terisolasi.
Gambar 3.6 Graf G dengan dua matching yaitu matching M (ditandai dengan garis tebal) dan matching
)
(ditandai dengan garis putus-putus)
28
Gambar 3.7 H=G(
)
2. Andaikan P adalah komponen dari H. Dalam hal ini
. Jika
semua simpul pada P mempunyai derajat dua, maka masing-masing simpulnya berinsiden dengan satu rusuk pada M dan satu rusuk pada
.
Maka dapat disimpulkan bahwa siklus (M, M’)-alternating dengan orde genap. 3. Ada x∈V(P) sedemikian hingga degH(x) = 1. Maka terdapat paling sedikit satu simpul misalkan saja simpul y, dengan derajat satu selain simpul x. Ketika ∆(P) ≤ 2, P adalah lintasan yang menghubungkan x dan y. Simpulsimpul internalnya (jika ada) merupakan simpul berderajat dua, maka P adalah Lintasan (M, M’)-alternating.
29
Contoh 3.2: 1. Perhatikan Gambar 3.6 dan Gambar 3.7. Simpul v2,v4,v9 pada graf G menjadi simpul terisolasi pada graf H. 2. Pada Gambar 3.7, v1v7v3v10 adalah lintasan (M, M’)-alternating. 3. Pada Gambar 3.7, v5v8v6v11 v5 adalah siklus (M, M’)-alternating dengan orde genap.
Teorema 3.1 (Teorema Berge): Matching M pada graf G adalah matching maksimum jika dan hanya jika G tidak mengandung lintasan M-augmenting (Chartrand and Lesniak, 1996: 259).
Bukti:
(⇒)
Akan dibuktikan dengan kontradiksi. Misalkan M adalah matching maksimum pada graf G dan terdapat lintasan M-augmenting P. Dalam hal ini, P haruslah memiliki jumlah rusuk yang ganjil, karena agar suatu lintasan P merupakan lintasan M-augmenting, setiap satu rusuk yang merupakan matching M harus berajasen dengan dua rusuk lainnya yang bukan matching (E(G)\M). Untuk lebih jelasnya, misalkan lintasan M-augmenting P=v0v1v2… vk1vk.
Perhatikan bahwa k jumlah rusuk berjumlah ganjil, karena v0 dan vk
30
unsarated M, artinya v0v1 dan vk-1vk harus bukan anggota matching M. ⊆ (G) dengan
Selanjutnya, definisikan himpunan rusuk
{v1v2, v3v4,…, vk-2vk-1}) ∪ { v0v1, v2v3,…, vk-1vk}, maka matching pada graf G dengan nilai
= (M-
merupakan
. Hal ini kontradiksi
dengan M adalah matching maksimum. Oleh karena itu, jika M adalah matching maksimum pada graf G, maka G tidak mungkin memiliki lintasan M-augmenting.
(⇐)
Akan dibuktikan dengan kontradiksi. Misalkan M bukan matching maksimum dan
adalah matching maksimum di G. Akibatnya
. Definisikan, H=G( beda simetri di M dan
) dengan
menunjukkan
.
Dari pembuktian lemma 3.1, diperoleh setiap simpul di H berderajat 1 atau 2, karena setiap simpul di H berinsiden dengan paling banyak satu rusuk di M dan satu rusuk di
. Dengan demikian, komponen H adalah
lintasan yang rusuknya bergantian di M dan banyak rusuknya adalah genap. Karena maksimum,
dari
penjelasan
atau siklus dengan
dimisalkan sebagai matching
sebelumnya
Akibatnya, H mempunyai lebih banyak rusuk
diperoleh
.
dibandingkan rusuk M.
Sehingga lintasan P di H yang rusuk awal dan rusuk akhirnya adalah anggota dari
. Dengan kata lain simpul awal serta simpul akhir dari
31
lintasan P merupakan M-unsaturated. Maka lintasan P adalah lintasan M-augmenting. Kita peroleh pernyataan, jika M bukan matching maksimum di G maka G mengandung lintasan M-augmenting. Pernyataan ini ekivalen dengan jika G tidak mengandung lintasan
M-augmenting, maka M adalah
matching maksimum di G.
Seperti yang telah dijelaskan sebelumnya, algoritma Kuhn-Munkres dapat direpresentasikan dengan graf bipartit. Representasi algoritma Kuhn-Munkres pada graf bipartit melibatkan penerapan matching, maka akan dibahas mengenai matching pada graf bipartit.
3.2
Matching Pada Graf Bipartit Sebelum membahas lebih jauh mengenai matching pada graf bipartit, akan
dijelaskan dulu mengenai himpunan persekitaran. Misalkan terdapat graf sebarang G=(V,E), dengan V adalah himpunan simpul pada G dan S merupakan subset dari V(G), maka himpunan persekitaran dari S (neighbour set of S) adalah himpunan semua simpul yang berajasen dengan simpul-simpul di S. Himpunan persekitaran biasanya dinotasikan dengan NG(S).
Teorema 3.2 (Teorema Hall):
32
Misalkan G adalah graf bipartit dengan bipartisi {X,Y}. Maka G mengandung sebuah matching yang saturates untuk setiap simpul di X untuk setiap
jika dan hanya jika
(Junming Xu, 2003: 212).
Bukti:
(⇒)
Misalkan G mengandung matching M yang saturates pada tiap simpul di X dan S adalah subset dari X. Karena tiap simpul pada S matched di bawah M dengan simpul berbeda di
, maka diperoleh
.
(⇐)
Akan dibuktikan dengan kontradiksi. Misalkan G adalah graf bipartit yang memenuhi
untuk setiap
, tetapi G tidak
mempunyai matching yang saturates pada setiap simpul dari X. Misalkan M* adalah matching maksimum pada G, maka akan terdapat simpul u di X yang merupakan unsaturated M*. Selanjutnya definisikan himpunan simpul di G dengan Z={v∈V(G): terdapat lintasan M*-alternating dari u ke v}, dengan kata lain Z adalah himpunan semua simpul yang terhubung ke u oleh lintasan M*alternating. Karena M* adalah matching maksimum dan u unsaturated M*, dari teorema 3.1 (teorema Berge) diperoleh u adalah satu-satunya simpul yang unsaturated M* pada Z.
33
Misalkan S = Z ∩ X dan T = Z ∩ Y. Maka diperoleh simpul pada S\{u} matched di bawah M* dengan simpul pada T. Sehingga dan T subset dari
.
Lebih tepat lagi NG(S)=T karena setiap simpul di NG(S) terhubung ke u oleh suatu lintasan M*-alternating. Tetapi
hal ini kontradiksi dengan
jadi diperoleh pernyataan
dan NG(S)=T,
Maka haruslah G memiliki matching yang
saturates terhadap setiap simpul di X.
Akibat 1 (Teorema Marriage, Forbenius): Graf bipartit G dengan bipartisi {X,Y}, memiliki matching sempurna jika dan hanya jika
dan
untuk setiap
atau Y (Junming Xu,
2003: 213).
Akibat 2 (König): Jika G adalah graf bipartit k-regular dengan k > 0, maka G memiliki sebuah matching sempurna (Junming Xu, 2003: 213). Bukti: Misalkan G adalah graf bipartit k-regular dengan bipartisi {X,Y}. Karena G adalah k-regular, maka
. Karena k>0, maka
.
34
Misalkan S subset dari X, dengan E1 adalah himpunan rusuk yang berinsiden dengan simpul di S dan E2 adalah himpunan simpul yang berinsiden dengan simpul di NG(S). Maka berdasarkan definisi NG(S) diperoleh E1 subset dari E2 oleh karena itu diperoleh menunjukan
. Selanjutnya hal ini , maka berdasarkan teorema Teorema 3.2 (teorema
Hall) diperoleh pernyataan bahwa G memiliki matching M yang saturates terhadap setiap simpul di X, dan karena sempurna.
, maka M adalah matching
