# Maximum Matchings of a Digraph Based on the Largest Geometric Multiplicity

Authors: Yunyun Yang; Gang Xie
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

Matching theory is one of the most forefront issues of graph theory. Based on the largest geometric multiplicity, we develop an efficient approach to identify maximum matchings in a digraph. For a given digraph, it has been proved that the number of maximum matched nodes has close relationship with the largest geometric multiplicity of the transpose of the adjacency matrix. Moreover, through fundamental column transformations, we can obtain the matched nodes and related matching edges. In particular, when a digraph contains a cycle factor, the largest geometric multiplicity is equal to one. In this case, the maximum matching is a perfect matching and each node in the digraph is a matched node. The method is validated by an example.


---

## Body

## 1. Introduction

Matching theory is one of the fundamental branches of graph theory. Historically, matching not only can be used for us to understand the structure of a graph which plays a crucial role but also has been related to a wide range of important problems in theoretical aspects, such as combinatorial optimization, crystal physics, and theoretical computer science research. In addition, matching theory is also closely linked with practical problems in work arrangements, resource allocation, information transmission, network flow, transportation and postservice, and so forth. To solve these problems we need to seek the maximum matching which is one of the core issues in matching theory [1–3]. Not only is it interesting by itself, but it can also be used to solve an army of other problems in combinatorial optimization [4–6]. Therefore, the work of the maximum matching theory has profound theoretical significance and wide application background.The maximum matching in an undirected graph is a maximum set of edges without common nodes. The book by Burkard et al. [7] reviewed thoroughly the bipartite matching problem. The popular classic method using the Hopcroft-Karp algorithm needs the determination of the bipartite equivalent graph. For arbitrary graphs, it is complicated to find a maximum matching and Edmonds and Karp [8] presented a polynomial algorithm. It was a major breakthrough and innovation to find a maximum matching. Additionally, on this basis, a multitude of algorithms are given in the literatures [9–13]. Subsequently, the work [14] gave a few maximum matching problems such as the maximum-cardinality matching problem and the minimum cost perfect matching problem. Later, Dobson et al. [15] developed a new kind of maximum matching graphs. They pointed out maximum matchings of special graphs such as trees, cycles, or complete graphs. Reference [16] presented minimization of the Laplacian spectral radius of trees with given matching number. Moreover, Duarte et al. [17] established a method to maintain maximum matching under addition and deletion of edges in a graph. Even et al. [18] then proposed a method of computing rough estimate maximum-cardinality matchings and estimation maximum weight matchings based on deterministic distributed algorithms. The work in [19] introduced an algorithm to calculate maximum matchings in a bipartite graph.However, the abovementioned study was focused on undirected graphs. Relatively speaking, for the maximum matching of digraphs only a little research has been conducted. Additionally, the solution of the matching is mainly based on the bipartite graph method, while the solution of the bipartite graph itself remains a tough issue. So we are still in lack of mature theories and algorithms. Therefore, we put forward a new method to identify maximum matchings in a digraph. The main idea of the method stems from two conditions of controllability of complex networks [20, 21]. The process of the method is simple, yet effective. In a sense, the work of this paper has developed and enriched matching theory.The rest of the paper is organized as follows. Section2 introduces the basic notations and definitions used in this paper. In Section 3, the technique in the case of a digraph is presented. The first part of Section 3 describes the technical concept based on minimum input theorem [20] and the largest geometric multiplicity theorem [21], and the second part of it introduces the algorithm steps. Section 4 presents an example to validate the method and Section 5 gives the conclusion and future work.


## 2. Notations and Preliminaries

