譚秋月

（武夷學(xué)院數(shù)學(xué)與計(jì)算機(jī)系，福建武夷山354300）

基于路的多重完全圖相關(guān)圖生成樹計(jì)數(shù)

譚秋月

（武夷學(xué)院數(shù)學(xué)與計(jì)算機(jī)系，福建武夷山354300）

利用圖G的標(biāo)定技巧、矩陣和行列式運(yùn)算、補(bǔ)生成樹矩陣定理、不等式運(yùn)算等理論，研究了當(dāng)m=2, 3, 4, 5，且a1, a2, …, am為任意數(shù)時(shí)，基于路的多重完全圖相關(guān)圖一般情況的生成樹數(shù)目，并得到了相關(guān)公式。

多重完全圖相關(guān)圖；生成樹；補(bǔ)生成樹矩陣定理

0 引言

圖的生成樹數(shù)目是圖的重要不變量之一，其應(yīng)用廣泛。例如在網(wǎng)絡(luò)可靠性方面有重要應(yīng)用：一個(gè)網(wǎng)絡(luò)可以用一個(gè)圖G來模擬，這個(gè)網(wǎng)絡(luò)中所有的站點(diǎn)之間可以互相通訊，意味著圖G中必須包含一個(gè)生成樹，因此，圖的生成樹的數(shù)目是評(píng)價(jià)該圖（網(wǎng)絡(luò)）可靠性的重要指標(biāo)之一，最大化生成樹的數(shù)目是加強(qiáng)網(wǎng)絡(luò)可靠性的一個(gè)途徑。

如果能得到一個(gè)圖G生成樹數(shù)目的計(jì)數(shù)公式對(duì)確定圖G在完全圖Kn中的補(bǔ)圖（即補(bǔ)圖類Kn-G，其中）的生成樹數(shù)目的計(jì)數(shù)公式也很有意義。文獻(xiàn)[1-3]給出了基于路的多重完全圖相關(guān)圖補(bǔ)圖類。本文討論當(dāng)m=2, 3, 4, 5時(shí)基于路的多重完全圖相關(guān)圖生成樹的數(shù)目，并求出一般情況下（即a1, a2, …, am為任意數(shù)時(shí)）的計(jì)數(shù)公式。

1 圖的定義

假設(shè)G1=(V1, E1)和G2=(V2, E2)沒有公共頂點(diǎn)，以V1∩V2為頂點(diǎn)集，以E1, E2和為邊集所組成的圖，稱為G2和G2的聯(lián)圖，記為[4]。

特別地，一個(gè)頂點(diǎn)和完全圖Km的聯(lián)圖Km+1為完全圖，如圖1所示。

圖1 Fig.1

定義1[3]由m個(gè)完全圖Ka1+1, Ka2+1, Kam+1和連接這m個(gè)完全圖上的任意一點(diǎn)形成的路Pm所組成的圖，稱為一個(gè)基于路的多重完全圖，記為。

定義2[3]如果基于路的多重完全圖滿足ai≥2(i=1, 2, …, m)以及n≥m+ a1+…+am，在完全圖Kn中刪去圖所有的邊后組成的圖稱為基于路的多重完全圖相關(guān)圖，記為。

圖2為一個(gè)基于路的4重完全圖PK4(2, 2, 3, 2)，圖3為一個(gè)基于路的4重完全圖相關(guān)圖K15-PK4(2, 2, 3, 2)的補(bǔ)圖。

圖2 (2, 2, 3, 2)Fig.2(2, 2, 3, 2)

圖3 Fig.3

本文僅討論m=2, 3, 4, 5，且a1, a2, …, am為任意數(shù)時(shí)，多重完全圖相關(guān)圖生成樹數(shù)目的計(jì)數(shù)公式。

2.1 結(jié)論

定理1當(dāng)m=2，且a1, a2為任意數(shù)時(shí)，基于路P2的多重完全圖相關(guān)圖的生成樹數(shù)目為

特殊地，當(dāng)m=2，a1=a2=a時(shí)，的生成樹數(shù)目為

