TEORI GRAF

MATCHING GRAPH
 Pengertian Penjodohan (Matching)
Penjodohan (matching) pada graph G adalah sebuah
himpunan sisi-sisi yang saling lepas (independent).

Dua sisi dikatakan saling lepas jika kedua sisi tersebut

tidak mempunyai titik ujung persekutuan. Penjodohan
(matching) dilambangkan dengan M.
 Penjodohan (Matching)
Sebagai contoh, perhatikan graph G pada gambar 1 berikut
Penjodohan (Matching)

Contoh Matching
Bukan Matching
Himpunan Ukuran
M1 = {e1, e3, e6} E1 = {e1, e2, e5}
Matching berukuran 3
M2 = {e2, e5,e8} E2 = {e1, e3, e6, e7}
M3 = {e1, e3} E3 = {e7, e8}
Matching Berukuran 2
M4 = {e4, e6} Dll
Penjodohan (Matching)

Sebuah titik v di G dikatakan tertutup

oleh penjodohan M jika titik v di graph
G merupakan titik akhir (ujung) dari
salah satu sisi di M. Jika titik v di graph
Contoh M-saturated M-unsaturated
G tertutup oleh perjodohan M maka v Matching
dikatakan M-saturated atau
penjodohan M menutup v. Sebaliknya, M3 = {e1, e3} v1 , v2, v3, v4 v5, v6
jika titik v di graph G tidak tertutup oleh
matching M, maka dikatakan titik v M- M4 = {e4, e6} v2, v4, v5, v6 v1, v3
unsaturated atau M tidak menutup v.
Penjodohan (Matching)

Sebuah penjodohan M di graph G dinamakan penjodohan maksimum jika G tidak

mempunyai penjodohan yang lain dengan ukuran lebih besar dari penjodohan M.
Dengan kata lain, jika M’ penjodohan pada G maka |M| > |M’|.

Contoh: M1 = {e1, e3, e6}

|M1| = 3
Karena pada graph G sebelumnya tidak ada penjodohan yang berukuran 4 maka
M1 adalah penjodohan maksimum, begitu juga untuk M2
Penjodohan (Matching)

Sebuah penjodohan M di graph G dikatakan penjodohan sempurna jika M

memuat semua titik G. Dengan kata lain, jika M penjodohan sempurna pada graph
G, maka setiap titik di G adalah M-saturated.
Contoh: Digunakan graph G sebelumnya.
M1 = {e1, e3, e6} adalah sebuah penjodohan sempurna di graph G, begitu juga
M2 = {e2, e5,e8} merupakan penjodohan sempurna di graph G.
(M1 dan M2 adalah pejodohan maksimum yang tertutup atau memuat semua titik,
sehingga merupakan pejodohan sempurna).
Setiap penjodohan sempurna adalah penjodohan maksimum
tetapi setiap penjodohan maksimum belum tentu penjodohan
sempurna.
Contoh :
1. Himpunan M1 = {e2, e4, e6} sebuah penjodohan maksimum, tetapi
M1 bukan penjodohan sempurna pada graph G karena tidak
menutup di v7.
2. Himpunan M2 = {e3, e6, e10} sebuah penjodohan maksimum tetapi
M2 bukan penjodohan sempurna pada graph G karena tidak
menutup di v2.
Misalkan M adalah penjodohan di graph G. Lintasan alternatif-M
adalah lintasan yang sisinya bergantian di E\M dan di M

Lintasan augumentasi-M adalah Sebuah lintasan alternatif-M yang titik

awal dan titik akhirnya tidak tertutup oleh M.
Contoh :
1. M = 𝑒2 , 𝑒4 , 𝑒6
Lintasan 𝑃 = {𝑣7 , 𝑒10 , 𝑣5 , 𝑒4 , 𝑣4 , 𝑒3 , 𝑣3 , 𝑒2 , 𝑣2 , 𝑒1 , 𝑣1 , 𝑒6 , 𝑣6 } adalah
sebuah lintasan alternatif-M.
2. 𝑀1 = 𝑒2 , 𝑒4 pada graph G.
Lintasan 𝑃1 = {𝑣7 , 𝑒7 , 𝑣2 , 𝑒2 , 𝑣3 , 𝑒3 , 𝑣4 , 𝑒4 , 𝑣5 , 𝑒5 , 𝑣6 } adalah sebuah
lintasan augumentasi-M1 pada graph G.
Penjodohan (Matching)
Teorema 1:
Jika M sebuah penjodohan dan P adalah lintasan
augumentasi-M pada graph G, maka ada
penjodohan M’ pada G dengan
Bukti:
Misalkan M adalah sebuah penjodohan di G.
Misalkan 𝑃 = {𝑣1 , 𝑒1 , 𝑣2 , 𝑒2 , 𝑣3 , … , 𝑒2𝑚−1 , 𝑣2𝑚 } sebuah
lintasan argumentasi-M pada G.
Maka 𝐸1 = {𝑒2 , 𝑒4 , 𝑒6 , … , 𝑒2𝑚−2 } ⊆ 𝑀

