PENGGUNAAN ALGORITMA KUHN MUNKRES UNTUK MENDAPATKAN MATCHING MAKSIMAL PADA GRAF BIPARTIT BERBOBOT

Oleh :
GURITNA NOOR AINATMAJA - M0101033 -

ABSTRAK Guritna Noor Ainatmaja, 2009. PENGGUNAAN ALGORITMA KUHN MUNKRES UNTUK MENDAPATKAN MATCHING MAKSIMAL PADA GRAF BIPARTIT BERBOBOT, Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sebelas Maret. Masalah penempatan calon pegawai ke dalam posisi jabatan pekerjaan dapat dibawa ke dalam graf teori dengan mencari matching maksimal pada graf bipartit berbobot. Matching maksimal pada graf bipartit berbobot dapat diselesaikan dengan menggunakan algoritma Kun Munkres. Tujuan dari penulisan ini adalah mendapatkan matching maksimal pada graf bipartit berbobot, menentukan kompleksitas running time algoritma Kuhn Munkres, dan menyusun sebuah program untuk mencari matching maksimal pada graf bipartit berbobot. Metode yang digunakan dalam penulisan skripsi ini adalah studi literatur. Oleh karena itu, materi bersumber dari buku-buku referensi dan jurnal yang berhubungan dengan matching maksimal pada graf bipartit berbobot, algoritma, kompleksitas waktu O-Besar, dan bahasa pemrograman dengan menggunakan software Matlab 6.1. Dari pembahasan disimpulkan bahwa matching maksimal pada graf bipartit berbobot dapat diselesaikan dengan menggunakan algoritma Kuhn Munkres. Kompleksitas waktu dalam kasus terburuk algoritma Kuhn Munkres adalah sebesar ( ) 4 n O . Untuk data n vertex yang besar dapat diselesaikan dengan pembuatan program menggunakan software Matlab 6.1.