PENENTUAN MATCHING MAKSIMUM PADA GRAF BIPARTIT BERBOBOT MENGGUNAKAN METODE HUNGARIAN

RINA WAHYUNINGSIH - NIM. 05610034 , (2011) PENENTUAN MATCHING MAKSIMUM PADA GRAF BIPARTIT BERBOBOT MENGGUNAKAN METODE HUNGARIAN. Skripsi thesis, UIN Sunan Kalijaga Yogyakarta.

Full text not available from this repository.

Abstract

ABSTRAK Matching merupakan bagian dari teori graf yang membahas mengenai pemasangan. Matching M adalah himpunan dari sisi E(G) sedemikian sehingga tidak ada dua sisi yang incident pada simpul yang sama. Matching dapat digunakan untuk menyelesaikan banyak persoalan, salah satunya adalah masalah penugasan (assignment problem). Masalah penugasan merupakan pemasalahan memasangkan n pegawai dan n tugas sedemikian sehingga setiap pegawai mendapatkan satu tugas, dan tiap tugas diberikan tepat kepada satu pegawai. Masalah penugasan dapat diilustrasikan dalam graf bipartit berbobot, yakni dengan menempatkan n pegawai pada himpunan simpul X, n tugas pada himpunan simpul Y, dan sisi yang memuat bobot menunjukkan nilai pegawai terhadap tugas. Masalah penugasan dapat diselesaikan dengan menentukan matching pada graf bipartit berbobot melalui metode Hungarian. Langkah awal metode ini adalah dengan melakukan pelabelan simpul x dan y, lalu dipilih matching awal. Jika setiap simpul pada himpunan X merupakan simpul saturated, maka matching telah maksimum, namun jika terdapat simpul unsaturated maka simpul tersebut digunakan sebagai simpul akar pohon alternating. Dapatlah ditentukan dari pohon alternating suatu lintasan yang terbentuk. Jika ditemukan lintasan augmenting, maka lintasan augmenting ini digunakan untuk membentuk matching yang lebih banyak. Jika yang terbentuk adalah lintasan alternating, maka dilakukan pelabelan simpul baru, hingga ditemukan lintasan augmenting. Proses ini terus diulang hingga tidak ditemukan lagi simpul unsaturated pada himpunan simpul X. Matching disebut maksimum jika telah memenuhi semua simpul pada himpunan X. Matching ini merupakan matching sempurna dengan jumlah bobot sisi yang maksimum pada graf bipartit berbobot. Matching yang dihasilkan merupakan solusi dari masalah penugasan yakni memasangkan seorang pegawai dengan sebuah tugas. div

Item Type: Thesis (Skripsi)
Additional Information / Pembimbing: Pembimbing: Muchammad Abrori, S.Si, M.Kom.
Uncontrolled Keywords: matching, graf, masalah penugasan, metode Hungarian
Depositing User / Editor: Users 1 not found.
Last Modified: 04 May 2012 16:49
URI: http://digilib.uin-suka.ac.id/id/eprint/6074

Actions (login required)

View Item View Item