特殊圖類的生成樹數目

（湖南工業大學 理學院，湖南 株洲 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]。

定理1（矩陣樹定理）圖G的生成樹數目等于其Kirchhoff 矩陣K(G)的任何一個(n-1)級主子式的值，即τ(G)=detKr(G)。其中：K(G)=D(G)-A(G)，D(G)為度矩陣，A(G)為G的鄰接矩陣；Kr(G)為K(G)的任何一個(n-1)級主子陣[11]。

定理2設平面圖G的平面對偶圖為G*，則τ(G)=τ(G*)[11]。

2 主要結果與證明

定義3設P=u0u1u2…un和Q=v0v1v2…vn(n≥1)是兩條長度為n且頂點互不相交的路，則稱并圖為梯形圖，記為Ln。將3個兩兩互不相交的梯形圖分別與三角形的每條邊的兩端點相接，得到的圖稱為Y 形圖，如圖1所示，記為Yn。

圖1 Y 形圖Fig.1 Y-shaped graph

定義4設P=u0u1u2…unv和Q=v0v1v2…vnv（n≥1）是兩條終點相同，但起點以及內部頂點不交的路，則稱并圖為箭形圖，記為Sn。將4 個兩兩互不相交的箭形圖分別與四邊形每條邊的兩端點相接，得到的圖稱為十字形圖，如圖2所示，記為Tn。

圖2 十字形圖Fig.2 Cross graph

定理3對n≥1，有

證明根據圖Yn的特征可知，其對偶圖Y*n是有3n+2 個頂點的平面圖，且Y*n的Kirchhoff 矩陣為3n+2 階矩陣。對Y*n的頂點進行適當標號，使其對應的Kirchhoff 矩陣為

由定理1 知，圖Y*n的生成樹數目等于的3n+1 階順序主子式，即

其中yn=4yn-1-yn-2，且y1=4，y2=15。

遞推關系式yn- 4yn-1+yn-2=0 的特征多項式及其因子分解為

因此

將y1=4，y2=15 代入yn得

解得

因此

再由定理2 得

定理4對n≥1，有

證明根據圖Tn的特征可知，其對偶圖T*n是有4n+6 個頂點的平面圖，且T*n的Kirchhoff 矩陣為4n+6 階矩陣。對T*n的頂點進行適當標號，使其對應的Kirchhoff 矩陣為

由定理1 知，圖T*n的生成樹數目τ等于的4n+5 階順序主子式，即

將t1=3，t2=11 代入tn得

再由定理2 得

3 結語

從理論上說，可以利用Kirchhoff 矩陣樹定理來確定任何圖的生成樹數目，但是對于一個高階的一般圖，計算其Kirchhoff 矩陣的主子式相當困難。利用Kirchhoff 矩陣樹定理，結合平面圖的對偶圖對應的Kirchhoff 矩陣，本文的定理3 和定理4，給出了兩類具有一定對稱性的平面圖Yn和Tn的生成樹數目的通項公式，從而大大簡化了對生成樹數目的計算。