%0 Thesis
%9 Skripsi
%A RINA WAHYUNINGSIH - NIM. 05610034 ,  
%B /S1 - Skripsi/Fakultas Saintek/
%D 2011
%F digilib:6074
%I UIN Sunan Kalijaga Yogyakarta
%K matching, graf, masalah penugasan, metode Hungarian
%T PENENTUAN MATCHING MAKSIMUM PADA GRAF BIPARTIT BERBOBOT MENGGUNAKAN METODE HUNGARIAN
%U https://digilib.uin-suka.ac.id/id/eprint/6074/
%X  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 
%Z Pembimbing: Muchammad Abrori, S.Si, M.Kom.