For integrity, we give a few notations and definitions in this section.LetGD be a digraph which consists of a nonempty finite set V of elements called nodes and a finite set E of ordered pairs of different nodes called edges. We write GD=(V,E). The size of GD is the number of nodes in GD, denoted by GD=N. In Figure 1, for instance, V={1,2,3,4,5,6}, E={(1,3),(2,3),(3,4),(4,5),(4,6),(6,4)}.Figure 1
A digraph with six nodes and six edges.We first generalize the concepts of geometric multiplicity of an eigenvalue, matching, and maximum matching in an undirected graph (in a digraph) and its bipartite representation (see [20]).Definition 1.
Given a matrixA with the eigenvalue λ, the dimension of the eigenspace of A corresponding to the eigenvalue λ is called the geometric multiplicity of the eigenvalue λ.Notice that the geometric multiplicity is the largest number of linearly independent eigenvectors associated with an eigenvalue.Definition 2.
For an undirected graph, a matchingM is an independent set of edges, where no two share a node. A node is matched if it is incident to an edge in the matching. Otherwise, the node is unmatched.Definition 3.
For an undirected graph, a maximum matchingM∗ is a matching of maximum-cardinality among all matchings. A maximum matching M∗ is a perfect matching if all nodes are matched.Similarly, we consider the cases in a digraph and give the definitions of a matching and maximum matching of a digraph and its bipartite representation.Definition 4.
For a digraph, matchingMD is a subset of edges with no common starting-nodes or no common ending-nodes. That is to say, no two edges in MD share a common starting-node or a common ending-node. A node is matched if it is an ending-node of a matching edge. Otherwise, it is unmatched.Definition 5.
For a digraph, a matching of maximum-cardinality is called a maximum matching, symbolized byMD∗. A maximum matching MD∗ is called perfect if all nodes in the digraph are matched.DenoteMD∗ as the size of the maximum matching MD∗ in GD. It is found that if maximum matching MD∗ is perfect, then MD∗=N, where N means the number of nodes in GD.For the maximum matching of a digraph, a simple algorithm based on bipartite graph is described below. A bipartite graph is defined asF(V)=(V+∪V-,Γ). Here, V+={v1+,v2+,…,vN+} and V-={v1-,v2-,…,vN-} are the sets of nodes corresponding to the N nodes in GD, respectively. Edge set Γ=vi+,vj-∣eij≠0. See Figure 2. First, we split each node v into two nodes vi+ and vi- to make a digraph GD transform to its bipartite graph representation F(V). Then we connect an edge between nodes vi+ and vj- in F(V) if there is an edge eij in GD. In this way, we get a general bipartite graph. Afterwards, maximum matchings of the bipartite graph can be found using the classical Hopcroft-Karp algorithm as shown in Figure 2.Figure 2
Matching in a digraph and its bipartite representation. (a) A simple digraph is composed of five nodes and five edges. (b) The bipartite representation of the digraph shown in (a). Its maximum matching is displayed in green. Matched (or unmatched) nodes are displayed in green (or red), respectively.
(a)
(b)A maximum matching inGD contains the maximum possible number of nodes in Γ. It is worth noting that, generally, a given digraph could include several different maximum matchings. In addition, as long as the digraph contains a cycle factor, its maximum matching is a perfect matching.However, when the size of a digraph is large it is exceedingly arduous to find its maximum matchings by using bipartite graph method. Consequently, it is desirable to propose a practical method as mentioned below to solve this problem.


## 3. Maximum Matchings of a Digraph Based on Largest Geometric Multiplicity

Motivated by the relation between maximum matchings and controllability of directed networks, the method proposed in the paper is derived from two conditions of controllability of complex networks [20, 21]. In this section, the theoretical basis and its calculation steps are described in detail.


### 3.1. The Theoretical Basis

