（湖南工业大学 理学院，湖南 株洲 412007）

0 引言

在实际应用当中，只要是描述两个事物之间的关系，均能够将其抽象概括为图论中的模型。有关图的生成树数目问题，涉及多个领域且极具实践应用价值，从而是图论研究中十分活跃的课题之一。例如，在网络系统的应用中，图（网络）生成树的数目是评估图可靠性的一个重要指标。对于一个通信网络而言，其可靠性主要由生成树的个数决定。因此，在网络可靠性的研究中，人们十分关心一个图（网络）生成树的数目问题。研究图生成树的计数对网络的可靠性研究有着十分重要的现实价值。

计算一个图的生成树数目不是件容易的事情。文献[1]利用 Feussner 公式计算了一些特殊图类的生成树数目。文献[2]通过Cayley 公式求出了3 类特殊平面图的生成树数目，并且给出了它们的递推关系式及通项表达式。文献[3]通过引入收缩团，探讨了完全图的生成树数目问题，并利用归纳法得到了比Cayley 公式更一般的公式。文献[4]给出了上述公式的概率求法。文献[5]将图的生成树数目问题归结为其块图的生成树数目问题，从而提供了一种较简便的计算图生成树数目的方法。文献[6-9]利用平面图的对偶图的Kirchhoff 矩阵，求出了一些特殊图类的生成树数目。

1 预备知识

定义1包含图G所有顶点的子图称为图G的生成子图，若图G的一个生成子图T恰为一棵树，则称T是图G的一棵生成树。图G的生成树数目用τ(G) 表示[10]。

定义2设图G是一个平面图的平面嵌入，则G的对偶图G*定义为：对于平面图G的每个面f都有G*的顶点f*与之对应，对于G的每条边e都有G*的边e*与之对应，且G*中顶点与被e*连接，当且仅当G中的面f1与f2被边e所分隔[10]。……