Masalah Matching Maksimum pada Graf Non-bipartite Menggunakan Algoritma Kardinalitas Matching Edmonds dan Aplikasinya pada Kasus The Battle of Britain

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.

[img]
Preview
Text
12610006_BAB-I_IV-atau-V_DAFTAR-PUSTAKA.pdf - Published Version

Download (3MB) | Preview
[img]
Preview
Text
12610006_BAB-II_sampai_SEBELUM-BAB-TERAKHIR.pdf - Published Version

Download (3MB) | Preview

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

Item Type: Thesis (Skripsi)
Additional Information: Muchammad Abrori, S.Si., M.Kom.
Uncontrolled Keywords: kardinalitas matching edmonds, matching, matching maksimum
Subjects: Tehnik Industri
Divisions: Fakultas Sains dan Teknologi > Teknik Industri (S1)
Depositing User: Sugeng Hariyanto, SIP (sugeng.hariyanto@uin-suka.ac.id)
Date Deposited: 07 Apr 2017 14:50
Last Modified: 07 Apr 2017 14:50
URI: http://digilib.uin-suka.ac.id/id/eprint/25053

Share this knowledge with your friends :

Actions (login required)

View Item View Item
Chat Kak Imum