First, two conditions of controllability of complex networks are reviewed.Consider a linear time-invariant (LTI) dynamics (1) on a directed network or digraph GD,(1)x˙=Bx+Qu,where x=(x1,x2,…,xN)T∈RN is called the state vector, the state matrix B=(bij)N×N is the transpose of the adjacency matrix of the network, and bij means the weight of a directed edge from node j to node i. Q∈RN×M is the input matrix (control matrix), and u=(u1,u2,…,uM)T∈RM(M⩽N) is the input or control vector. Based on Kalman’s controllability rank condition [22], linear system (1) can be controlled from any initial state to any desired state in finite time if and only if it meets the following condition: (2)rank⁡Q,BQ,B2Q,…,BN-1Q=N.For large systems, using the above method is a formidable challenge. Recently, Liu et al. [20] studied network controllability revealing an interesting interplay between the structure and structural controllability of directed networks. In particular, they mapped the structural controllability of a directed network into the maximum matching problem as Lemma 6 mentioned below and pointed out that the unmatched nodes are needed to control to achieve full control of the entire network. Thus it can be seen that they have dealt with the problem of network controllability intensively and tactfully. Moreover, Yuan et al. [21], based on the maximum multiplicity, provided another interesting paradigm to identify driver nodes required to achieve full control of arbitrary network structures as described in Lemma 7.Lemma 6 (minimum input theorem [20]).
The minimum number of inputs(NI) or identically the minimum number of driver nodes (ND) needed to fully control a network GD is given by (3)NI=ND=max⁡N-MD∗,1.Lemma 7 (largest geometric multiplicity theorem [21]).
Assuming thatB with l distinct eigenvalues has been determined, for a digraph, the minimum number of driver nodes ND is determined by the largest geometric multiplicity μ(λi) of the eigenvalue λi of B; that is, (4)ND=maxi⁡μλi,where μ(λi)=dim⁡Vλi=N-rank(λiIN-B), λi, i=1,2,…,l, represent the distinct eigenvalues of B, and IN is the unit matrix with the same order as B.A condition for finding maximum matchings of a digraph is now established.Theorem 8 (maximum matchings of a digraph based on largest geometric multiplicity).
Suppose thatB has eigenvalues λi with geometric multiplicity μi(λi), i=1,2,…,l, and λm is the eigenvalue associated with the largest geometric multiplicity μ(λm). Let matrix B′ be the column canonical form of matrix λmIN-B. Then, the linearly dependent rows in B′ are associated with the unmatched nodes, and the linearly independent rows are associated with the matched nodes.Proof.
If LTI dynamics (1) is controllable, then according to the PBH (Popov-Belevitch-Hautus) theorem [23], we can obtain (5)rank⁡λiIN-B,Q=N.
By the property of rank inequalities, it is easy to obtain(6)N=rank⁡λiIN-B,Q⩽rank⁡λiIN-B+rank⁡Q. Then (7)rankQ⩾N-rank⁡λiIN-B. When the equality holds, LTI dynamics (1) is controllable. It implies that (8)rankQ=maxi⁡N-rank⁡λiIN-B.Also, ND=rank(Q). Then(9)ND=maxiN-rank⁡λiIN-B.
Lety=P-1x and S=P-1Q, according to nonsingular transformation; then LTI dynamics (1) is equivalently changed to the following:(10)y˙=Jy+Su,where J is the Jordan matrix. Systems (1) and (10) have the same controllability properties, that is, for arbitrarily eigenvalues λi of matrix B, and rank(λiIN-B,Q) is the same as rank⁡(λiIN-J,S), and rank⁡(Q)=rank⁡(S). To facilitate explanation, set N=9. Suppose we take the Jordan block matrix J as(11)J=λ1000000000λ2100000000λ2000000000λ2000000000λ3100000000λ3100000000λ3000000000λ3000000000λ39×9,where each missing entry is zero. Here, μ(λ1)=1, μ(λ2)=2, and μ(λ3)=3. For λ1, in matrix λ1IN-J there is one zero column which is column 1. For λ2, in matrix λ2IN-J there are two zero columns which are columns 2 and 4. Similar to the case of λ2, for λ3, matrix λ3IN-J has three zero columns which are columns 5, 8, and 9. Therefore, we can draw the conclusion that the number of zero columns for an eigenvalue λi is exactly the geometric multiplicity μ(λi). Hence, λiIN-B has μ(λi) zero columns and N-μ(λi) linearly independent columns. This implies that(12)rank⁡λiIN-B=N-μλi.Combining (9) and (12), it follows that (13)ND=maxi⁡N-rank⁡λiIN-B=maxi⁡μλi.That is, ND is the number of the linearly dependent rows of the matrix λmIN-B. These linearly dependent rows are associated with the driver nodes.
On the other hand, by Lemma6 we conclude that ND is the number of unmatched nodes with respect to any maximum matchings. These unmatched nodes are just the driver nodes. It is not difficult to see that these matched nodes are associated with the rows which are linearly independent on other rows in B′.
Thus, the rows of the matrixλmIN-B, which are linearly dependent, are associated with the driver nodes needed to be controlled to maintain full control. It means that the number of the matched nodes is N-maxi⁡{μ(λi)}. The proof is thus completed.Obviously, the nodes corresponding to the linearly independent rows are matched nodes with numericalrank⁡(λmIN-B), which is the largest geometric multiplicity μ(λm). More precisely, the nodes corresponding to all the linearly independent rows are matched nodes of a maximum matching. In fact, we can perform fundamental column transformations on λmIN-B and obtain its column canonical form B′, which reveals the linearly dependent rows. The linearly dependent rows in B′ correspond to the unmatched nodes. And those linearly independent rows correspond to the matched nodes. Next, we proceed to a method for seeking maximum matchings in a digraph.


