有向三角形树的匹配数

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

随着以互联网[1]为代表的网络信息技术的飞速发展，人类社会已经逐步进入了复杂网络时代。钱学森给出了复杂网络[2]的一个较为严格的定义：具有自相似、无标度、自组织、小世界、吸引子中部分或全部性质的网络为复杂网络。如何利用复杂网络让人们的生活更加有效，成为了人们关注的焦点。基于此，一些学者开始研究复杂网络的可控性。如果我们想要控制一个系统，我们首先要确定一个顶点集， 通过在这些顶点集上输入不同的信号完全控制整个网络，我们称这些节点为驱动节点。我们特别有兴趣于：确定最小的驱动节点数[3]， 记为ND， 它可以有效地完全控制系统的动力学过程。

2011 年刘和Barabasi 等人[3]给出有向网络匹配的定义及最小输入定理：指出有向网络的可控节点数等于有向网络的顶点数减去最大匹配包含的边数，由此开启了研究复杂网络可控性的新篇章。

1971年日本化学家Haruo Hosoya [4]-[6]介绍了基于结构描述的分子图， 他命名了拓扑指标并记为Z。

他用下面的方式定义了Z 或Z(G)：从图G 中选择k 条相互独立的边的方法数记为m(G, k)， 对所有图m(G, 0) = 1，并且m(G, 1)等于图G 的边数，则： ( )()0, kZZ Gm G k≥== ∑ 称Z 或Z(G)为Hosoya 指标或Hosoya 拓扑指标。

本文中我们首先给出有向树、有向三角形树及有向三角形树匹配的概念，研究有向三角形树的匹配数及其相关性质。其次根据本文的主要内容给出计算一类有向三角形树匹配数的算法。

2. 基本知识 首先给出一些无向图、有向图及有向树的基本定义以及基本的符号表示。

2.1. 无向图的基本概念 一个图G = (V, E)是一个三元组[7]，这个三元组包含一个顶点集V(G)，一个边集E(G)和一个关系， 该关系使得每一条边和两个顶点(不一定是不同的点)相关联，并将这两个顶点称为这条边的端点。设边e