View Artikel Ilmiah
KembaliNIM (Student Number) | H1B009001 |
---|---|
Nama Mahasiswa | DESIH PURNAMASARI |
Judul Artikel | Algoritma Kuhn-Munkres dalam Penentuan Matching Sempurna pada Graf Bipartit |
Abstrak | Matching 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 Kunci | Matching sempurna, Algoritma Kuhn-Munkres, feasible vertex labelling, equality subgraph, dan matching maksimum. |
Nama Pembimbing 1 | Triyani, M.Si. |
Nama Pembimbing 2 | Agus Sugandha, M.Si. |
Tahun | 2013 |
Jumlah Halaman | 11 |
Page generated in 0.0585 seconds.