eprintid: 25053
rev_number: 10
eprint_status: archive
userid: 6
dir: disk0/00/02/50/53
datestamp: 2017-04-07 07:50:43
lastmod: 2017-04-07 07:50:44
status_changed: 2017-04-07 07:50:43
type: thesis
metadata_visibility: show
creators_name: Mohammad Imam Jauhari, NIM. 12610006
title: Masalah Matching Maksimum pada Graf Non-bipartite
Menggunakan Algoritma Kardinalitas Matching Edmonds dan
Aplikasinya pada Kasus The Battle of Britain
ispublished: pub
subjects: TA
divisions: jur_tind
full_text_status: public
keywords: kardinalitas matching edmonds, matching, matching maksimum
note: Muchammad Abrori, S.Si., M.Kom.
abstract: banyak penggunaannya. Matching merupakan bagian dari teori graf yang
membahas tentang masalah pemasangan. Matching maksimum merupakan
matching dengan jumlah elemen terbanyak. Pencarian matching maksimum
lebih sukar dilakukan pada graf non-bipartite dikarenakan terdapat minimal
satu buah cycle ganjil yang menyebabkan munculnya sebuah blossom.
Sebuah blossom dapat menyebabkan gagalnya proses pencarian matching
maksimum pada suatu graf non-bipartite. Dalam penelitian ini akan
dilakukan pencarian matching maksimum pada suatu graf non-bipartite
menggunakan algoritma kardinalitas matching Edmonds.
Algoritma kardinalitas matching Edmonds merupakan algoritma yang
mampu digunakan dalam melakukan pencarian matching maksimum pada
graf non-bipartite. Penyusutan dilakukan terhadap setiap blossom Bi yang
ditemui menjadi sebuah pseudovertex bi. Guna mempercepat pencarian
matching maksimum digunakan metode greedy sederhana untuk melakukan
inisialiasi matching terhadap graf G. Penyusunan pohon alternating
dilakukan apabila masih terdapat lebih dari 2 simpul exposed di (G, M).
Dengan menggunakan algoritma kardinalitas matching Edmonds
diperoleh sebuah matching maksimum pada sebuah graf non-bipartite dengan
kardinalitas terbesar. Matching maksimum yang dihasilkan merupakan solusi
dari permasalahan pemasangan pilot pada kasus The Battle of Britain yakni
setiap dua pilot dapat dipasangkan ke dalam satu pesawat tempur serta hasil
pemasangan masing-masing pilot merupakan pemasangan dengan jumlah
pasangan terbanyak.
Kata kunci : kardinalitas matching edmonds, matching, matching maksimum
date: 2017-02-16
date_type: published
pages: 107
institution: UIN SUNAN KALIJAGA YOGYAKARTA
department: Fakultas Sains dan Teknologi
thesis_type: skripsi
thesis_name: other
citation:   Mohammad Imam Jauhari, NIM. 12610006  (2017) Masalah Matching Maksimum pada Graf Non-bipartite Menggunakan Algoritma Kardinalitas Matching Edmonds dan Aplikasinya pada Kasus The Battle of Britain.  Skripsi thesis, UIN SUNAN KALIJAGA YOGYAKARTA.   
document_url: https://digilib.uin-suka.ac.id/id/eprint/25053/1/12610006_BAB-I_IV-atau-V_DAFTAR-PUSTAKA.pdf
document_url: https://digilib.uin-suka.ac.id/id/eprint/25053/2/12610006_BAB-II_sampai_SEBELUM-BAB-TERAKHIR.pdf