GRAF BIPARTISI LENGKAP BERLABEL DALAM MENYELESAIKAN MASALAH PENUGASAN
SKRIPSI
RONAL GOMAR PURBA 040803061
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010
Universitas Sumatera Utara
GRAF BIPARTISI LENGKAP BERLABEL DALAM MENYELESAIKAN MASALAH PENUGASAN
SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Sains
RONAL GOMAR PURBA 040803061
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010
Universitas Sumatera Utara
PERSETUJUAN
Judul
Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: GRAF BIPARTISI LENGKAP BERLABEL DALAM MENYELESAIKAN MASALAH PENUGASAN : SKRIPSI : RONAL G PURBA : 040803061 : SARJANA (S1) MATEMATIKA : MATEMATIKA : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA
Diluluskan di Medan, Juni 2010 Komisi Pembimbing: Pembimbing 2
Pembimbing 1
Drs. Henry Rani Sitepu, M.Si NIP. 19530303 198303 1 002
Prof. Dr. Herman Mawengkang NIP. 19461128 1974403 1 001
Diketahui/ Disetujui oleh Departemen Matematika FMIPA USU Ketua,
Dr. Saib Suwilo, M.Sc NIP. 19640109 198803 1 004
Universitas Sumatera Utara
PERNYATAAN
GRAPH BIPARTISI LENGKAP BERLABEL DALAM MENYELESAIKAN MASALAH PENUGASAN
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, Juni 2010
RONAL G PURBA NIM. 040803061
Universitas Sumatera Utara
PENGHARGAAN
Puji dan syukur penulis ucapkan serta panjatkan keapda Tuhan Yang Maha Kuasa atas kasih, berkat dan karuniaNya sehingga penulis dapat menyelesaikan ini. Skripsi ini berjudul “ Graf Bipartisi Lengkap Berlabel dalam Menyelesaikan Masalah Penugasan” diajukan sebagai salah satu syarat untuk memperoleh gelar sarjana pada Departemen Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara. Dalam kesempatan ini Penulis juga didukung dan dibantu oleh orang-orang yang ada di sekitar penulis. Oleh sebab itu penulis ingin mengucapkan terima kasih yang sebesar-besanya kepada: 1. Ayahanda dan Ibunda yang tersayang dan tercinta, Alm. M. Purba dan D br. Silaban yang telah mengasuh dan membesarkan penulis dengan rasa kasih dan sayang tulus yang tak terbatas. 2. Keluarga tercinta, T. Purba, E br. Purba, H. Purba, D br. Purba, L br. Purba, R br. Purba, James Edison Purba dan Lustina br. Purba yang selalu memberikan dukungan dan dorongan di setiap kondisi dan keadaan apa pun. 3. Rasdi Sirait yang selalu menemani penulis dalam langkah dan hari-hari penulis untuk menyelesaikan skripsi ini. 4. Bapak Prof. Herman Mawengkang dan Bapak Drs. Henry Rani Sitepu, M.Si selaku dosen pembimbing 1 dan dosen pembimbing 2 yang telah banyak memberikan masukan dan bantuan kepada penulis. 5. Bapak Drs. Djakaria Sebayang dan Bapak Drs. H Haluddin Panjaitan selaku dosen penguji buat penulis. 6. Teman-teman stambuk 2004 (Jekson, Golti, Jusian, Justinus, Darto, Domiatus, Halomoan, Mangasi, Lewin, Ukur Bangun, Hindra, Frans, Rista, Agnes, Kristin, Cani, Marta, Debo) dan lain-lain yang tidak dapat saya sebutkan satu per satu. Rekan-rekan stambuk 2005 khususnya Math ’05 FC (Marco, Jo, Paul, Mama, Sahat, Nixon, Nico, Doni, Cahaya, Opung, Reynold, Paskah, Andre, Firiska) serta Meilinda, Ester, Trisna, Christen Cs. Dan seluruh adik-adik stambuk 2006, 2007, 2008, dan 2009 thanks for all. 7. Untuk The Master College (TMC), Mr. Doni, S.Si, Miss Putri S.T, Miss Elisabet, S.P, Mr. Nelson, S.P, dan seluruh anak TMC serta Bapak Ir. Wesley Siagian (Sutomo 1 Medan). Dalam penyusunan skripsi ini mungkin terdapat kekurangan dan kesalahan, untuk itu penulis mengharapkan kritik dan saran yang membangun dari pembaca guna perbaikan skripsi ini. Akhirnya penulis berharap semoga skripsi ini dapat memberikan manfaat dan guna bagi para pembaca. Medan, Juni 2010 Penulis
Ronal G Purba
Universitas Sumatera Utara
ABSTRAK
Pengambilan kebijakan dalam suatu perusahaan atau instansi membutuhkan metodemetode dalam penugasan n pekerja terhadap m penugasan. Dengan menggunakan matriks penugasan akan dihasilkan satu pekerja ditempatkan pada satu tugas. Diharapkan terbentuk penugasan yang akan memberikan total keuntungan maksimum. Akan tetapi, dengan menggunakan algoritma matching bobot maksimum dalam graf bipartisi lengkap berlabel dibutuhkan perulangan sebanyak jumlah verteks sampai berhenti ketika diperoleh Alternating Tree dengan Augmenting Path.
Universitas Sumatera Utara
ABSTRACT
Decision making on the companies or institutions needs methods for assignment of n worker for m assignments. Using assignment matrices will be found the result a worker for an assignment. The form of the assignment will give the total of maximum profit. But by using maximum weight matching algorithm of labelling complete bipartition graph needed repeating as much the vertex amount until stoping when gotten Alternating tree and Augmenting Path.
Universitas Sumatera Utara
DAFTAR ISI
Halaman PERSETUJUAN PERNYATAAN PENGHARGAAN ABSTRAK ABSTRACT DAFTAR ISI DAFTAR TABEL DAFTAR GAMBAR
BAB 1
i ii iii iv v vi viii ix
PENDAHULUAN
1.1
Latar Belakang
1.2 1.3 1.4 1.5 1.6 1.7
Perumusan Masalah Batasan Masalah Tujuan Penelitian Manfaat Penelitian Metodologi Penelitian Tinjauan Pustaka
BAB 2
LANDASAN TEORI
1 2 2 2 3 3 3
2.1
Penugasan Sebagai Masalah Matching Bobot Maksimum Dalam Graf Bipartisi Lengkap Berlabel 2.1.1 Loop Dan Edge Paralel 2.1.2 Graf Sederhana (Simple Graf) 2.1.3 Ketetanggaan (Adjacent) 2.1.4 Bersisian (Incident) 2.1.5 Simpul Terpencil (Isolated Vertex) 2.1.6 Graf Kosong (Null Graf) 2.1.7 Derajat (Degree) 2.3 Jenis-JenisGraf 2.4 Defenisi Dan Teori Matching Dalam Graf Bipartisi 2.5 Penyajian Masalah Penugasan Dalam Graf Bipartisi Lengkap Berlabel
7 7 7 8 8 8 9 9 13 19
Universitas Sumatera Utara
BAB 3 3.1 3.2 3.3
PEMBAHASAN Penyelesaian Masalah Penugasan Secara Klasik Algoritma Untuk Mencari Matching Bobot Maksimum Penyelesaian Masalah Penugasan dengan Menggunakan Algoritma Matching Bobot Maksimum dalam Graf Bipartisi Lengkap Berlabel
BAB 4 KESIMPULAN DAN SARAN 4.1 Kesimpulan 4.2 Saran
26 26
28
40 40
DAFTAR PUSTAKA
Universitas Sumatera Utara
DAFTAR TABEL
Halaman Tabel 2.1 Matched edge, Unmatched edge, Matched Vertex dan Single Vertex Tabel 2.2 Bobot Tabel 3.1 Matriks Permutasi Tabel 3.2 Matriks Permutasi Berderajat 3 Untuk Mencari Enam Kemungkinan Penugasan Tabel 3.3 Kemungkinan Penugasan
16 22 24 23 25
Universitas Sumatera Utara
DAFTAR GAMBAR
Halaman Gambar 2.1 Matriks Penugasan Gambar 2.2 Simple Graf Gambar 2.3 Graf Kosong Gambar 2.4 Graf Berarah dan Graf Ganda Berarah Gambar 2.5 Graf Lengkap Gambar 2.6 Graf Lingkaran Gambar 2.7 Graf Bipartite Gambar 2.8 Graf Bipartisi Lengkap Gambar 2.9 Graf Bipartisi Dan Bipartisi Lengkap Gambar 2.10 Graf Bipartisi Berlabel Gambar 2.11 Matching M1 Gambar 2.12 Matching M1 Gambar 2.13 Matching Sempurna Gambar 2.14 Matching Bobot Maksimum Gambar 2.15a Augmenting M sepanjang P Gambar 2.15b Augmenting M sepanjang P Gambar 2.16 Graf Bipartisi Tanpa Komplit Matching dari V1 ke V2 Gambar 2.17 Graph Lengkap Berlabel dari Masalah Penugasan Gambar 3.1 Matching Awal M1={v1v5,v2 v7} Gambar 3.2 Alternating Tree tanpa Augmenting Path Gambar 3.3 Alternating Tree Tanpa Augmenting Path Gambar 3.4 Alternating Tree dengan Augmenting Path Gambar 3.5 Alternating Tree tanpa Augmenting Path Gambar 3.6 Alternating Tree tanpa Augmenting Path Gambar 3.7 Alternating Tree dengan Augmenting Path Gambar 3.8 Matching Maksimum M = {v1 v6, v2v8, v3v5, v4 v7}
4 8 8 10 10 10 11 11 12 13 13 14 15 15 17 18 19 20 29 31 32 33 35 36 38 39
Universitas Sumatera Utara
