無圈競(jìng)賽圖的內(nèi)(外)生成樹與路的計(jì)數(shù)

郭廷花，楊愛民

(1.山西金融職業(yè)學(xué)院基礎(chǔ)部，太原 030008;2.山西大學(xué)數(shù)學(xué)科學(xué)院，太原 030006)

無圈競(jìng)賽圖的內(nèi)(外)生成樹與路的計(jì)數(shù)

郭廷花1，楊愛民2

(1.山西金融職業(yè)學(xué)院基礎(chǔ)部，太原 030008;2.山西大學(xué)數(shù)學(xué)科學(xué)院，太原 030006)

主要研究了無圈競(jìng)賽圖中的外向生成樹和指定點(diǎn)對(duì)的路問題，得到了圖中全部外向生成樹的計(jì)數(shù)公式τ+(Tn)=(n-1)!，在此基礎(chǔ)上，得出圖中全部內(nèi)向生成樹的計(jì)數(shù)公式τ-(Tn)=(n-1)!;兩點(diǎn)之間全部路的計(jì)數(shù)公式σ(Tn)=2n-2，在此基礎(chǔ)上，得出n階無圈圖全部路數(shù)為2j-i-1.

無圈競(jìng)賽圖;外向生成樹;路;計(jì)數(shù)

在本文的討論中，無向圖的概念和術(shù)語可參見[1]，有向圖的概念和術(shù)語可參見[2]。設(shè)G(V，E)為一無向簡單圖，其中V為頂點(diǎn)集為邊集。若稱其為 n階空?qǐng)D，若，即G中每兩點(diǎn)恰有一條邊，稱之為n階完全圖，記為Kn.對(duì)一個(gè)給定頂點(diǎn)數(shù)的圖G，以上兩種情況是含邊數(shù)最少和最多的兩種極端情況，亦即任意一個(gè)n階圖皆為Kn的子圖。

在圖的基本理論研究中，往往討論一個(gè)n階圖中某種特定結(jié)構(gòu)的子圖的存在性問題，以及在存在的情況下的計(jì)數(shù)問題，進(jìn)而如若圖為賦權(quán)圖，還要研究其優(yōu)化問題。比如生成樹問題，Hamilton圈問題，匹配問題等。對(duì)以上問題的研究，尤以生成樹的結(jié)果最為完整。對(duì)于生成樹的存在性，我們熟知有以下結(jié)果:

定理1 每個(gè)連通圖都包含生成樹。

對(duì)一個(gè)給定的簡單圖G，若用τ(G)記其全部的生成樹棵數(shù)，則有以下的迭代公式:

其中G-e是從G中刪去邊e得到的圖，Ge是指對(duì)邊e進(jìn)行收縮。特別地，當(dāng)G=Kn時(shí)，Clayey于1889年證明了如下公式[3]:

對(duì)于一般的圖G，設(shè)D為其任一定向圖，M為其關(guān)聯(lián)矩陣，K為從 M中刪去任意一行得到的矩陣，則:

這就是著名的矩陣—樹定理[4]。

對(duì)于有向圖D中的生成樹(外向和內(nèi)向)的存在性，文獻(xiàn)中已有涉及，但其外向(或內(nèi)向)生成樹的個(gè)數(shù)，所見文獻(xiàn)還未涉及。本文主要討論一類特殊的有向圖—無圈競(jìng)賽圖中的外向(內(nèi)向)生成樹及D中指定兩頂點(diǎn)之間全部路的計(jì)數(shù)問題。

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

主要研究一類特殊的有向圖—無圈競(jìng)賽圖。一個(gè)有向圖D由非空有限集V(D)和A(D)構(gòu)成，V(D)和A(D)為有向圖D的頂點(diǎn)集和弧集。一個(gè)有向圖簡記為D=(V，A).設(shè)(u，v)∈A(D)為D的一條弧，稱頂點(diǎn)u為弧(u，v)的尾，v為弧(u，v)的頭，并稱頂點(diǎn)u支配頂點(diǎn)v，簡記為uv，稱D中頂點(diǎn)u，v是相鄰的。如果D中存在弧uv或vu.

定義1 設(shè)D為有向圖，D中的一條路是一個(gè)由頂點(diǎn)vi和弧ɑj交錯(cuò)排列而點(diǎn)不重的序列P= v1ɑ1v2ɑ2…vk-1ɑk-1vk，i=1，2，…，k-1，P中弧ɑi的尾是vi，頭是vi+1.當(dāng)v1=vk時(shí)，P稱為圈，記為C.