### 3.2. The Algorithm Steps

A maximum matching of a digraph consists of matched nodes and matching edges. This section describes how to find the matched nodes and the matching edges, respectively.First, for a given digraphGD, the algorithm steps based on largest geometric multiplicity to identify matched nodes of a maximum matching are described as follows.Algorithm for Identifying Matched Nodes of a Maximum MatchingStep 1.
Compute the eigenvaluesλi of the matrix B and find their geometric multiplicity μ(λi), i=1,2,…,l.Step 2.
Find the eigenvalueλm associated with the largest geometric multiplicity μ(λm).Step 3.
Perform some fundamental column transformations onλmIN-B and get its column canonical form B′.Step 4.
Find linearly independent rows inB′.Step 5.
The linearly independent rows correspond to the matched nodes of a maximum matching.It should be noted that the set of matched nodes of maximum matchings is not unique, since it is related to the order of implementing the fundamental transformations. Generally speaking, there are some candidates of linearly independent rows. Nevertheless, the number of matched nodes of these maximum matchings is the same and it depends on the largest geometric multiplicityμ(λm).Once the matched nodes are identified, the maximum matching edges can be obtained through the following steps. To describe for convenience, assume the maximum matched nodes to be nodes 1, 2, and 3,{1,2,3} for short.Algorithm for Identifying Matching Edges of a Maximum MatchingStep 1.
Construct a new matrixCN×m by the following expression: (14)CN×m=b1b2b3T, where bi=[b1ib2i⋯bNi], i=1,2,3, and m is the number of the matched nodes, with m=3. These columns are extracted from the matrix B, which are maximum matched nodes corresponding to the columns of the matrix B.Step 2.
Find the columnbi which contains the least amount of 1. If it is more than one, we can arbitrarily choose one. For simplicity, assume bi=b1, where bj1=1. The edge e=(j,1) is the matching edge corresponding to the matching node 1.Step 3.
Letbji=0, i=2,3, and get a matrix C1N×m.Step 4.
In the matrixC1N×m, consider the rest of the column bj(bj≠bi) and repeat Steps 2 and 3.Step 5.
In the end, make the nonzero elements in different rows and columns. The edges corresponding to these nonzero elements are just matching edges. In this way, we can find all matching edges corresponding to the matched nodes.To determine matched nodes by using the fundamental column transformations, we adopt the elimination method with the computation complexityO(N2(log⁡N)2).


## 3.1. The Theoretical Basis

