Study On The Matching Number Of The Two Kinds Of Directed Graphs

With the increasingly powerful of computing devices and rapid development of Internet, we can collect and deal with different kinds and large scale of actual networks data. And by some measures we want to control effectively the complex networks such that it make advantageous to people’s production and life. 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 significance.This article mainly studies the counting problems and the extremal problems on the number of matchings in directed trees and a class of directed triangle trees. First of all, this paper introduces the research background of complex networks, controllability of the complex networks and the matching number of networks. The second chapter introduces some basic knowledge about undirected graphs, directed graphs and directed trees. The third chapter in this paper, we investigate the calculation method of the matching number of directed trees with n nodes. The expression of the matching number and its related properties are given and a algorithm are presented. The fourth chapter, we investigate the counting problems and the extremal problems for the number of matchings in a class of directed triangle trees with n triangles. We give a algorithm for the matching number of directed triangle trees and determine the bounds for the matching number of directed triangle trees with n triangles and the correspond graphs. The last chapter summarizes this paper, and some problems remaining to be solved are given.