路(圈)中所含的弧數(shù)稱為路(圈)的長度。起點(diǎn)為x，終點(diǎn)為y的路稱為x到y(tǒng)的路，簡記為(x，y)路。

在無向圖中，連通的無圈圖稱為樹。設(shè)T為一棵樹，對(duì)T的每一條邊賦以方向后得到的圖稱之為定向樹。在有向圖的討論中，我們更關(guān)心的是兩類特殊的定向樹—外向生成樹和內(nèi)向生成樹。即設(shè)T是有向圖D的一棵生成定向樹，且T僅含一個(gè)入(出)度為零的頂點(diǎn)s，我們稱之為外向(內(nèi)向)生成樹，并稱s為T的根，用記號(hào)和分別表示有向圖D中以頂點(diǎn)s為根的外向生成樹和內(nèi)向生成樹。

任意給定一個(gè)有向圖D，D中并不是總存在著外(內(nèi))向生成樹。例如一條長度大于2的有向路，顛倒其任意一條弧得到的有向圖，它既不存在外向生成樹，亦不存在內(nèi)向生成樹，什么樣的有向圖D包含外向生成樹或內(nèi)向生成樹呢?下面我們引入有向圖強(qiáng)分解的概念，并利用此概念給出有向圖D存在外(內(nèi))分支的一個(gè)充要條件。

D的一個(gè)強(qiáng)分支是一個(gè)最大的導(dǎo)出強(qiáng)連通有向子圖。若D1，D2，…，Dt是D的全部強(qiáng)分支，顯然有V(D)=V(D1)∪V(D2)∪…∪V(Dt)，且V(Di)∩V(Dj)=φ(i≠j).我們把D1∪D2∪…∪Dt叫做D的強(qiáng)分解。有向圖D的強(qiáng)分支有向圖SC(D)是由收縮D的強(qiáng)分支并刪去在這個(gè)過程中所產(chǎn)生的平行弧而得到的圖，亦即如果D1，D2，…，Dt是D的強(qiáng)分支，則有 V(SC(D)) = {v1，v2，…，vt}和這意味著SC(D)中無有向圈存在，它的頂點(diǎn)可以排列為v1，v2，…，vt，使得當(dāng)j＞i時(shí)，vj到vi無弧，稱為SC(D)的無圈序。對(duì)應(yīng)SC(D)中零入度(零出度)的頂點(diǎn)的強(qiáng)分支稱為D的初始(終止)強(qiáng)分支，其余的強(qiáng)分支稱為中間強(qiáng)分支。

定理2 連通的有向圖D包含一棵外向(內(nèi)向)生成樹當(dāng)且僅當(dāng)D有一個(gè)初始(終止)強(qiáng)分支。

定理3[5]每一個(gè)無圈有向圖有一個(gè)出度為零的頂點(diǎn)和一個(gè)入度為零的頂點(diǎn)。特別的，每一個(gè)無圈有向競(jìng)賽圖恰有一個(gè)出度為零的頂點(diǎn)和一個(gè)入度為零的頂點(diǎn)。

2 主要結(jié)果

設(shè)D為一個(gè)n階無圈競(jìng)賽圖。由于D不含圈，故每個(gè)頂點(diǎn)為一個(gè)強(qiáng)分支，它的強(qiáng)連通分支有向圖即為本身。設(shè)其唯一的無圈序?yàn)関1，v2，…，vn，則顯然下圖為5階無圈競(jìng)賽圖及無圈序:

圖1 5階無圈競(jìng)賽圖Fig.1 5-order acyclic tournament

定理4 設(shè)Tn為n階無圈競(jìng)賽圖，τ+(Tn)為其以v1為根的全部外向生成樹，則τ+(Tn)=(n-1)!.

證明:設(shè)v1，v2，…，vn為其唯一的無圈序，v1為其唯一入度為零的頂點(diǎn)，由定理2知Tn存在外向生成樹，由定理3知其根為v1.下面我們通過對(duì)n做歸納來證明上述定理。

當(dāng)n=2時(shí)唯一的外向生成樹即為本身Tn，當(dāng)n= 3時(shí)，容易驗(yàn)證恰有兩棵外向生成樹。

