View Artikel Ilmiah

Kembali
NIM (Student Number)H1B009001
Nama MahasiswaDESIH PURNAMASARI
Judul ArtikelAlgoritma Kuhn-Munkres dalam Penentuan Matching Sempurna pada Graf Bipartit
AbstrakMatching merupakan himpunan sisi yang saling bebas di suatu graf G. Jika setiap simpul di graf bersisian dengan suatu sisi pada matching M, maka disebut matching sempurna. Salah satu algoritma yang dapat digunakan untuk menemukan matching sempurna berbobot optimal adalah Algoritma Kuhn-Munkres. Prinsip dasar dari algoritma tersebut adalah menentukan feasible vertex labelling yang akan digunakan untuk menemukan equality subgraph. Kemudian, equality subgraph tersebut digunakan untuk menemukan matching sempurna berbobot optimal. Untuk mempercepat penentuan matching sempurna, pada equality subgraph dipilih matching maksimum.
Abstrak (Inggris)Matching is a set of independent edges in a graph G. If each vertex in the graph G incident with the edge on the matching M, then it is called a perfect matching. The Kuhn-Munkres Algorithm is one of the algorithm that can be used to find the perfect matching with optimal weight. The basic principle of the algorithm is to determine a feasible vertex labelling that will be used to find the equality subgraph. Then, the equality subgraph will be used to find the perfect matching with optimal weight. To accelerate the determination of a perfect matching, on the equality subgraph, the maximum matching has to be chosen.
Kata KunciMatching sempurna, Algoritma Kuhn-Munkres, feasible vertex labelling, equality subgraph, dan matching maksimum.
Nama Pembimbing 1Triyani, M.Si.
Nama Pembimbing 2Agus Sugandha, M.Si.
Tahun2013
Jumlah Halaman11
Page generated in 0.0585 seconds.