Dalam teori graf, terdapat salah satu bahasan yang banyak mengulas mengenai penugasan, yaitu matching. Matching pada skripsi ini digunakan untuk penugasan pewarnaan sisi sehingga setiap sisi yang terkait ke simpul yang sama diwarnai dengan warna yang berbeda, yang menjadi masalah adalah berapa jumlah minimum warna yang diperlukan untuk mewarnai sisi – sisi tersebut agar tidak ada dua sisi yang saling adjacent mempunyai warna yang sama.
Pada kasus ketika G adalah graf bipartit, maka ᵡ’= ∆. Dimana ᵡ’ adalah jumlah minimum warna yang diperlukan untuk mewarnai sisi di G dan ∆ adalah derajat maksimum semua simpul di G.
Berdasarkan Penjelasan diatas, penulis mencoba mengkaji lebih dalam dengan menghubungkan secara langsung antara matching dan pewarnaan sisi untuk pembuktian teorema (Konig’s, 1916) jika G adalah graf bipartit, maka ᵡ’=∆. Oleh karena itu penulis memilih judul “Matching Pada Dekomposisi Graf Bipartit (Untuk alternatif pembuktian teorema (Konig’s, 1916) jika G adalah graf bipartit, maka ᵡ’= ∆)”.
Tidak ada komentar:
Posting Komentar