有向三角形树的匹配数

On the Matching Number of Directed Triangle Trees

摘要: 有向图G的一个匹配是由其一组没有公共起点也没有公共终点的有向边构成的集合。图G的k匹配是指含k (k = 1, 2, …, n)条有向边的匹配；图G的k-匹配数是指含k (k = 1, 2, …, n)条有向边的匹配的选择方法数；图G的匹配数指所有k-匹配数的和。刘和Barabasi等人提出：有向网络的可控节点数等于有向网络的顶点数减去最大匹配包含的边数。说明有向网络的可控性与有向网络的匹配数有着密切的联系。因此，研究有向网络的所有匹配数目具有一定的应用意义。这篇文章主要研究一类有向三角形树的所有匹配数的计数问题和极值问题。给出了一类含n个三角形的有向三角形树匹配数的计算方法，以及有向三角形树匹配数的上下界和相应的结构。

Abstract: A matching of a directed graph G is a set of some directed edges without common starting-node and end-node. K-matching of a digraph G is the matching with the k (k = 1, 2,…, n) edges; k-matching number of a graph G is the number of distinct matchings containing k (k = 1, 2,…, n) edges. The matching of a graph G refers to the number of all k-matchings. Liu and Barabasi put forward: the number of controllable nodes in directed networks is equal to the number of nodes of directed networks minus the number of edges of the maximum matching. It illustrates that the matching number and controllability of directed networks have a close connection. Thus, the research of the number of all matchings of directed networks is of applied significance. This article mainly studies the counting problems and the extremal problems on the number of matchings in a class of directed triangle trees. We investigate the calculation method and the expression of the matching number in a class of directed triangle trees with n triangles and determine the bounds for the matching number in directed triangle trees with n triangles and the correspond graphs.