Problem of Maximum Matching in Non-Bipartite Graph Using Edmonds’ Cardinality Matching Algorithm and Its Applicationin the Battle of Britain Case

Abstract

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.

Keywords

• edmonds’ cardinality matching, maximum matching, the battle of britain