設(shè)k=n-1時(shí)結(jié)論成立，即τ+(Tn-1)=(n-2)!.

討論k=n時(shí)的情況。令D=Tn-vn，由以上假設(shè).由于vn的入鄰集，而Tn-1的任一外向生成樹添加vn的任一外向弧均構(gòu)成了Tn的一棵生成樹，且這樣得到的外向生成樹是兩兩不同的，故τ+( Tn)=τ+( Tn-1) (n-1) = (n-1)!．

注:(n-1)!不是Tn的非同構(gòu)生成樹的棵樹，而是Tn中不同的生成樹的棵樹;例T4中不同的生成樹為6棵，而不同構(gòu)的生成樹僅有4棵。

把無圈競(jìng)賽圖的每一條弧顛倒后所得之圖與原圖同構(gòu)，僅是序號(hào)顛倒了，與上面證明完全相仿，因而得以下結(jié)論:

定理5 設(shè)Tn為n階無圈競(jìng)賽圖，τ-(Tn)為其以vn為根的全部內(nèi)向生成樹，則τ-(Tn)=(n-1)!.

定理6 設(shè)Tn為n階無圈競(jìng)賽圖，v1，v2，…，vn為其唯一無圈序，用σ(Tn)記其從v1到vn的全部不同的路的數(shù)目，則σ(Tn)=2n-2.

證明:對(duì)Tn的唯一無圈序v1，v2，…，vn，稱v1為起點(diǎn)，vn為終點(diǎn)，其余為中間頂點(diǎn)。對(duì)任意的中間頂點(diǎn)vi1＜ vi2＜ … ＜ vik，其中vi1，vi2，…，vik是{2，3，…，n-1}的一個(gè)k個(gè)元素的組合。由Tn的結(jié)構(gòu)知v1vi1，vi2，…，vikvn是Tn中一條由v1到vn的長為k+1的路，故從v1到vn的長為k+1的路的條數(shù)為Ckn-2，于是從v1到vn的全部不同路數(shù)為:

推論1 設(shè)Tn為n階無圈圖，v1，v2，…，vn為其唯一無圈序，則vi到vj(i＜j)的全部路數(shù)為2j-i-1.

證明:由于Tn中由點(diǎn)vi，vi+1，…，vj的導(dǎo)出子圖Tn＜vi，vi+1，…，vj＞為一j-i+1階無圈競(jìng)賽圖，據(jù)定理6立得。

注:定理6，推論1中的路數(shù)是指不同的路數(shù)，而非不同構(gòu)的路數(shù)。例T4中從v1到v4不同的路數(shù)24-2=4條，而不同構(gòu)的路數(shù)為3條。

[1]BONDY J.A，Murty USR.Graph Theory with Application[M].New York:Amercian Elserier，1979.

[2]BANG-JENSEN J，GUTIN G.Digraphs Theory:Algorithms and Applications[M].London:Springer Verlag，2001.

[3]CAYLEY A.A theorem on tree[J].Quart.J.Math，1889(23):276-378.

[4]KIRCHHOFF G.Uber die Auflosung der Gleichungen，auf welche man bei Untersuchung der linearen Verteilung Strome grfurht wird[J].Ann.Phys.chem，1847(72):497-508.

[5]LUO YONG-PING，YANG AI-MIN.A Lower Bound of the Number of Hamilton Path for Tournament[J].華北工學(xué)院學(xué)報(bào)，2004(6):438-440.

The Count of In-branching(out-branching)and Path on Acyclic Tournaments

GUO Ting-hua1，YANG Ai-ming2
(1.Basic Department，Shanxi Professional College of Finance，Taiyuan 030008，China; 2.School of Mathematical Sciences，Shanxi University，Taiyuan 030006，China)

Out-branchings and paths in the acyclic tournaments are discussed.Two count formulas of all out-branchings and all paths from initial vertex to terminal vertex in a acyclic tournament were got as τ+(Tn)=(n-1)!and σ(Tn)=2n-2，two count formulas of all in-branchings and all paths of order acyclic graph were got on the above basis as σ(Tn)=2n-2and 2j-i-1.

acyclic tournament，out-branching，path，count

0517.5

A

10.3969/j.issn.1673-2057.2015.04.018

1673-2057(2015)04-0323-03

2015-04-08

郭廷花(1979-)，女，講師，碩士研究生，主要研究方向?yàn)閳D論理論及算法的研究。