First, two conditions of controllability of complex networks are reviewed.Consider a linear time-invariant (LTI) dynamics (1) on a directed network or digraph GD,(1)x˙=Bx+Qu,where x=(x1,x2,…,xN)T∈RN is called the state vector, the state matrix B=(bij)N×N is the transpose of the adjacency matrix of the network, and bij means the weight of a directed edge from node j to node i. Q∈RN×M is the input matrix (control matrix), and u=(u1,u2,…,uM)T∈RM(M⩽N) is the input or control vector. Based on Kalman’s controllability rank condition [22], linear system (1) can be controlled from any initial state to any desired state in finite time if and only if it meets the following condition: (2)rank⁡Q,BQ,B2Q,…,BN-1Q=N.For large systems, using the above method is a formidable challenge. Recently, Liu et al. [20] studied network controllability revealing an interesting interplay between the structure and structural controllability of directed networks. In particular, they mapped the structural controllability of a directed network into the maximum matching problem as Lemma 6 mentioned below and pointed out that the unmatched nodes are needed to control to achieve full control of the entire network. Thus it can be seen that they have dealt with the problem of network controllability intensively and tactfully. Moreover, Yuan et al. [21], based on the maximum multiplicity, provided another interesting paradigm to identify driver nodes required to achieve full control of arbitrary network structures as described in Lemma 7.Lemma 6 (minimum input theorem [20]).
The minimum number of inputs(NI) or identically the minimum number of driver nodes (ND) needed to fully control a network GD is given by (3)NI=ND=max⁡N-MD∗,1.Lemma 7 (largest geometric multiplicity theorem [21]).
Assuming thatB with l distinct eigenvalues has been determined, for a digraph, the minimum number of driver nodes ND is determined by the largest geometric multiplicity μ(λi) of the eigenvalue λi of B; that is, (4)ND=maxi⁡μλi,where μ(λi)=dim⁡Vλi=N-rank(λiIN-B), λi, i=1,2,…,l, represent the distinct eigenvalues of B, and IN is the unit matrix with the same order as B.A condition for finding maximum matchings of a digraph is now established.Theorem 8 (maximum matchings of a digraph based on largest geometric multiplicity).
Suppose thatB has eigenvalues λi with geometric multiplicity μi(λi), i=1,2,…,l, and λm is the eigenvalue associated with the largest geometric multiplicity μ(λm). Let matrix B′ be the column canonical form of matrix λmIN-B. Then, the linearly dependent rows in B′ are associated with the unmatched nodes, and the linearly independent rows are associated with the matched nodes.Proof.
If LTI dynamics (1) is controllable, then according to the PBH (Popov-Belevitch-Hautus) theorem [23], we can obtain (5)rank⁡λiIN-B,Q=N.
By the property of rank inequalities, it is easy to obtain(6)N=rank⁡λiIN-B,Q⩽rank⁡λiIN-B+rank⁡Q. Then (7)rankQ⩾N-rank⁡λiIN-B. When the equality holds, LTI dynamics (1) is controllable. It implies that (8)rankQ=maxi⁡N-rank⁡λiIN-B.Also, ND=rank(Q). Then(9)ND=maxiN-rank⁡λiIN-B.
Lety=P-1x and S=P-1Q, according to nonsingular transformation; then LTI dynamics (1) is equivalently changed to the following:(10)y˙=Jy+Su,where J is the Jordan matrix. Systems (1) and (10) have the same controllability properties, that is, for arbitrarily eigenvalues λi of matrix B, and rank(λiIN-B,Q) is the same as rank⁡(λiIN-J,S), and rank⁡(Q)=rank⁡(S). To facilitate explanation, set N=9. Suppose we take the Jordan block matrix J as(11)J=λ1000000000λ2100000000λ2000000000λ2000000000λ3100000000λ3100000000λ3000000000λ3000000000λ39×9,where each missing entry is zero. Here, μ(λ1)=1, μ(λ2)=2, and μ(λ3)=3. For λ1, in matrix λ1IN-J there is one zero column which is column 1. For λ2, in matrix λ2IN-J there are two zero columns which are columns 2 and 4. Similar to the case of λ2, for λ3, matrix λ3IN-J has three zero columns which are columns 5, 8, and 9. Therefore, we can draw the conclusion that the number of zero columns for an eigenvalue λi is exactly the geometric multiplicity μ(λi). Hence, λiIN-B has μ(λi) zero columns and N-μ(λi) linearly independent columns. This implies that(12)rank⁡λiIN-B=N-μλi.Combining (9) and (12), it follows that (13)ND=maxi⁡N-rank⁡λiIN-B=maxi⁡μλi.That is, ND is the number of the linearly dependent rows of the matrix λmIN-B. These linearly dependent rows are associated with the driver nodes.
On the other hand, by Lemma6 we conclude that ND is the number of unmatched nodes with respect to any maximum matchings. These unmatched nodes are just the driver nodes. It is not difficult to see that these matched nodes are associated with the rows which are linearly independent on other rows in B′.
Thus, the rows of the matrixλmIN-B, which are linearly dependent, are associated with the driver nodes needed to be controlled to maintain full control. It means that the number of the matched nodes is N-maxi⁡{μ(λi)}. The proof is thus completed.Obviously, the nodes corresponding to the linearly independent rows are matched nodes with numericalrank⁡(λmIN-B), which is the largest geometric multiplicity μ(λm). More precisely, the nodes corresponding to all the linearly independent rows are matched nodes of a maximum matching. In fact, we can perform fundamental column transformations on λmIN-B and obtain its column canonical form B′, which reveals the linearly dependent rows. The linearly dependent rows in B′ correspond to the unmatched nodes. And those linearly independent rows correspond to the matched nodes. Next, we proceed to a method for seeking maximum matchings in a digraph.


