Problem of Maximum Matching in Non-Bipartite Graph Using Edmonds’ Cardinality Matching Algorithm and Its Applicationin the Battle of Britain Case
| Main Authors: | Abrori, Muchammad, Jauhari, Mohammad Imam |
|---|---|
| Other Authors: | Prodi Matematika Fakultas Sains dan Teknologi UIN Sunan Kalijaga Yogyakarta |
| Format: | Article info application/pdf eJournal |
| Bahasa: | eng |
| Terbitan: |
Mathematics Department, Maulana Malik Ibrahim State Islamic University of Malang
, 2019
|
| Subjects: | |
| Online Access: |
http://ejournal.uin-malang.ac.id/index.php/Math/article/view/4294 http://ejournal.uin-malang.ac.id/index.php/Math/article/view/4294/pdf |
Daftar Isi:
- Matching is a part of graph theory that discusses pair. A matching M is called to be maximum if M has the highest number of elements. A blossom which is encountered in non-bipartite graph can cause failure in process of finding the maximum matching in non-bipartite graph. One of the algorithms that can be used to find a maximum matching in non-bipartite graph is Edmonds’ Cardinality Matching Algorithm. Shrinking process is done in each blossom Bi that is encountered to become pseudovertex bi, in a way that each blossom does not interfere the process of finding a maximum matching in non-bipartite graph. In order to accelerate the finding, simple greedy method is used to perform initialization of matching and BFS algorithm is also used in constructing an alternating tree in a non-bipartite graph.The research discussed the finding of maximum matching in non-bipartite graph using Edmonds’ cardinality matching algorithm. In addition, this research gave a sample of its application in the resolution of The Battle of Britain case. The result obtained is a maximum matching in non-bipartite graph. The maximum matching obtained is a solution to the case of The Battle of Britain.