特殊圖類的生成樹數(shù)目

（湖南工業(yè)大學(xué) 理學(xué)院，湖南 株洲 412007）

0 引言

在實(shí)際應(yīng)用當(dāng)中，只要是描述兩個(gè)事物之間的關(guān)系，均能夠?qū)⑵涑橄蟾爬閳D論中的模型。有關(guān)圖的生成樹數(shù)目問題，涉及多個(gè)領(lǐng)域且極具實(shí)踐應(yīng)用價(jià)值，從而是圖論研究中十分活躍的課題之一。例如，在網(wǎng)絡(luò)系統(tǒng)的應(yīng)用中，圖（網(wǎng)絡(luò)）生成樹的數(shù)目是評(píng)估圖可靠性的一個(gè)重要指標(biāo)。對(duì)于一個(gè)通信網(wǎng)絡(luò)而言，其可靠性主要由生成樹的個(gè)數(shù)決定。因此，在網(wǎng)絡(luò)可靠性的研究中，人們十分關(guān)心一個(gè)圖（網(wǎng)絡(luò)）生成樹的數(shù)目問題。研究圖生成樹的計(jì)數(shù)對(duì)網(wǎng)絡(luò)的可靠性研究有著十分重要的現(xiàn)實(shí)價(jià)值。

計(jì)算一個(gè)圖的生成樹數(shù)目不是件容易的事情。文獻(xiàn)[1]利用 Feussner 公式計(jì)算了一些特殊圖類的生成樹數(shù)目。文獻(xiàn)[2]通過Cayley 公式求出了3 類特殊平面圖的生成樹數(shù)目，并且給出了它們的遞推關(guān)系式及通項(xiàng)表達(dá)式。文獻(xiàn)[3]通過引入收縮團(tuán)，探討了完全圖的生成樹數(shù)目問題，并利用歸納法得到了比Cayley 公式更一般的公式。文獻(xiàn)[4]給出了上述公式的概率求法。文獻(xiàn)[5]將圖的生成樹數(shù)目問題歸結(jié)為其塊圖的生成樹數(shù)目問題，從而提供了一種較簡(jiǎn)便的計(jì)算圖生成樹數(shù)目的方法。文獻(xiàn)[6-9]利用平面圖的對(duì)偶圖的Kirchhoff 矩陣，求出了一些特殊圖類的生成樹數(shù)目。

1 預(yù)備知識(shí)

定義1包含圖G所有頂點(diǎn)的子圖稱為圖G的生成子圖，若圖G的一個(gè)生成子圖T恰為一棵樹，則稱T是圖G的一棵生成樹。圖G的生成樹數(shù)目用τ(G) 表示[10]。

定義2設(shè)圖G是一個(gè)平面圖的平面嵌入，則G的對(duì)偶圖G*定義為：對(duì)于平面圖G的每個(gè)面f都有G*的頂點(diǎn)f*與之對(duì)應(yīng)，對(duì)于G的每條邊e都有G*的邊e*與之對(duì)應(yīng)，且G*中頂點(diǎn)與被e*連接，當(dāng)且僅當(dāng)G中的面f1與f2被邊e所分隔[10]。

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

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

2 主要結(jié)果與證明

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

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

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

圖2 十字形圖Fig.2 Cross graph

定理3對(duì)n≥1，有

證明根據(jù)圖Yn的特征可知，其對(duì)偶圖Y*n是有3n+2 個(gè)頂點(diǎn)的平面圖，且Y*n的Kirchhoff 矩陣為3n+2 階矩陣。對(duì)Y*n的頂點(diǎn)進(jìn)行適當(dāng)標(biāo)號(hào)，使其對(duì)應(yīng)的Kirchhoff 矩陣為

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

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

遞推關(guān)系式y(tǒng)n- 4yn-1+yn-2=0 的特征多項(xiàng)式及其因子分解為

因此

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

解得

因此

再由定理2 得

定理4對(duì)n≥1，有

證明根據(jù)圖Tn的特征可知，其對(duì)偶圖T*n是有4n+6 個(gè)頂點(diǎn)的平面圖，且T*n的Kirchhoff 矩陣為4n+6 階矩陣。對(duì)T*n的頂點(diǎn)進(jìn)行適當(dāng)標(biāo)號(hào)，使其對(duì)應(yīng)的Kirchhoff 矩陣為

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

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

再由定理2 得

3 結(jié)語(yǔ)

從理論上說，可以利用Kirchhoff 矩陣樹定理來(lái)確定任何圖的生成樹數(shù)目，但是對(duì)于一個(gè)高階的一般圖，計(jì)算其Kirchhoff 矩陣的主子式相當(dāng)困難。利用Kirchhoff 矩陣樹定理，結(jié)合平面圖的對(duì)偶圖對(duì)應(yīng)的Kirchhoff 矩陣，本文的定理3 和定理4，給出了兩類具有一定對(duì)稱性的平面圖Yn和Tn的生成樹數(shù)目的通項(xiàng)公式，從而大大簡(jiǎn)化了對(duì)生成樹數(shù)目的計(jì)算。