Swadian, Ayu (2007) Penentuan matching maksimum pada Bipartite Graph [Bigraph]. Sarjana thesis, Universitas Brawijaya.
Abstract
Matching M pada graph G = (V , E) adalah himpunan bagian dari himpunan sisi-sisi E(G) di mana tidak ada dua dari masing-masing titiknya yang adjacent. Teori matching ini pada umumnya digunakan untuk menyelesaikan Job Assignment Problem (masalah penugasan kerja) di mana masalah tersebut direpresentasikan pada bipartite graph (bigraph). Pada Tugas Akhir ini akan ditentukan matching maksimumnya dengan menggunakan metode Hungarian, yaitu dengan membentuk sembarang matching M yang kemudian dicari M-augmenting path melalui M-alternating path untuk mendapatkan matching yang lebih besar dari M (Teorema Hall). Metode Hungarian ini dapat diaplikasikan untuk menentukan matching maksimum bigraph berbobot (Algoritma Kuhn-Munkres), di mana akan ditentukan juga bobot maksimum atau minimumnya.
English Abstract
Matching M in graph G = (V , E) is subset of edges set E (G) where there is no two from each edges which adjacent. The theory of matching in general is used to solve Job Assignment Problem where the problem is representated at bipartite graph (bigraph). In this paper, it will be determined maximum matching by using the Hungarian method, by construct any matching M then search for M-augmenting path through M-alternating path to get matching larger ones from M (Hall Theorem). The Hungarian method can be applicated to determine maximum matching problem at weighted bigraph (Kuhn-Munkres algorithm), where it also will be determined the maximum or minimum weight.
Other obstract
-
| Item Type: | Thesis (Sarjana) |
|---|---|
| Identification Number: | SKR/MIPA/2007/050701706 |
| Uncontrolled Keywords: | lternating tree, augmenting path, Kuhn-Munkres algorithm, Hall Theorem, maximum matching, The Hungarian method. |
| Subjects: | 500 Natural sciences and mathematics > 510 Mathematics |
| Divisions: | Fakultas Matematika dan Ilmu Pengetahuan Alam > Matematika |
| Depositing User: | Unnamed user with email repository.ub@ub.ac.id |
| Date Deposited: | 16 Jul 2007 00:00 |
| Last Modified: | 24 Nov 2021 07:45 |
| URI: | http://repository.ub.ac.id/id/eprint/151596 |
Preview |
Text
050701706.pdf Download (2MB) | Preview |
Actions (login required)
 |
View Item |