PENENTUAN MATCHING MAKSIMUM PADA GRAF BIPARTIT BERBOBOT MENGGUNAKAN METODE HUNGARIAN

Muchammad Abrori(1*), Rina Wahyuningsih(2),

(1) Jurusan Matematika, Universitas Islam Negeri Sunan Kalijaga, Jln. Adi Sucipto no. 1, Jogjakarta
(2) Jurusan Matematika, Universitas Islam Negeri Sunan Kalijaga, Jln. Adi Sucipto no. 1, Jogjakarta
(*) Corresponding Author
DOI: https://doi.org/10.23917/jiti.v11i1.984

Abstract

Matching is a part of graph theory that discuss to make a pair, that can be used to solve many problems; one of them is the assignment problem. The assignment problem is to make a pair problem for n as the employees and for n as the duties, therefore each employee gets one duty, and each duty is given exactly for each employee. The assignment problem can be solved by determining the matching in weighted bipartite graph through Hungarian Method. It can be determined from the alternating tree of a formed edge. If there is augmenting path, that augmenting path is used to form the more number of matching. If the formed path is alternating path, therefore the process is labeling the new node until finding the augmenting vertices. This matching is called as the perfect matching with the number of maximum weighed side in weighted bipartite graphs. The result matching is the solution for the assignment problem by giving an employee with a duty.

Keywords

matching; graph; assignment problem; Hungarian method

References

Anton, Howard, 1987, Aljabar Linear Elementer: Jakarta.

Berge, Coulde, 1970, Graph and Hypergraph, Dunod: Netherlands.

Bondy, J.A dan Murty, U.S.R., 1976, Graph Theory with Applications, Mac Millan Press: New York.

Chartrand, Gary dan Oellermann, Ortrud, 1993, Applied and Algoritmic Graph Theory, Mc Graw Hill International Edition: New York.

Gondran, M. dan Minoux, M., 1984, Graphs and Algorithms. John Wiley & Sons, Ltd.: Chichester, Inggris.

Kocay, William dan Kreher, Donald, 2005, Graph Theory and Optimization, Chapman & Hall / CRC.

Magun, J., 2000. Greedy Matching Algorithms, an Experimental Study. Schweizerischer Nationalfond, Grant NF 2000-422 44.94. Zűrich, Switzerland.

Venkateswaran, R., Obranivic, Z., Raghavendra, C.S., 1993. Cooperative Genetic for Optimization Problem in Distributed Computer System. Technical report TR-EECS-93-018. School of EECS. Washington State University.

Wibisono, Samuel, 2008, Matematika Diskrit. Edisi Kedua, Graha Ilmu: Yogyakarta.

Article Metrics

Abstract view(s): 1255 time(s)
PDF (Bahasa Indonesia): 3326 time(s)

Refbacks

  • There are currently no refbacks.