## 3.2. The Algorithm Steps

A maximum matching of a digraph consists of matched nodes and matching edges. This section describes how to find the matched nodes and the matching edges, respectively.First, for a given digraphGD, the algorithm steps based on largest geometric multiplicity to identify matched nodes of a maximum matching are described as follows.Algorithm for Identifying Matched Nodes of a Maximum MatchingStep 1.
Compute the eigenvaluesλi of the matrix B and find their geometric multiplicity μ(λi), i=1,2,…,l.Step 2.
Find the eigenvalueλm associated with the largest geometric multiplicity μ(λm).Step 3.
Perform some fundamental column transformations onλmIN-B and get its column canonical form B′.Step 4.
Find linearly independent rows inB′.Step 5.
The linearly independent rows correspond to the matched nodes of a maximum matching.It should be noted that the set of matched nodes of maximum matchings is not unique, since it is related to the order of implementing the fundamental transformations. Generally speaking, there are some candidates of linearly independent rows. Nevertheless, the number of matched nodes of these maximum matchings is the same and it depends on the largest geometric multiplicityμ(λm).Once the matched nodes are identified, the maximum matching edges can be obtained through the following steps. To describe for convenience, assume the maximum matched nodes to be nodes 1, 2, and 3,{1,2,3} for short.Algorithm for Identifying Matching Edges of a Maximum MatchingStep 1.
Construct a new matrixCN×m by the following expression: (14)CN×m=b1b2b3T, where bi=[b1ib2i⋯bNi], i=1,2,3, and m is the number of the matched nodes, with m=3. These columns are extracted from the matrix B, which are maximum matched nodes corresponding to the columns of the matrix B.Step 2.
Find the columnbi which contains the least amount of 1. If it is more than one, we can arbitrarily choose one. For simplicity, assume bi=b1, where bj1=1. The edge e=(j,1) is the matching edge corresponding to the matching node 1.Step 3.
Letbji=0, i=2,3, and get a matrix C1N×m.Step 4.
In the matrixC1N×m, consider the rest of the column bj(bj≠bi) and repeat Steps 2 and 3.Step 5.
In the end, make the nonzero elements in different rows and columns. The edges corresponding to these nonzero elements are just matching edges. In this way, we can find all matching edges corresponding to the matched nodes.To determine matched nodes by using the fundamental column transformations, we adopt the elimination method with the computation complexityO(N2(log⁡N)2).


## 4. Example

