﻿ 有向三角形树的匹配数 On the Matching Number of Directed Triangle Trees

Computer Science and Application
Vol.06 No.05(2016), Article ID:17711,11 pages
10.12677/CSA.2016.65036

On the Matching Number of Directed Triangle Trees

Mengying Li, Haixing Zhao

Computer Department, QingHai Normal University, Xining Qinghai

Received: May 4th, 2016; accepted: May 27th, 2016; published: May 30th, 2016

Copyright © 2016 by authors and Hans Publishers Inc.

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.

Keywords:Complex Networks, Directed Tree, Directed Triangle Trees, Matching, Hosoya Index

1. 引言

1971年日本化学家Haruo Hosoya [4] - [6] 介绍了基于结构描述的分子图，他命名了拓扑指标并记为Z。他用下面的方式定义了Z或Z(G)：从图G中选择k条相互独立的边的方法数记为m(G, k)，对所有图m(G, 0) = 1，并且m(G, 1)等于图G的边数，则：

2. 基本知识

2.1. 无向图的基本概念

2.2. 有向图的基本概念

1) 有且仅有一个节点的入度为0；

2) 除树根外的节点的入度为1；

3) 从树根到任一节点有一条连通的有向路。

Figure 1. Directed tree G = (V; E)

3. 一类有向三角形树的匹配数

3.1. 有向树的基本定义

3.2. 有向三角形树的基本定义

Figure 2. Directed tree F

Figure 3. Directed triangle tree D3

3.3. 一类有向三角形树匹配数的计算方法

Figure 4. Directed triangle tree D

Figure 5. Directed graph D-v0

Figure 6. Directed graph D1, Directed graph D2

Figure 7. Directed tree Dv1, Directed tree Dv2, Directed graph D3

Figure 8. Directed graph D4, Directed graph D5

;

.

1) Dn-1的任意一个匹配和D1的任意一个匹配都没有公共始点和终点，注意到，此时有

2) Dn-1的某些匹配和D1的某些匹配有公共的始点，此时有

(2) 用数学归纳法证明左边不等式。设Dn可以在某一个具有n-1个三角形的有向三角形树图Dn-1的任意节点与新的节点v0粘贴得到，的中心与的v0粘结得到，其中的有向边为v0v1，v0v2，v1v2。类似(1)的证明考虑和Dn的匹配，分下面几种情况考虑：

a)的匹配由v1v2匹配组成，Dn的匹配由v1v2与Dn-1的匹配组成，根据归纳假设这种情形下

b)的匹配由v0v1，v0v2，v0v1v2分别与三角形的第三边生成的匹配组成，Dn的匹配由v0v1，v0v2，v0v1v2分别与Dn-1三角形的第三边生成的匹配组成，这种情形下他们匹配数相等。

c)的匹配只能是v0v1，v0v2，v0v1v2，或者是包含中心点v0的匹配，Dn的匹配由v0v1，v0v2，v0v1v2，或者Dn-1三角形的非第三边生成的匹配组成，或者由v0v1，v0v2，v0v1v2，和Dn-1中与v0不相交的Dn-1三角形的非第三边生成的匹配组成，这种情形下

Figure 9. Directed triangle star graph, Directed graph

Figure 10. Directed graph

3.4. 有向三角形树匹配数的算法

, ,

For each bottom up do

4. 结论与展望

On the Matching Number of Directed Triangle Trees[J]. 计算机科学与应用, 2016, 06(05): 292-302. http://dx.doi.org/10.12677/CSA.2016.65036

1. 1. 汪小帆, 李翔, 陈关荣. 网络科学导论[M]. 北京: 高等教育出版社, 2012.

2. 2. 郭世泽, 陆哲明. 复杂网络基础理论[M]. 北京: 科学出版社, 2012.

3. 3. Liu, Y.Y., Slotine, J.J. and Barabasi, A.L. (2011) Controllability of Complex Networks. Nature, 473, 167-173. http://dx.doi.org/10.1038/nature10011

4. 4. 陈关荣. 复杂动态网络环境下控制理论遇到的问题与挑战[J]. 自动化学报. 2013, 39(4): 312-321.

5. 5. Wagner, S. (2008) Extremal Trees with Respect to Hosoya Index and Merri-field-Simmons Index. MATCH Communications in Mathematical and in Computer Chemistry, 59, 203-216.

6. 6. Wagner, S. and Gutman, I. (2010) Maxima and Minima of the Hosoya Index and Merrifield-Simmons Index A Survey of Result and Techniques. Acta Applicandae Mathematicae, 112, 323-346. http://dx.doi.org/10.1007/s10440-010-9575-5

7. 7. West, D.B., 著. 图论导引[M]. 李建中, 骆吉洲, 译. 北京: 机械工业出版社, 2005.

8. 8. Jogen, B.J. and Gutin, G., 著. 有向图理论, 算法及其应用[M]. 姚兵, 张忠辅, 译. 北京: 科学出版社, 2009.

9. 9. 邓辉文. 离散数学[M]. 北京: 清华大学出版社, 2013.