Printer Friendly

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

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. Section 2 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.

Let [G.sub.D] 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 [G.sub.D] = (V, E). The size of [G.sub.D] is the number of nodes in [G.sub.D], denoted by [absolute value of ([G.sub.D])] = 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)}.

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 matrix A with the eigenvalue [lambda], the dimension of the eigenspace of A corresponding to the eigenvalue [lambda] is called the geometric multiplicity of the eigenvalue [lambda].

Notice that the geometric multiplicity is the largest number of linearly independent eigenvectors associated with an eigenvalue.

Definition 2. For an undirected graph, a matching M 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 matching [M.sup.*] is a matching of maximum-cardinality among all matchings. A maximum matching [M.sup.*] 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, matching [M.sub.D] is a subset of edges with no common starting-nodes or no common endingnodes. That is to say, no two edges in [M.sub.D] 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 maximumcardinality is called a maximum matching, symbolized by [M.sup.*.sub.D]. A maximum matching [M.sup.*.sub.D] is called perfect if all nodes in the digraph are matched.

Denote [absolute value of ([M.sup.*.sub.D])] as the size of the maximum matching [M.sup.*.sub.D] in [G.sub.D]. It is found that if maximum matching [M.sup.*] is perfect, then [absolute value of ([M.sup.*.sub.D])] = N, where N means the number of nodes in [G.sub.D].

For the maximum matching of a digraph, a simple algorithm based on bipartite graph is described below. A bipartite graph is defined as F(V) = [V.sup.+] [union] [V.sup.-], [GAMMA]). Here, [V.sup.+] = {[v.sup.+.sub.1], [v.sup.+.sub.2], ..., [v.sup.+.sub.N] } and = {[v.sup.-.sub.1], [v.sup.-.sub.2], ..., [v.sup.-.sub.N]} are the sets of nodes corresponding to the N nodes in [G.sub.D], respectively. Edge set [GAMMA] = {([v.sup.+.sub.i], [v.sup.-.sub.j]) | [e.sub.ij] [not equal to] 0}. See Figure 2. First, we split each node v into two nodes [v.sup.+.sub.i] and [v.sup.-.sub.i] to make a digraph [G.sub.D] transform to its bipartite graph representation F(V). Then we connect an edge between nodes [v.sup.+.sub.i] and [v.sup.-.sub.j] in F(V) if there is an edge [e.sup.i.sub.j] in [G.sub.D]. 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.

A maximum matching in [G.sub.D] contains the maximum possible number of nodes in [GAMMA]. 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 [G.sub.D],

[??] = Bx + Qu, (1)

