Skripsi

Penentuan matching maksimal dan matching maksimum pada graph sederhana / Irawati Dwi Anggraeni

Abstrak
ABSTRAK Anggraeni Irawati Dwi. 2009. Penentuan Matching Maksimal dan Matching Maksimum pada Graph Sederhana. Skripsi Jurusan Matematika FMIPA Universitas Negeri Malang. Pembimbing (I) Prof. Drs. Purwanto Ph.D (II) Dr. Subanji S.Pd M.Si. Kata Kunci Matching Matching Maksimal Matching Maksimum Teori graph merupakan salah satu cabang matematika yang menarik untuk dibahas. Penggunaan teori graph dalam kehidupan nyata sudah cukup banyak dilakukan di masyarakat. Salah satu contoh penerapannnya adalah untuk masalah penugasan (assignment problem). Pokok bahasan dalam teori graph yang digunakan untuk menyelesaikan masalah penugasan ini adalah matching. Matching dalam graph adalah himpunan sisi-sisi yang non adjacent dimana tidak ada dua sisi yang mempunyai titik akhir sama. Matching maksimal dalam graph adalah matching yang ukurannya tidak dapat diperbesar. Untuk menentukan matching maksimal pada suatu graph dapat digunakan sebuah algoritma sebagai alat bantu yaitu algoritma Greedy. Matching maksimum dalam graph adalah matching dengan ukuran paling maksimum (paling banyak). Untuk menentukan matching maksimum pada suatu graph dapat digunakan sebuah algoritma sebagai alat bantu yaitu algoritma Edmonds. Setiap matching maksimum pasti maksimal tetapi tidak semua matching maksimal pasti maksimum. Algoritma Greedy pada pencarian matching maksimal dan algoritma Edmonds pada pencarian matching maksimum dapat digunakan untuk memcahkan masalah dalam kehidupan sehari-hari misalkan pada penentuan pasangan pegawai yang dapat bekerja sama dalam suatu kantor untuk menentukan pasangan pekerja yang dapat berkolaborasi dalam menyelesaikan sebuah proyek dan juga untuk menentukan daerah yang dapat dikunjungi sales agar pengiriman barang lebih optimal.

Informasi Detail

DDC

Rs 511.66 ANG p

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2009.

Deskripsi Fisik

ix, 52 lembar : il., ; 30 cm

Bahasa

Indonesia

No Reg

03265/KI/09

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang. 2009

Subjek

1. MATCHING
2. GRAPH

Pembimbing

1. Purwanto 2. Subanji

Lampiran Berkas