Sehingga 𝐸1 ∗ = {𝑒1 , 𝑒3 , 𝑒5 , … , 𝑒2𝑚−1 } juga sebuah

penjodohan baru pada G. Jelas bahwa,
𝐸∗ = 𝐸 + 1
Selanjutnya, dibentuk penjodohan baru M’ sedemikian
hingga,

𝑀′ = 𝐸1 ∗ ∪ 𝑀 − 𝐸1
Karena 𝐸1 ∗ ∩ 𝑀 − 𝐸1 = ∅ , maka :
𝑀′ = 𝐸1 ∗ + 𝑀 − 𝐸1
= 𝐸1 ∗ + 𝑀 − 𝐸1
= 𝐸1 + 1 + 𝑀 − 𝐸1 , karena 𝐸1 ⊆ 𝑀
= 𝑀 +1
Dengan demikian Teorema terbukti
Contoh :

𝑀1 = {𝑒2 , 𝑒4 } pada graph 𝐺1

Lintasan augmentasi-𝑀1 = {𝑣7 , 𝑒7 , 𝑣2 , 𝑒2 , 𝑣3 , 𝑒3 , 𝑣4 , 𝑒4 , 𝑣5 , 𝑒5 , 𝑣6 }
𝑀1 ′ = {𝑒7 , 𝑒3 , 𝑒5 }
Sehingga
𝑀1 = 2
𝑀′ = 𝑀1 + 1 = 2 + 1 = 3
Penjodohan (Matching)
Teorema 2:
Sebuah penjodohan M pada graph G adalah
penjodohan maksimum jika dan hanya jika G tidak
memuat lintasan augumentasi-M
Penjodohan (Matching)
Bukti:
Misalkan M adalah penjodohan maksimum pada graph
G. Andaikan terdapat lintasan argumentasi-M pada G.
Menurut teorema 9.1, terdapat penjodohan M’
pada G dengan 𝑀′ = 𝑀1 +1 , kontradiksi
bahwa M penjodohan maksimum pada G.
Penjodohan (Matching)
Misalkan graph G tidak memuat lintasan argumentasi-M, Andaikan M
bukan penjodohan maksimum pada G.
Misalkan M’ penjodohan maksimum pada G, maka 𝑀′ > 𝑀1
maka H memuat lebih banyak sisi M’ dari pada sisi M. Sehingga ada
komponen di H berupa lintasan yang sisi awal dan sisi akhirnya di M’.
Dengan demikian titik awal dan titik akhir lintasan tersebut tidak
tertutup oleh M.
Oleh karena itu lintasan tersebut adalah lintasan argumentasi-M pada
G, kontradiksi. Dengan demikian bukti teorema lengkap.
Contoh :

𝑀1 = {𝑒2 , 𝑒4 } pada graph 𝐺1

