Problem of Maximum Matching in Non-Bipartite Graph Using Edmonds’ Cardinality Matching Algorithm and Its Application in the Battle of Britain Case CAUCHY –Jurnal Matematika Murni dan Aplikasi Volume 5(4) (2019), Pages 169-180 p-ISSN: 2086-0382; e-ISSN: 2477-3344 Submitted: July 18, 2017 Reviewed: October 09, 2017 Accepted: May 31, 2019 DOI: http://dx.doi.org/10.18860/ca.v5i4.4294 Problem of Maximum Matching in Non-Bipartite Graph Using Edmonds’ Cardinality Matching Algorithm and Its Application in the Battle of Britain Case Muchammad Abrori1, Mohammad Imam Jauhari 2 1,2 Department of Mathematics State Islamic University Sunan Kalijaga, Indonesia Email: borymuch@yahoo.com, jonycrish@gmail.com 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 INTRODUCTION A matching 𝑀 in 𝐺 is a subset of 𝐸(𝐺) where there are no two edges in 𝑀 that meet in the same vertex [3]. Matching concept can be used in many things especially for the problem of pairing. In the discussion about matching, there is a term called maximum matching. Maximum matching is matching 𝑀 with the highest cardinality [1]. Generally, the finding of maximum matching is performed in bipartite graph, but it can also be executed in non-bipartite graph. The process of finding the maximum matching in non-bipartite graph is a bit different from that in bipartite graph where in non-bipartite graph, it should contain at least an odd cycle that issues a blossom. A blossom can cause a failure in some algorithms of finding the maximum matching or it cannot be engaged in finding the maximum matching in non-bipartite graph. One of the algorithms that can be used in finding maximum matching in non- bipartite graph is Edmonds’ cardinality matching algorithm. This algorithm can handle a Problem of Maximum Matching in Non-Bipartite Graph Using Edmonds’ Cardinality Matching Algorithm and Its Application in the Battle of Britain Case Muchammad Abrori 170 blossom found in non-bipartite graph. Hence the process of finding maximum matching can be done without any obstacle even though there is a blossom while finding the maximum matching. METHODS The research was begun with studying the basic concept about graph theory which cover definition of basic graph, types of graph, subgraph and skelter subgraph, operation of graph, and basic concept about tree graph and matching concept in 𝐺 graph. Besides, the research also explains about Breadth-First Search (BFS) algorithm to arrange tree construction of alternating 𝑇. Then, it discusses Edmonds’ cardinality matching algorithm and its application in finding a maximum matching in a graph and in the last chapter, there is a sample of pairing a pilot in a war of Britain in 1940 which was taken from M. Gondran and Minoux’s book entitled “Graphs and Algorithms”. RESULTS AND DISCUSSION Definition: Matching [6] A matching 𝑀 in 𝐺 is a subset of a set 𝐸(𝐺) where there are no two edges in 𝑀 that meet at the same vertex. A 𝐺 graph with matching 𝑀 ⊆ 𝐸(𝐺) can be written in (𝐺, 𝑀). Example: A graph 𝐺1 with matching 𝑀 = {𝑣2𝑣3, 𝑣4𝑣5}. 𝐺1: There are two vertex terms in matching graph: 1. Saturated vertex is a vertex which is incident with the edges in matching 𝑀. [8] Example: In 𝐺1, the saturated vertex is vertex 𝑣2, 𝑣3, 𝑣4, 𝑣5. 2. Exposed vertex is a vertex which is not incident with each edge in matching M. [8]. Example: In 𝐺1, the exposed vertex is vertex 𝑣1 and 𝑣6. Apart from vertex, path in the matching graph is also divided into two kinds: 1. Alternating path is a path with the edges that alternate between the edge that is included in 𝑀 and not included in 𝑀. [7] Example: In 𝐺1 path 𝑃: 𝑣1 − 𝑣2 − 𝑣3 − 𝑣4 − 𝑣5 is an alternating path 2. Augmenting path is a path with the beginning and ending vertex that are exposed vertex. [7] Example: In 𝐺1 path 𝑃: 𝑣1 − 𝑣2 − 𝑣3 − 𝑣4 − 𝑣5 − 𝑣6 is an augmenting path Problem of Maximum Matching in Non-Bipartite Graph Using Edmonds’ Cardinality Matching Algorithm and Its Application in the Battle of Britain Case Muchammad Abrori 171 Maximum Matching Matching 𝑀 in a 𝐺 graph is called maximum if there is no matching 𝑀′in 𝐺 with |𝑀′| > |𝑀|. [1] Example: Graph with a matching that is not maximum yet Graph with a matching that is already maximum Matching Initialization Initialization process is used to shorten the finding of maximum matching in a graph. This process uses a help of simple greedy method as follows: [9] 1. 𝑀 = ∅ 2. If there is no more e edge which can be added into 𝑀, then stop 3. Otherwise, select e edge that does not have the same vertex with the edges in 𝑀 3.1 𝑀 = (𝑀 ∪ 𝑒) 4. Turn back to 𝑀. Blossom A blossom 𝐵 in a matching graph (𝐺, 𝑀) is an odd cycle with 𝑀 ∩ 𝐵 which is the maximum matching in 𝐵 with base which is an exposed vertex or outer vertex for 𝑀 ∩ 𝐵. [3] Example: In a case of bipartite graph, it is not possible to find a blossom while constructing alternating tree 𝑇 because bipartite graph does not have two vertices that are adjacent to each other at the same partition. Therefore, it is impossible for two vertices at the same layer to join each other [10]. The following below is the illustration: In non-bipartite graph In bipartite graph Problem of Maximum Matching in Non-Bipartite Graph Using Edmonds’ Cardinality Matching Algorithm and Its Application in the Battle of Britain Case Muchammad Abrori 172 A blossom in non-bipartite graph can raise a possibility of not finding an augmenting path while constructing alternating tree 𝑇 so that it causes a failure in the finding process of maximum matching [10]. Shrinking Blossom To prevent the problem caused by a blossom 𝐵, the process of shrinking and unshrinking should be done to a blossom 𝐵 that is encountered when the alternating tree 𝑇 is shrinking. A shrinking blossom is a shrinking process to odd cycle in (𝐺, 𝑀) by replacing all of the vertices and edges in blossom 𝐵 with a labeled vertex, for example 𝑏 with 𝑏 = 𝐵/𝐵. Vertex 𝑏 is called pseudovertex. When the unshrink process toward 𝑏 is not executed yet (by deleting label 𝑏 then replacing it with 𝐵 as it was), ignore all of the vertices in 𝐵 and all of the edges which join one vertex to the other in 𝐵. Besides, the unshrink process toward 𝑏 is a returning process of all vertices and edges included in blossom 𝐵 [3]. Example: Shrink Unshrink Below is a lemma which ensures that shrinking and unshrink process can be used in finding a maximum matching. Lemma of Shrinking Cycle [7] Supposed 𝐺 is a graph with matching 𝑀, and r is an exposed vertex in (𝐺, 𝑀). Supposed that during the process of establishing an alternating tree T with the root 𝑟, it encounters blossom 𝐵. If vertex 𝑤 is a base of blossom 𝐵 and graph 𝐺 ′ = 𝐺/𝐵 is a graph produced from the shrinking of blossom 𝐵 into pseudovertex 𝑏. Graph (𝐺, 𝑀) will contain an augmenting path that begins in vertex 𝑟 if and if only graph (𝐺 ′, 𝑀′) with matching 𝑀′ = 𝑀/𝐵 contains an augmenting path that starts in vertex 𝑟. Problem of Maximum Matching in Non-Bipartite Graph Using Edmonds’ Cardinality Matching Algorithm and Its Application in the Battle of Britain Case Muchammad Abrori 173 Alternating Tree An alternating tree 𝑇 is a tree whose edges alternate between the edge that is included in 𝑀 and not included in 𝑀 and are rooted in an exposed vertex of which each edge relates an inner vertex with an outer vertex thus every inner vertex in 𝑇 is exactly incident with two edges in 𝑇. Inner vertex is a vertex that occupies odd layer (1,3,5, … ), while outer vertex is a vertex that occupies even layer (0,2,4, … ) [3]. The following is the steps to construct an alternating tree 𝑇 using BFS: [7] (Root): Choose an exposed vertex 𝑟 in graph (𝐺, 𝑀). Make the exposed vertex 𝑟 as the root (layer 0) in alternating tree 𝑇. 1. In layer 1, add all the vertices 𝑎1, 𝑎2, 𝑎3, … , 𝑎𝑝 which are adjacent to the root 𝑟. Keep in mind that all of the vertices that are added are only saturated ones. 2. Add vertex 𝑏𝑖 = 𝑚𝑎𝑡𝑒(𝑎𝑖 ) on layer 2 (even) in 𝑇. 3. For the next layer, add all the vertices 𝑐1, 𝑐2, 𝑐3, … , 𝑐𝑝 where 𝑐𝑖 is adjacent to at least one 𝑏𝑖 , while the edge that relates 𝑐𝑖 with 𝑏𝑖 is not contained in 𝑀. Continue step 1, 2, and 3 until finding one of these two possibilities as follows: (a) an augmenting path, (b) an odd cycle. 4. If x is a vertex in layer 2i, and 𝑦 ≠ 𝑚𝑎𝑡𝑒(𝑥) is a vertex that is adjacent to 𝑥. So, there are four possibilities: Case 1: y is an exposed vertex (and not yet contained in 𝑇). So, an augmenting path has been found. Therefore, the constructing process of alternating tree 𝑇 is discontinued. Case 2: 𝑦 is not an exposed vertex; neither 𝑦 nor 𝑚𝑎𝑡𝑒(𝑦) is contained in 𝑇. So, add 𝑦 into layer 2𝑖 + 1 and m 𝑚𝑎𝑡𝑒(𝑦) into layer 2𝑖 + 2. Case 3: 𝑦 is already contained in 𝑇 as an inner vertex. So, a cycle with an even length has been found. Therefore, ignore if the condition below is found. Problem of Maximum Matching in Non-Bipartite Graph Using Edmonds’ Cardinality Matching Algorithm and Its Application in the Battle of Britain Case Muchammad Abrori 174 Case 4: 𝑦 is already contained in 𝑇 as an outer vertex. Blossom has been found. Stop the constructing process of alternating tree T and do the shrinking process of the blossom. The followings are theorems that become the basis of Edmonds’ cardinality matching algorithm in finding a maximum matching in a graph [7]. Theorem: [2] 𝑀1 and 𝑀2 are matching in graph 𝐺. If 𝐻 is a spanning subgraph of 𝐺, then in every component of 𝐻 with (𝐸(𝐻) = (𝑀1 − 𝑀2) ∪ (𝑀2 − 𝑀1) thing that should fulfill the following requirements: 1. An isolated vertex, 2. An even cycle in which the edge of the cycle alternates in 𝑀1 dan 𝑀2, 3. A path in which the edge of the path alternates in 𝑀1 dan 𝑀2 thus every end of the vertex is unsaturated in 𝑀1 or 𝑀2 but not in both. Theorem: [7] Matching 𝑀 in graph 𝐺 is called maximum if and if only there is no augmenting path in 𝐺 with respect to 𝑀. Edmonds’ Cardinality Matching Algorithm The followings are the steps from Edmonds’ cardinality matching algorithm: [4] Step 1 (initialization) Graph 𝐺 is a non-bipartite graph with matching 𝑀0 = Ø. Do the matching initialization in 𝐺 by using greedy algoritm. Step 2 (An Examination of exposed vertex) 2.1 If all vertices in (𝐺, 𝑀) are incident with a matching edge, go to step 5. 2.2 If there is only one unexamined exposed vertex in (𝐺, 𝑀), go to step 5. 2.3 Otherwise, select any exposed vertex 𝑟 in (𝐺, 𝑀) as a root and construct alternating tree 𝑇: 2.3.1 If the alternating tree 𝑇 ends with an exposed vertex 𝑠 wheres ≠ 𝑟, an augmenting path from 𝑟 to 𝑠 has been found. Go to step 3. 2.3.2 If the alternating tree 𝑇 encountered an odd cycle, stop the constructing process and go to step 4. Step 3 (Augmenting Path): 3.1 If the augmenting path 𝑃 obtained from the alternating tree 𝑇 contains pseudovertex 𝑏𝑖 (𝑖 = 1,2,3 … ), then unshrink the pseudovertex 𝑏𝑖 into a blossom 𝐵𝑖 as previously. By using path 𝑃, trace backwards starting from the exposed vertex s to vertex r (root) through an alternating path with an even length in blossom 𝐵𝑖 . Do the same steps until augmenting path in (𝐺, 𝑀) is found in which it does not contain any pseudovertex 𝑏𝑖 . Augment matching M in (𝐺, 𝑀) with 𝑀′ = 𝑀 ⊕ 𝑃. Go to step 3.2. Problem of Maximum Matching in Non-Bipartite Graph Using Edmonds’ Cardinality Matching Algorithm and Its Application in the Battle of Britain Case Muchammad Abrori 175 3.2 If the augmenting path 𝑃 that has been obtained from the alternating tree 𝑇 does not contain pseudovertex 𝑏𝑖 (𝑖 = 1,2,3 … ), then augment matching M in (𝐺, 𝑀) with 𝑀′ = 𝑀 ⊕ 𝑃. Go to step 2. Step 4 (Odd cycle) This step is reached only if the alternating tree 𝑇 encounters a cycle with an odd length (called blossom). Suppose a blossom 𝐵𝑖 (𝑖 = 1,2,3 … ) is encountered in the constructing process of alternating tree 𝑇, then shrink blossom 𝐵𝑖 into a pseudovertex 𝑏𝑖 . Continue the construction process of alternating tree 𝑇 with root 𝑟 as step 2. Step 5 The matching on graph 𝐺 is maximum. Stop the finding process. Sample Case (The Battle of Britain) In the Battle of Britain (1940), The Royal Air Force provided several aircrafts to thwart the German air force attack. The aircrafts provided by the Royal Air Force could be flown only by two people as a pilot and co-pilot. To get the best results in the mission to thwart German air force attack, the Royal Air Force brought some of the best pilots from all regions in Britain. However, there was a problem to solve by the Royal Air Force: among all the pilots that were called, some of them could not fly together in one aircraft because there were differences in terms of language, the ability of flying techniques, as well as in terms of flying experience. Suppose the Royal Air Force obtained 18 best pilots from all regions in Britain that were ready to fly the aircraft. Based on the problem, the Royal Air Force wished to pair the 18 pilots where each pair consisted of two pilots in such a way that the number of all the possible pairs is the highest number. In order to solve such problem, the Royal Air Force conducted a series of tests to the 18 pilots including language test, flying technique test, and psychological test to determine the suitability of the 18 pilots to fly together in one aircraft as a pilot and co-pilot [5]. Table 1 Table of pairing between each aircraft pilot The pilot’s number 𝒊 = (𝟏, 𝟐, … , 𝟏𝟖) The result of pairing between each aircraft pilot 1st Pilot Pilot: 2nd and 17th 2nd Pilot Pilot: 1st, 3rd, and 5th 3rd Pilot Pilot: 2nd, 4th, 5th, and 6th 4th Pilot Pilot: 3rd, 7th, and 9th 5th Pilot Pilot: 2nd, 3rd, and 6th 6th Pilot Pilot: 3rd, 5th, and 15th 7th Pilot Pilot: 4th, 8th, 9th, 11th, and 13th 8th Pilot Pilot: 7th, 9th, and 10th 9th Pilot Pilot: 4th, 7th, 8th, 10th, 13th, and 15th 10th Pilot Pilot: 8th, 9th, and 16th 11th Pilot Pilot: 7th, 12th, 13th, and 14th 12th Pilot Pilot: 11th and 14th 13th Pilot Pilot: 7th, 9th, 11th, and 14th 14th Pilot Pilot: 11th, 12th, and 13th 15th Pilot Pilot: 6th, 9th, 16th, and 18th 16th Pilot Pilot: 10th, 15th, and 18th 17th Pilot Pilot 1th 18th Pilot Pilot: 15th and 16th By transforming the problem into the form of graph, where the pilots are represented as a vertex and the corresponding relationship between each pilot is Problem of Maximum Matching in Non-Bipartite Graph Using Edmonds’ Cardinality Matching Algorithm and Its Application in the Battle of Britain Case Muchammad Abrori 176 represented as an edge, the following graph is obtained: (The following form of graph is taken from [7]): 𝐺2: By following the steps from Edmonds’ cardinality matching algorithm, we obtain maximum matching on graph 𝐺2 as follows: Step 1 (initialization): By doing the process of matching initialization to graph 𝐺2, we obtain graph (𝐺2, 𝑀) with 𝑀 = {𝑣1𝑣2, 𝑣3𝑣4, 𝑣5𝑣6, 𝑣7𝑣8, 𝑣9𝑣10, 𝑣11𝑣12, 𝑣13𝑣14, 𝑣15𝑣16} as follows: (𝐺2, 𝑀): Since there are still two exposed vertices left that are 𝑣17 and 𝑣18, then go to step 2.3 Step 2.3 : Vertex 𝑣17 is selected as the root, by using BFS we obtain an alternating tree 𝑇1 that corresponds to graph (𝐺2, 𝑀) as follows: Problem of Maximum Matching in Non-Bipartite Graph Using Edmonds’ Cardinality Matching Algorithm and Its Application in the Battle of Britain Case Muchammad Abrori 177 Tree 𝑇1: Since blossom 𝐵 = {𝑣4, 𝑣8, 𝑣9, 𝑣10} has been encountered, then go to step 4. Step 4: Shrink blossom 𝐵 = {𝑣4, 𝑣8, 𝑣9, 𝑣10} to obtain a graph as follows: (𝐺2 ′ , 𝑀1): By continuing the constructing process of alternating tree that corresponds to graph (𝐺2 ′ , 𝑀1), we obtain: Tree 𝑇2: Problem of Maximum Matching in Non-Bipartite Graph Using Edmonds’ Cardinality Matching Algorithm and Its Application in the Battle of Britain Case Muchammad Abrori 178 Since blossom 𝐵′ = {𝑏, 𝑣2, 𝑣3, 𝑣5, 𝑣6, 𝑣15, 𝑣16} has been encountered, then go to Step 4: Shrink blossom 𝐵′ = {𝑏, 𝑣2, 𝑣3, 𝑣5, 𝑣6, 𝑣15, 𝑣16} to obtain a graph as follows: (𝐺2 ′′, 𝑀2): By continuing the constructing process of alternating tree that corresponds to graph (𝐺2 ′′, 𝑀2), we obtain: Tree 𝑇3: Since an augmenting path 𝑃′′: 𝑣18 − 𝑏 ′ − 𝑣1 − 𝑣17 that contains pseudovertex 𝑏′ has been obtained, then go to step 3.1 Step 3.1: By unshrinking the pseudovertex 𝑏′, we obtain augmenting path 𝑃′: 𝑣18 − 𝑣15 − 𝑣16 − 𝑏 − 𝑣3 − 𝑣2 − 𝑣1 − 𝑣17 that contains pseudovertex 𝑏, then go to step 3.1 Step 3.1: By usnhrinking the pseudovertex 𝑏, we obtain augmenting path 𝑃: 𝑣18 − 𝑣15 − 𝑣16 − 𝑣10 − 𝑣9 − 𝑣4 − 𝑣3 − 𝑣2 − 𝑣1 − 𝑣17 which does not contain any pseudovertex , then go to step 3.2 Step 3.2: Augment the initial matching 𝑀 using augmenting path 𝑃, we obtain a new matching in (𝐺2, 𝑀) as follows: Problem of Maximum Matching in Non-Bipartite Graph Using Edmonds’ Cardinality Matching Algorithm and Its Application in the Battle of Britain Case Muchammad Abrori 179 (𝐺2, 𝑀′): Since all vertices in (𝐺2, 𝑀′) are incident with a matching edge, then go to step 5. Step 5: Matching 𝑀′ in graph 𝐺2 is maximum, therefore the finding process is discontinued. From the steps that have been done, we obtain a maximum matching 𝑀′ in 𝐺2 with cardinality of matching 𝑀’ that is |𝑀′| = 9. Matching 𝑀′ that has been obtained is the solution of the problem of pairing the 18 pilots as described above with details as follows: 1. Pilot number 1 pairs up with pilot number 17 2. Pilot number 2 pairs up with pilot number 3 3. Pilot number 4 pairs up with pilot number 9 4. Pilot number 5 pairs up with pilot number 6 5. Pilot number 7 pairs up with pilot number 8 6. Pilot number 10 pairs up with pilot number 16 7. Pilot number 11 pairs up with pilot number 12 8. Pilot number 13 pairs up with pilot number 14 9. Pilot number 15 pairs up with pilot number 18 And the maximum number of aircrafts that can be flown is as many as 9 aircrafts. CONCLUSION Matching 𝑀 in graph 𝐺 is a subset of 𝐸(𝐺) edge set where there are no two edges in Matching 𝑀 that meet each other at the same vertex in graph 𝐺. Generally, Edmonds’ cardinality matching algorithm is divided into three steps where the first step is the process of matching initialization. The second step is shrinking and unshrinking of blossom 𝐵𝑖 . The third step is to execute augmenting- 𝑀 if the augmenting 𝑃 path has been found. Edmonds’ cardinality matching algorithm can be applied to find for maximum matching especially towards non-bipartite graph. The process of matching initialization is the effort to find the first matching to fasten the finding of maximum matching. Alternating 𝑇 tree is a 𝑇 graph concept that is used to find an augmenting path to obtain a new matching that has bigger cardinality than the first matching from the process of matching initialization. Problem of Maximum Matching in Non-Bipartite Graph Using Edmonds’ Cardinality Matching Algorithm and Its Application in the Battle of Britain Case Muchammad Abrori 180 REFERENCES [1] Bondy, J. A., And Murty, U. S. R., 1976, Graph Theory with Applications, New York: Mac Millan Press. [2] Chartrand, G., And Lesniak, L., 1996, graph dan digraphs (third edition), London: Chapman dan Hill. [3] Edmons, Jack, 1965, paths, trees, and flowers, canadian j.math., 17, 449-467. [4] Evans, James R., and Edward Minieka, 1992, Optimization Algorithms for Networks and Graphs, New York: Marcel Dekker, Inc. [5] Gondran, M., and M. Minoux, 1984, Graphs and Algorithms, New York: Jhon Wiley & Sons. [6] Gross, Jonathan L., and Jay Yellen (Editors), 1999, Handbook of Graph Theory, USA: CRC Press. [7] Jungnickel, Dieter, 2008, Graphs, Networks, and Algorithms (Third Edition), Berlin: Springer – Verlag. [8] Lovasz, L., and M. D. Plummer, 1986, Matching Theory, USA: North – Holland. [9] Winter, 2005, Maximum Matching, CS105, www.cs.dartmouth.edu/~ac/Teach/CS105.../kavathekar-scribe.pdf [10] Zwick, U., 2009, Maximum Matching in Bipartite and Non-bipartite Graphs, http://www.cs.tau.ac.il/~zwick/grad-algo-0910/match.pdf http://www.cs.dartmouth.edu/~ac/Teach/CS105.../kavathekar-scribe.pdf http://www.cs.tau.ac.il/~zwick/grad-algo-0910/match.pdf