定理2當(dāng)m=3，且a1, a2, a3為任意數(shù)時(shí)，基于路P3的多重完全圖相關(guān)圖的生成樹數(shù)目為

特殊地，當(dāng)m=3，a1=a2=a3=a時(shí)，的生成樹數(shù)目為

定理3當(dāng)m=4，且a1, a2, a3, a4為任意數(shù)時(shí)，基于路P4的多重完全圖相關(guān)圖的生成樹數(shù)目為

特殊地，當(dāng)m=4，a1=a2=a3=a4=a時(shí)，的生成樹數(shù)目為

定理4當(dāng)m=5，且a1, a2, a3, a4, a5為任意數(shù)時(shí)，基于路P5的多重完全相關(guān)圖的生成樹數(shù)目為

2.2 結(jié)論的證明

式中

因此，根據(jù)補(bǔ)生成樹矩陣定理[1]，生成樹的數(shù)目為。

3 結(jié)語

對(duì)定理1至定理4中的生成樹數(shù)目公式進(jìn)行比較，沒有找到規(guī)律，目前無法用數(shù)學(xué)歸納法推導(dǎo)出圖更一般（即m為任意大于1的整數(shù)時(shí)）的生成樹數(shù)目的公式，希望在進(jìn)一步工作中有所突破。

[1]Nikolopoulos S D，Rondogiannis P. On the Number of Spanning Trees of Multi-Star Related Graphs[J]. Information Processing Letters，1998，65(4)：183-188.

[2]Yan W M，Myrvold W，Chung K L. A Formula for the Number of Spanning Trees of a Multi-Star Related Graph [J]. Information Processing Letters, 1998, 68(6)：295-298.

[3]譚秋月.基于路的多重完全圖相關(guān)圖的生成樹數(shù)目[J].曲阜師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，38(3)：47-52. Tan Qiuyue. The Number of Spanning Trees of Multi-Complete Related Graphs Based on Paths[J]. Journal of Qufu Normal University：Natural Science，2012，38(3)：47-52.

[4]李曉明，黃振杰. 圖中樹的數(shù)目計(jì)算及其在網(wǎng)絡(luò)可靠性中的作用[M]. 哈爾濱：哈爾濱工業(yè)大學(xué)出版社，1993：1-9. Li Xiaoming，Huang Zhenjie. The Number of Trees in Graph Calculation and Its Role in the Network Reliability [M]. Harbin：Harbin Institute of Technology Press，1993：1-9.

[5]譚秋月. 基于圈或路的多重星相關(guān)圖的生成樹數(shù)目[J].天津師范大學(xué)學(xué)報(bào)：自然科學(xué)版， 2013，33(1)：30-34. Tan Qiuyue. Number of Spanning Trees of Multi-Star Related Graphs Based on Cycles or Paths[J]. Journal of Tianjin Normal University：Natural Science Edition，2013，33(1)：30-34.

（責(zé)任編輯：鄧光輝）

The Path-Based Enumeration of Spanning Trees of Multi-Complete Related Graphs

Tan Qiuyue
（Department of Mathematics and Computer，Wuyi University，Wuyishan Fujian 354300，China）

By means of Graph G labeling techniques, matrix and determinant computations, the complement-spanning-tree matrix theorem and inequalities computing etc., studies the number of spanning trees of the general situation of the path-based multi-complete related graphswhen m=2, 3, 4, 5, and a1, a2, …, amare arbitrary numbers, and gets relative counting formula.

multi-complete related graphs；spanning trees；complement-spanning-tree matrix theorem

O157.5

A

1673-9833(2014)05-0001-04

10.3969/j.issn.1673-9833.2014.05.001

2014-01-18

福建省教育廳科技基金資助項(xiàng)目（JK2012056），武夷學(xué)院一般基金資助項(xiàng)目（xq0933）

譚秋月（1980-），女，陜西楊凌人，武夷學(xué)院講師，碩士，主要研究方向?yàn)閳D論和離散數(shù)學(xué)，E-mail：tqyspa@163.com