Lintasan augmentasi-𝑀1 = {𝑣7 , 𝑒7 , 𝑣2 , 𝑒2 , 𝑣3 , 𝑒3 , 𝑣4 , 𝑒4 , 𝑣5 , 𝑒5 , 𝑣6 }
Sehingga
𝑀1 = 2
(tidak maksimum karena ada 𝑀1 ′ = {𝑒7 , 𝑒3 , 𝑒5 } dengan 𝑀1 ′ = 3
B. Penjodohan dan Penutup pada
Graph Bipartisi
Jika G sebuah graph dan 𝑆 ⊆ 𝑉(𝐺) , maka himpunan
semua titik G yang berhubungan langsung dengan titik-
titik di S, dilambangkan dengan 𝑁𝐺 (𝑆) atau 𝑁(𝑆)
Teorema 3 (Teorema Hall) :
Misalkan G adalah graph bipartisi dengan bipartisi
(X,Y). Graph G memuat sebuah penjodohan yang
menutup semua titik X jika dan hanya jika 𝑁(𝑆) ≥
𝑆 , untuk setiap 𝑆 ⊆ 𝑋
Bukti:

Misalkan graph bipartisi G dengan bipartisi (X,Y)

memuat penjodohan M yang menutup semua titik X dan
misalkan 𝑆 ⊆ 𝑋. Karena titik-titik di S dipasangkan
oleh M ke titik yang berbeda di 𝑆 ⊆ 𝑌 maka
𝑁(𝑆) ≥ 𝑆
Misalkan G adalah graph bipartisi dengan bipartisi
(X,Y) yang memenuhi 𝑁(𝑆) ≥ 𝑆 , ∀ 𝑆 ⊆ 𝑋
Andaikan G tidak memuat penjodohan yang menutup
semua titik X.

- Misal M* adalah penjodohan maksimum di G, karena

pengandaian M* tidak menutup semua titik X, berarti ada
titik di X yang tidak ditutupi oleh M*, misalkan titik u.
- Misalkan Z menyatakan himpunan semua titik yang
terhubung ke u oleh lintasan- lintasan alternatif-M*.
Karena M* penjodohan maksimum maka, menurut
teorema 2, bahwa hanya titik u yang tidak tertutup oleh
M* di titik Z.
Namakan himpunan 𝑆 = 𝑍 ∩ 𝑋 dan 𝑇 = 𝑍 ∩ 𝑌.

Jelas titik-titik di 𝑆\ 𝑢 dipasangkan oleh M* dengan titik

di T.
Oleh karena itu 𝑁(𝑆) ⊇ 𝑇 dan 𝑇 = 𝑆 − 1 ........... (1)
Karena setiap titik di 𝑁(𝑆) ≥ 𝑆 terhubung ke u oleh
lintasan alternatif-M*, diperoleh 𝑁 𝑆 = 𝑇 ............. (2)
Dari (1) dan (2) didapat
𝑁(𝑆) = 𝑆 − 1 < 𝑆
Suatu kontradiksi. Dengan demikian teorema terbukti.
Contoh:

Misalkan: X = {v1 , v2 , v3}

Y = {v4 , v5 , v6} dan S = {v2 , v3} , ∀ 𝑆 ⊆ 𝑋
Sehingga, |S| = 2
Titik yang berhubungan dengan S atau N(S) = {v4 , v5 , v6}
Sehingga |N(S)| = 3
Teorema berikut dikenal dengan sebutan Teorema Perkawinan,
merupakan akibat dari Teorema Hall.
Ilustrasi:
Jika setiap gadis di suatu daerah mengenal tepat k pria,
dan setiap pria juga mengenal tepat k gadis, maka
dapat dilakukan perkawinan sedemikian hingga setiap
gadis kawin dengan seorang pria yang dia kenal dan
setiap pria kawin dengan seorang gadis yang dia kenal.
Secara matematis ditulis seperti teorema berikut.
Teorema 4 (Teorema Perkawinan) :
Jika G adalah graph bipartisi beraturan-k dengan k > 0,
maka G memuat penjodohan sempurna.
Bukti:
Misalkan G adalah graph bipartisi beraturan dengan bipartisi (X,Y).
Karena G adalah beraturan-k, maka:
𝑘 𝑋 = 𝐸(𝐺) = 𝑘 𝑌 , dan karena k > 0, 𝑋 = 𝑌
Misalkan 𝑆 ⊆ 𝑋 dan lambangkan dengan 𝐸1 dan 𝐸2 secara
berturut-turut, adalah himpunan-himpunan dari sisi-sisi yang terkait
dengan titik S dan 𝑁(𝑆). Berdasarkan definisi dari 𝑁 𝑆 , 𝐸1 ⊆ 𝐸2 , ,
oleh karena itu 𝑘 𝑁(𝑆) = 𝐸2 ≥ 𝐸1 = 𝑘 𝑆 Akibatnya ,
𝑁(𝑆) ≥ 𝑆
Sehinnga berdasrkan Teorema 3, G memuat penjodohan M yang
menutup semua titik X. Karena 𝑋 = 𝑌 maka penjodohan M
menutup semua titik Y.
Jadi M adalah penjodohan sempurna pada graph G.
Contoh

Diketahui : k = 3 dengan M = {e1, e3, e5}

Sehingga M memuat semua titik graph bipartisi yaitu titik v1, v2,
v3, v4, v5, v6.
Penutup (Cover) pada graph G adalah himpunan 𝐾 ⊆ 𝑉 𝐺 ∋
setiap sisi G mempunyai paling sedikit satu titik ujung di K.
Sebuah penutup (cover) minimum jika tidak ada penutup K’
pada G sedemikian hingga 𝐾′ < 𝐾
Contoh :

Dari graph di atas diperoleh :

 Cover – k = 𝑣1 , 𝑣2 , 𝑣4 , 𝑣5 , 𝑣3 , 𝑣6 ,

 Cover minimum 𝑣1 , 𝑣3 , 𝑣5 ,

Berdasarkan definisi tersebut, diperoleh lemma berikut

Lemma 1 :
Jika k penutup graph G dan M sebuah pejodohan pada G, maka
k memuat paling sedikit satu titik ujung dari setiap sisi pada M.
Lemma 2 :

Misalkan M sebuah penjodohan dan K sebuah penutup

pada graph G dengan 𝑀 = 𝐾 , maka M penjodohan
maksimum dan K adalah penutup minimum
Bukti:
Andaikan M* penjodohan maksimum dan K’ penutup minimum, maka
𝑀 ≤ 𝑀∗ ≤ 𝐾′ ≤ 𝐾
karena 𝑀 = 𝐾 , maka 𝑀 = 𝑀∗ dan 𝐾 = 𝐾′
Jadi M adalah penjodohan maksimum dan K adalah penutup minimum
Contoh :
 Teorema 5:
Jika G graph bipartisi, maka kardinalitas penjodohan
maksimum di G sama dengan kardinalitas penutup
minimum di G.
Bukti:
Misalkan G adalah graph bipartisi dengan bipartisi (X,Y) dan
misalkan M* adalah penjodohan maksimum pada G.
Misalkan U adalah himpunan titik-titik di X yang tidak tertutup oleh
M* dan Z adalah himpuna semua titik yang terhubung oleh lintasan
alternati-M* ke titikU. Misalkan 𝑆 = 𝑍 ∩ 𝑋 dan 𝑇 = 𝑍 ∩ 𝑌 maka,
seperti bukti Teorema Hall, setiap titik T tertutup oleh M dan 𝑁 𝑆 =
𝑇. Didefinisikan 𝐾 ′ = (𝑋 − 𝑆) ∪ 𝑇
Setiap sisi G harus memunyai paling sedikit satu titik
ujungnya di K’. Sebab jika tidak, terdapat sebuah sisi
dengan salah satu titik ujungnya di S dan titikujung
yang lain di , kontradiksi .
Dengan demikian K’ adalah penutup G dan jelas . K
adalah penutup minimum.
Contoh :
C. Penjodohan (Matching) Sempurna
Syarat cukup dan syarat perlu untuk suatu graf
memiliki suatu penjodohan sempurna diperoleh Tutte
(1947). Bukti yang diberikan di sini berdasarkan lovasz
(1973). Suatu komponen dari suatu graf adalah ganjil
atau genap sesuai dengan banyaknya titik-titik ganjil
atau genap. Dinotasikan o(G) menyatakan banyaknya
komponen ganjil dari G, e(G) menyatakan banyaknya
komponen genap dari G dan v(G) menyatakan
banyaknya titik pada graf G
Teorema 6 (Teorema Tutte)
Grap G mempunyai suatu penjodohan sempurna jika dan
hanya jika 𝑜(𝐺 – 𝑆) ≤ |𝑆| , untuk semua S himpunan bagian
dari V(G)
Contoh :

Graf G – S, dengan S = {𝑣15 , 𝑣16 }

o(G-S) = 2, |S| = 2
Graf G, dengan S = {𝑣15 , 𝑣16 } 𝑜(𝐺 – 𝑆) ≤ |𝑆|
Teorema 7
Jika grap G beraturan-3 dan G tidak memuat sisi
pemutus, maka G mempunyai penjodohan sempurna.

Teorema 8
Suatu grap G beraturan-3 dan G yang memuat
sisi pemutus, belum tentu mempunyai penjodohan
sempurna.
Contoh :

M= {e1, e6,e9,e12,e14 e19, e22 }

M-saturated = {V1, V2,V4,V5,V6,V7,V8,V9,V10}
M-unsaturated = {V3,V16}
Sehingga M bukan penjodohan sempurna
D. Aplikasi Penjodohan pada Graph
Pada bagian ini akan dibahas aplikasi dari perjodohan pada graph, khususnya pada graph bipartisi.
Masalah Penugasan Karyawan

Algoritma Metode Hungarian

Contoh
Misalkan diberi graph bipartisi G seperti tampak pada gambar
berikut. Temukanlah sebuah perjodohan maksimum pada graph G
Kembali ke step 3.
TERIMA KASIH