To illustrate the method explicitly, we present a simple example, as shown in Figure3. The digraph GD is illustrated in Figure 3(a); V={1,2,3,4,5,6}, E={(1,2),(1,3),(1,4),(1,5),(1,6),(4,3),(6,5)}. The transpose of the adjacency matrix, denoted by B, is as follows:(15)B=node123456011111000000000000001000000000000010.Figure 3
A digraph and its maximum matchings. (a) A digraph with six nodes and seven edges. The digraph has three kinds of maximum matchings shown by (b)–(d). In (b)–(d), matched (unmatched) nodes are shown in green (black), respectively. Similarly, matching (unmatching) edges are shown in red (black), respectively.
(a)
(b)
(c)
(d)It is not difficult to obtain eigenvalueλm=0 and μ(λm)=3. Here, λm is the eigenvalue associated with the largest geometric multiplicity μ(λm). Then compute the matrix λmIN-B and perform some fundamental column transformations on it to obtain its column canonical form B′ as follows:(16)B′=node123456010101001000000010000000000000000000.In the column canonical form B′, the 3rd row and 5th row must be chosen and another row should be chosen from the 2nd, 4th, and 6th rows. Thus we totally have three different combinations of matched nodes as indicated in Figures 3(b)–3(d). Each set of options results in a distinct configuration of the set of matched nodes. But the number of matched nodes is fixed. Here we have enumerated all possible combinations of maximum matchings, respectively, {2,3,5}, {3,4,5}, and {3,5,6}. These configurations of maximum matching are indeed exactly the same as the results by using the popular classic method.With{2,3,5}, for example, we find the maximum matching edges. Construct a new matrix CN×m and find the column b2 with b12=1 which contains the least amount of 1. The edge e=(1,2) is the matching edge corresponding to the matched node 1. Set b13=0 and b15=0. Then we get the matrix C1N×m. Similarly, for the rest of columns b3 and b5, repeat Steps 2 and 3 in the matrix C1N×m. Further, we get the matching edges e=(4,3) and e=(6,5). So the matching edges are e=(1,2), e=(4,3), and e=(6,5) corresponding to the matched nodes 2, 3, and 5. In the same way, the matching edges are e=(4,3), e=(1,4), and e=(6,5) corresponding to the matched nodes 3, 4, and 5. Likewise, the matching edges are e=(4,3), e=(6,5), and e=(1,6) corresponding to the matched nodes 3, 5, and 6. Consider (17)CN×m=b2b3b5T=235100000100100100001,C1N×m=2351_000000001_00000001_.Two observations are given here for special cases.When a digraph is a directed circle shown in Figure4, the transpose of the adjacency matrix B1 is shown in the following: (18)B1=0000110000010000010000010.Figure 4
A directed circle and its maximum matching (perfect matching). (a) is the original directed cycle. The directed cycle has perfect matching as shown in (b). In (b), all nodes are matched. Matched nodes are displayed in green. Similarly, matching edges are displayed in red.
(a)
(b)In this case, each eigenvalue ofB1 has geometric multiplicity exactly 1, and each row in B1 is linearly independent. Therefore, each node is matched. All nodes constitute a perfect matching.For an arbitrary digraph, it is difficult to make a statement about the largest multiplicity and digraph structure. However, for sparse digraphs (weighted or unweighted), the eigenvalue 0 corresponds to the largest geometric multiplicity. In other words, the zero eigenvalue dominates the eigenvalue spectrum. In this case, the nodes corresponding to the linearly independent rows are matched nodes with numericalrank⁡(λmIN-B)=rank⁡-B=rank⁡(B). Thereby, the number of matched nodes can be obtained by solving the rank of B. For instance, the transpose of adjacency matrix of a sparse digraph is shown as follows: (19)B2=0000000110000000000100000000001001000100000100100010000000010000. Its eigenvalue corresponding to the largest geometric multiplicity is zero. Thus the number of matched nodes MD∗=rank⁡(B2)=6. To summarize, in a sparse digraph the number of matched nodes is closely associated with the rank of its structure matrix. It also reveals the underlying relationship between the structure of a digraph and its maximum matchings.


## 5. Conclusion and Future Work

The paper constructed and proved one sufficient condition of matched nodes in a digraph, together with a new and practical method to find maximum matchings of a digraph. Maximum matchings in a digraph problem with largest geometric multiplicity of the eigenvalues are also investigated. It has shown how to find the maximum matched nodes and matching edges in general digraphs. From the experimental results, we observe that the method is effective. The key in our approach lies in bridging the largest geometric multiplicity and the matching theory.Developing and exploring other matching theory algorithms in a digraph would be a challenging job in further research. In the future, we will address this problem more systematically. In addition, the extension of this study to the case of undirected graphs is also an interesting problem.



---

*Source: 4702387-2016-04-28.xml*