圖G（p，q）的生成子圖的構造與計數

吳建強 侴萬禧

（1.安徽理工大學 理學院，安徽 淮南 232001；2.安徽理工大學 土木建筑學院，安徽 淮南 232001）

0 引言

在各種各樣的圖中，有一類簡單的，但卻是重要的圖，就是所謂的“樹”。它是基爾霍夫在解決電路理論中求解聯立方程問題時首先提出來的，可惜他的發現超越了時代而長期沒有引起重視。樹與圖中其他一些基本概念，如回路、割集等有密切的聯系，是圖論中比較活躍的領域。在圖論中，解決一些懸而未決的問題往往首先從樹這類圖入手。許多問題對一般的圖未能解決或者沒有簡便的方法，而對于樹，則已完滿解決，且方法較為簡便。

給定一個無向圖G，若G的一個生成子圖T是樹，則稱T為G的生成樹。圖的生成樹不是唯一的。但任何連通圖至少有一顆生成樹。所有生成樹中具有最小數的生成樹稱為最小生成樹，求最小生成樹是實際問題的需要，例如“為了把若干城市連接起來，設計最短通信線路”，“為了解決若干居民點供水，要求設計最短的自來水管線路”等等。

1 基本思路

定義1 設G（p,q）為p個頂和q個邊的任意連通圖，則G（p,q）中任意p-1個邊所導出的S（G）個子圖稱為生成子圖。

定義2 設圖G(p,q)中存在S(G)個生成子圖，則S（G）個生成子圖中T（G）個不含圈的生成子圖稱為生成樹，C（G）個含圈的生成子圖稱為含圈的生成子圖，并有 S（G）=C（G）+T（G）。

定理1 設G（p,q）為任意連通圖，則G（p,q）中任意p-1個邊所導出的生成子圖的個數為

S（G）個生成子圖中含圈的生成子圖的個數為

S（G）個生成子圖中不含圈的生成樹的個數為

式中：Ci（G）—圖 G（p,q）中 Ci的個數；個邊中任取p-j個邊的選擇數。

證明：不失一般性，設 G（p,q）為 p＝4，q＝6 的完全圖 K4，且 K4中 C3的個數 C3（G）＝4；C4的個數 C4（G）＝1，若定理 1 為真，則 K4中 P—1=3個邊所導出的生成子圖的個數

S（G）＝20個生成子圖中含圈的生成子圖僅與圈C3有關系，故含圈的生成子圖的個數為

S（G）＝20個生成子圖中不含圈的生成樹的個數為

定理1得證。

定理2設G（p,q）為任意連通圖，則G（p,q）中p-1個邊所導出的S(G)個生成子圖的構造歸結為

b＝S（G），v＝p，r＝A，k＝p－1，λ＝B 的（b，v，r，k，λ）設計中 S(G)個區組的構造。由于G（p,q）中q個邊的編號為區組的變元，S(G)個生成子圖與S(G)個區組一一對應，C（G）個含圈的生成子圖與C（G）個區組一一對應，T（G）個生成樹與 T（G）個區組一一對應，且有 S（G）＝C（G）＋T（G）

證明：不失一般性，設則 G（p,q）為 p＝4，q＝6 的完全圖 K4，若定理2 為真，則完全圖 K4的個生成子圖的構造歸結為 b＝20，v＝p＝4，r＝6，k＝p－1＝3，λ＝4 的（b，v，r，k，λ）設計中下列 0個區組 ：（1，2，3），（1，2，4），（1，2，5），（1，2，6），（1，3，4），（1，3，5），（1，3，6），（1，4，5），（1，4，6），（1，5，6），（2，3，4），（2，3，5），（2，3，6），（2，4，5），（2，4，6），（2，5，6），（3，4，5）,(3,4,6),(3,5,6),(4,5,6)的構造，當K4中q=6個邊的編號被確定后，S(G)=20個生成子圖與20個區組一一對應，20個生成子圖中有4個含圈的生成子圖，有16個不含圈的生成樹。 亦即：T（G）＝16，C（G）＝4 且

S（G）＝C（G）＋T（G），見圖 1。 定理 2 得證。

圖1

2 八面體平面的生成子圖

1）生成樹的個數

設圖 G（p,q）為 p＝6，q＝12 的八面體平面圖，圖 G（6，12）中的 C3的個數 C3（G）＝8，C4的個數 C4（G）＝15，C5的個數 C5（G）＝24，則據定理 1，圖 G（6，12）中生成子圖的個數為

S（G）＝792個生成子圖中含圈的生成子圖的個數C（G）＝393

S（G）＝792個生成子圖中不含圈的生成樹的個數為：

2）S（G）個生成子圖的構造

G（6，12）中 S（G）＝792 個生成子圖可借助于 b＝792，r＝330， k＝5，λ＝120 的下列區組的（b，v，r，k，λ）設計 ：（1，2，3，4，5）（1，2，3，4，6），（1，2，3，4，7），（1，2，3，4，8），（1，2，3，4，9），（1，2，3，4，10），（1，2，3，4，11），（1，2，3，4，12），（1，2，3，5，6），（1，2，3，5，7）…(8,9,10,11,12)。 當圖 G（6，12）中q＝12個邊的編號被確定后，792個區組中的399個區組與399個生成樹一一對應，792個區組中的393個區組與393個含圈的生成子圖一一對應，且有 S（G）＝C（G）＋T（G）的關系。 這說明：生成樹的個數的結算結果與實際構造想吻合。

3 結束語

由于Cayley公式僅適用于任意完全圖Kp中生成樹個數的計算。而任意非完全圖中的生成樹的計算問題，可以運用本文方法來解決，盡管計算繁瑣，但卻解決了任意圖生成樹的構造。任意平面中的生成樹在遙控技術等領域有著廣泛的應用，根據本文的思想，一種基于森林分解的生成樹的構造和計數方法將能夠得到，也必將得到廣泛的運用。

［1］Bollobasb.Graph Theory[M].New York：San Francisco,Academic Press,1978.

［2］Freds.Roberts BarryTesman.Applied Combinatorics[M].beijing：China Machine Press,2007.

［3］侴萬禧.完全圖的生成樹的構造與計算[J].山東師范大學學報：自然科學版,2007,11(4)：72-72.

［4］侴萬禧.任意的生成樹的構造與計數[J].山東師范大學學報：自然科學版,2008,23(1)：14-15.

［5］侴萬禧,郝朋偉.完全二分圖的生成樹的個數[J].阜陽師范學院學報,2008,25(4)：12-14.

［6］侴萬禧,等.平面的四著色與對偶圖的H圈[J].沈陽師范大學學報：自然科學版,2009,27(3)：264-266.

［7］徐俊明.圖論及其應用[M].中國科學技術大學出版社,2004.

［8］侴萬禧.2t名運動員的循環賽和對集的劃分[J].安徽理工大學學報：自然科學版,2006,26(1)：64-69.

［9］侴萬禧.邊矩陣K2n+1的k+1-邊著色與循環賽的安排[J].安徽建筑工業學院學報：自然科學版,2006,14(4)：1-5.

［10］侴萬禧,林雨.12 面體中的 H 圈[J].揚州大學學報：自然科學版,2007,10(4)：32-38.