where x = [([x.sub.1], [x.sub.2], ..., [x.sub.N]).sup.T] [member of] [R.sup.N] is called the state vector, the state matrix B = [([b.sub.ij]).sub.NxN] is the transpose of the adjacency matrix of the network, and [b.sub.ij] means the weight of a directed edge from node j to node i. Q [member of] [R.sup.NxM] is the input matrix (control matrix), and u = [([u.sub.1], [u.sub.2], ..., [u.sub.M]).sup.T] [member of] [R.sup.M] (M [less than or equal to] 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:

rank [Q, BQ, [B.sup.2]Q, ..., [B.sup.N-1] Q] = N. (2)

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 ([N.sub.I]) or identically the minimum number of driver nodes ([N.sub.D]) needed to fully control a network [G.sub.D] is given by

[N.sub.1] = [N.sub.D] = max {N-[absolute value of ([M.sup.*.sub.D])], 1}. (3)

Lemma 7 (largest geometric multiplicity theorem [21]). Assuming that B with I distinct eigenvalues has been determined, for a digraph, the minimum number of driver nodes ND is determined by the largest geometric multiplicity [mu]([[lambda].sub.i]) of the eigenvalue [[lambda].sub.i] of B; that is,

[mathematical expression not reproducible] (4)

where [[mathematical expression not reproducible], represent the distinct eigenvalues of B, and [I.sub.N] 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 that B has eigenvalues [[lambda].sub.i] with geometric multiplicity [[mu].sub.i]([[lambda].sub.i]), i = 1, 2, ..., I, and [[lambda].sub.m] is the eigenvalue associated with the largest geometric multiplicity [mu]([[lambda].sub.m]). Let matrix B' be the column canonical form of matrix [[lambda].sub.m][I.sub.N] - 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

rank [[[lambda].sub.i][I.sub.N] - B, Q] = N. (5)

By the property of rank inequalities, it is easy to obtain

N = rank [[[lambda].sub.i][I.sub.N] - B, Q] (6)

[less than or equal to] rank ([[lambda].sub.i][I.sub.N] - B) + rank (Q).


rank (Q) [greater than or equal to] N - rank ([[lambda].sub.i][I.sub.N] - B). (7)

When the equality holds, LTI dynamics (1) is controllable. It implies that

[mathematical expression not reproducible] (8)

Also, [N.sub.D] = rank(Q). Then

[mathematical expression not reproducible] (9)

Let y = [P.sup.-1] x and S = [P.sup.-1] Q, according to nonsingular transformation; then LTI dynamics (1) is equivalently changed to the following:

[??] = Jy + Su, (10)

where J is the Jordan matrix. Systems (1) and (10) have the same controllability properties, that is, for arbitrarily eigenvalues [[lambda].sub.i] of matrix B, and rank([[lambda].sub.i][I.sub.N] - B, Q) is the same as rank([lambda].sub.i][I.sub.N] - J, S), and rank(Q) = rank(S). To facilitate explanation, set N = 9. Suppose we take the Jordan block matrix J as

[mathematical expression not reproducible], (11)

where each missing entry is zero. Here, [mu]([[lambda].sub.1]) = 1, [mu]([[lambda].sub.2]) = 2, and [mu]([[lambda].sub.3]) = 3. For [[lambda].sub.1], in matrix [[lambda].sub.i][I.sub.N] - J there is one zero column which is column 1. For [[lambda].sub.2], in matrix [[lambda].sub.2][I.sub.N] - J there are two zero columns which are columns 2 and 4. Similar to the case of [[lambda].sub.2], for [[lambda].sub.3], matrix [[lambda].sub.3][I.sub.N] - 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 A; is exactly the geometric multiplicity [mu]([[lambda].sub.i]). Hence, [[lambda].sub.i][I.sub.N] - B has [mu]([[lambda].sub.i]) zero columns and N - [mu]([[lambda].sub.i]) linearly independent columns. This implies that

rank ([[lambda].sub.i][I.sub.N] - B) = N - [mu]([[lambda].sub.i]). (12)

Combining (9) and (12), it follows that

[mathematical expression not reproducible] (13)

That is, [N.sub.D] is the number of the linearly dependent rows of the matrix [[lambda].sub.m][I.sub.N] - B. These linearly dependent rows are associated with the driver nodes.

On the other hand, by Lemma 6 we conclude that [N.sub.D] 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 [[lambda].sub.m][I.sub.N] - 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 - [max.sub.i]{[mu]([[lambda].sub.i])}. The proof is thus completed.

Obviously, the nodes corresponding to the linearly independent rows are matched nodes with numerical rank([[lambda].sub.m][I.sub.N] - B), which is the largest geometric multiplicity [mu]([[lambda].sub.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 [[lambda].sub.m][I.sub.N] - 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 digraph [G.sub.D], 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 Matching

Step 1. Compute the eigenvalues [[lambda].sub.i] of the matrix B and find their geometric multiplicity [mu]([[lambda].sub.i]), i = 1, 2, ..., l.

Step 2. Find the eigenvalue [[lambda].sub.m] associated with the largest geometric multiplicity [mu]([[lambda].sub.m]).

Step 3. Perform some fundamental column transformations on [[lambda].sub.m][I.sub.N] - B and get its column canonical form B'.

Step 4. Find linearly independent rows in B'.

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 [mu]([[lambda].sub.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 Matching

Step 1. Construct a new matrix [C.sub.Nxm] by the following expression:

[mathematical expression not reproducible] (14)

where [b.sub.i] = [[] [b.sub.2i] ... [b.sub.Ni]], 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 column [b.sub.i] which contains the least amount of 1. If it is more than one, we can arbitrarily choose one. For simplicity, assume [b.sub.i] = [b.sub.1], where [b.sub.j1] = 1. The edge e = (j, 1) is the matching edge corresponding to the matching node 1.

Step 3. Let [b.sub.ji] = 0, i = 2,3, and get a matrix [C1.sub.Nxm.]

Step 4. In the matrix [C1.sub.Nxm], consider the rest of the column [b.sub.j] ([b.sub.j] [not equal to] [b.sub.i]) 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 complexity O([N.sup.2] [(logN).sup.2]).

4. Example

To illustrate the method explicitly, we present a simple example, as shown in Figure 3. The digraph [G.sub.D] 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:

[mathematical expression not reproducible] (15)

It is not difficult to obtain eigenvalue [[lambda].sub.m] = 0 and [mu]([[lambda].sub.m]) = 3. Here, [[lambda].sub.m] is the eigenvalue associated with the largest geometric multiplicity [mu]([[lambda].sub.m]). Then compute the matrix [[lambda].sub.m][I.sub.N] - B and perform some fundamental column transformations on it to obtain its column canonical form B' as follows:

[mathematical expression not reproducible] (16)

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 [C.sub.Nxm] and find the column [b.sub.2] with [b.sub.12] =1 which contains the least amount of 1. The edge e = (1, 2) is the matching edge corresponding to the matched node 1. Set [b.sub.13] = 0 and [b.sub.15] = 0. Then we get the matrix [C1.sub.Nxm]. Similarly, for the rest of columns [b.sub.3] and [b.sub.5], repeat Steps 2 and 3 in the matrix [C1.sub.Nxm.] Further, we get the matching edges e = (4, 3) and e = (6, 5). So the matching edges are e = (1, 2), e = (4, 3),ande = (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),ande = (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

[mathematical expression not reproducible] (17)

Two observations are given here for special cases.

When a digraph is a directed circle shown in Figure 4, the transpose of the adjacency matrix [B.sub.1] is shown in the following:

[mathematical expression not reproducible] (18)

In this case, each eigenvalue of [B.sub.1] has geometric multiplicity exactly 1, and each row in [B.sub.1] 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 numerical rank ([[lambda].sub.m][I.sub.N] -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:

[mathematical expression not reproducible] (19)

Its eigenvalue corresponding to the largest geometric multiplicity is zero. Thus the number of matched nodes [absolute value of ([M.sup.*.sub.D])] = rank([B.sub.2]) = 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.

Competing Interests

The authors declare that they have no competing interests.


This work was supported by Innovation Foundations of Education for Graduate Students of Shanxi Province (Grant no. 2016BY83), the Fund Project of Taiyuan City Science and Technology Special Talents (Grant no. 120247-28), and the National Natural Science Foundation of China (Grant no. 61402319). The authors thank Z. M. Gao for his valuable comments and useful feedback on the paper. Finally, they particularly thank Y. P. Liang with expertise in technical English editing for the English of this paper being improved.


[1] J. Bang-Jensen and G. Z. Gutin, Digraphs: Theory, Algorithms and Applications, Springer, New York, NY, USA, 2009.

[2] R. C. Read, Graph Theory and Computing, Academic Press, New York, NY, USA, 2014.

[3] Z. B. Xiong and J. F. Zhu, "Forward maximum matching algorithm based on improved trie tree structure," Computer Applications and Software, vol. 5, article 71, 2014.

[4] A. A. Schaffer, "Optimal node ranking of trees in linear time," Information Processing Letters, vol. 33, no. 2, pp. 91-96, 1989.

[5] H. L. Bodlaender, J. S. Deogun, K. Jansen et al., "Rankings of graphs," SIAM Journal on Discrete Mathematics, vol. 11, no. 1, pp. 168-181, 1998.

[6] W. Woess, Random Walks on Infinite Graphs and Groups, vol. 138, Cambridge University Press, New York, NY, USA, 2000.

[7] R. E. Burkard, M. Dell'Amico, and S. Martello, Assignment Problems, SIAM, 2009.

[8] J. Edmonds and R. M. Karp, "Theoretical improvements in algorithmic efficiency for network flow problems," Journal of the ACM, vol. 19, no. 2, pp. 248-264, 1972.

[9] H. B. Li and J. G. Zhai, "A fast dynamic optimum algorithm for maximum matching in bipartite graphs," Ludong University Journal (Natural Science Edition), vol. 22, no. 3, pp. 168-170, 2006.

[10] F. Carrabs, R. Cerulli, and M. Gentili, "The labeled maximum matching problem," Computers & Operations Research, vol 36, no. 6, pp. 1859-1871, 2009.

[11] J. Li and S. Y. Wang, "An algorithm for constructing the maximum matching graphs on bigraphs," Acta Electronica Sinica, vol 38, no. 1, pp. 161-166, 2011.

[12] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, UK, 1985.

[13] M. Tang, J. Guan, G. Q. Deng, and H. G. Wang, "A new algorithm and application of solving maximum matching problem of bipartite graph," Computer Systems & Applications, vol. 21, no. 3, pp. 72-75, 2012.

[14] T. Oncan, R. N. Zhang, and A. P. Punnen, "The minimum cost perfect matching problem with conflict pair constraints," Computers & Operations Research, vol. 40, no. 4, pp. 920-930, 2013.

[15] E. Dobson, I. Kovacs, and S. Miklavic, "The isomorphism problem for rose window graphs," Discrete Mathematics, vol. 323, pp. 7-13, 2014.

[16] W. Li and A. Chang, "The minimal Laplacian spectral radius of trees with given matching number," Linear and Multilinear Algebra, vol. 62, no. 2, pp. 218-228, 2014.

[17] M. A. Duarte, F. Joos, L. D. Penso, D. Rautenbach, and U. S. Souza, "Maximum induced matchings close to maximum matchings," Theoretical Computer Science, vol. 588, pp. 131-137, 2015.

[18] G. Even, M. Medina, and D. Ron, "Distributed maximum matching in bounded degree graphs," in Proceedings of the 2015 International Conference on Distributed Computing and Networking (ICDCN '15), p. 18, ACM, Singapore, January 2015.

[19] A. Azad and A. Buluc, "Distributed-memory algorithms for maximal cardinality matching using matrix algebra," in Proceedings of the IEEE International Conference on Cluster Computing (CLUSTER '15), pp. 398-407, IEEE, Chicago, 1ll, USA, September 2015.

[20] Y.-Y. Liu, J.-J. Slotine, and A.-L. Barabasi, "Controllability of complex networks," Nature, vol. 473, no. 7346, pp. 167-173, 2011.

[21] Z. Z. Yuan, C. Zhao, Z. R. Di, W.-X. Wang, and Y.-C. Lai, "Exact controllability of complex networks," Nature Communications, vol. 4, article 2447, 2013.

[22] R. E. Kalman, "Mathematical description of linear dynamical systems," Journal of the Society for Industrial and Applied Mathematics, Series A: Control, vol. 1, no. 2, pp. 152-192, 1963.

[23] M. L. J. Hautus, "Controllability and observability conditions of linear autonomous systems," Proceedings of the Koninklijke Nederlandse Akademie Van Wetenschappen Series A--Mathematical Sciences, vol. 72, no. 5, pp. 443-448, 1969.

Yunyun Yang and Gang Xie

College of Information Engineering, Taiyuan University of Technology, Taiyuan, Shanxi 030024, China

Correspondence should be addressed to Gang Xie;

Received 6 December 2015; Accepted 10 April 2016

Academic Editor: Zhike Peng

Caption: FIGURE 1: A digraph with six nodes and six edges.

Caption: 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.

Caption: 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.

Caption: 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.
COPYRIGHT 2016 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Yang, Yunyun; Xie, Gang
Publication:Mathematical Problems in Engineering
Date:Jan 1, 2016
Previous Article:Optimal Choices for the E-Tailer with Inventory Rationing, Hybrid Channel Strategies, and Service Level Constraint under Multiperiod Environments.
Next Article:Maneuvering Target Detection Based on JRC System in Gaussian and Non-Gaussian Clutter.

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters