eprintid: 6074
rev_number: 1
eprint_status: archive
userid: 8
dir: disk0/00/00/60/74
lastmod: 2012-05-04 16:49:18
status_changed: 2012-05-04 16:49:18
type: thesis
metadata_visibility: show
creators_name: RINA WAHYUNINGSIH - NIM. 05610034 ,  
title: PENENTUAN MATCHING MAKSIMUM PADA GRAF BIPARTIT BERBOBOT MENGGUNAKAN METODE HUNGARIAN
ispublished: pub
full_text_status: none
keywords: matching, graf, masalah penugasan, metode Hungarian
note: Pembimbing: Muchammad Abrori, S.Si, M.Kom.
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 
date: 2011-06-23
date_type: published
institution: UIN Sunan Kalijaga Yogyakarta
department: /S1 - Skripsi/Fakultas Saintek/
thesis_type: skripsi
refereed: TRUE
referencetext: 
	
	
	
		
	
	jenis bahasa : Bahasa Indonesia ; 
	
	1
	update terakhir : 2011-06-23 11:34:51 ; 
	nama file diserver lama : digilib-uinsuka--rinawahyun-6073-1-rinawah-n.pdf ; 
	letak file diserver lama : ./files/disk1/122/digilib-uinsuka--rinawahyun-6073-1-rinawah-n.pdf ; 
	url download server lama : /download.php?id=6716 ; 
	nama file lama : RINA WAHYUNINGSIH - NIM. 05610034 PENENTUAN MATCHING MAKSIMUM PADA GRAF BIPARTIT BERBOBOT MENGGUNAKAN METODE HUNGARIAN.pdf ; 
	format file : application/pdf ; 
	besar file : 577650 Kb. 
	penulis :  ; 

	
		1
	
	
	1
	update terakhir : 2011-06-23 11:34:51 ; 
	nama file diserver lama : digilib-uinsuka--rinawahyun-6073-1-rinawah-n.pdf ; 
	letak file diserver lama : ./files/disk1/122/digilib-uinsuka--rinawahyun-6073-1-rinawah-n.pdf ; 
	url download server lama : /download.php?id=6716 ; 
	nama file lama : RINA WAHYUNINGSIH - NIM. 05610034 PENENTUAN MATCHING MAKSIMUM PADA GRAF BIPARTIT BERBOBOT MENGGUNAKAN METODE HUNGARIAN.pdf ; 
	format file : application/pdf ; 
	besar file : 577650 Kb. 
	penulis :  ; 

	
	Copyright (c) 2010 by Perpustakaan Digital UIN Sunan Kalijaga Yogyakarta. Verbatim copying and distribution of this entire article is permitted by author in any medium, provided this notice is preserved.
citation:   RINA WAHYUNINGSIH - NIM. 05610034 ,   (2011) PENENTUAN MATCHING MAKSIMUM PADA GRAF BIPARTIT BERBOBOT MENGGUNAKAN METODE HUNGARIAN.  Skripsi thesis, UIN Sunan Kalijaga Yogyakarta.