連通圖含某些指定邊生成樹的環(huán)和矩陣生成法

孫文靜, 胡茂林

(1.寧夏大學(xué) 數(shù)學(xué)計算機學(xué)院, 寧夏 銀川 750021; 2.淮陰師范學(xué)院 數(shù)學(xué)科學(xué)學(xué)院, 江蘇 淮安 223300)

連通圖含某些指定邊生成樹的環(huán)和矩陣生成法

孫文靜1,2, 胡茂林2

(1.寧夏大學(xué) 數(shù)學(xué)計算機學(xué)院, 寧夏 銀川 750021; 2.淮陰師范學(xué)院 數(shù)學(xué)科學(xué)學(xué)院, 江蘇 淮安 223300)

提出并研究了連通圖含某些指定邊的生成樹的生成問題.在給出環(huán)補關(guān)聯(lián)矩陣與環(huán)和矩陣等定義的基礎(chǔ)上,給出并證明了連通圖含某些指定邊的生成樹的生成方法(環(huán)和矩陣法).利用環(huán)和矩陣法尋求圖的特殊的生成樹的方法、步驟以及其準確性和快捷性也在文中進行了討論.

指定邊; 生成樹; 環(huán)補關(guān)聯(lián)集; 環(huán)補關(guān)聯(lián)矩陣; 環(huán)和矩陣

0 引言

我們知道求連通圖的全部生成樹有很多方法,如Johson給出的基本割集多項式相乘展開法[1]、Mayeda給出的基本樹變換法[2]、朱紹文給出的兩類K-樹遞推公式法[3]、胡茂林給出的全部生成樹的組合生成法[4]等.在圖論的應(yīng)用中,常需要找出一個連通圖的所有生成樹.例如,在電網(wǎng)絡(luò)的拓撲分析中,需要找出網(wǎng)絡(luò)中所有可能的互異生成樹.但在實際中往往需要求出一個連通圖的含某些指定邊的生成樹.例如,一個有n座城市組成的地區(qū),城市1至n編號,為了地區(qū)經(jīng)濟的快速發(fā)展,決定其中一些城市可以修建高速鐵路.由于某幾個城市經(jīng)濟特別繁榮且考慮到建設(shè)成本,因此決定在這幾個經(jīng)濟特別繁榮的城市間修建直達的高速鐵路且這幾城市間高鐵不形成環(huán).這就需要求出一個連通圖的含某些指定邊的生成樹.因此,本文將在文[4]的基礎(chǔ)上介紹連通圖含某些指定邊的生成樹的一種方法(環(huán)和矩陣法).為此,我們給出含某些指定邊的圖頂點的相關(guān)關(guān)聯(lián)集、環(huán)補關(guān)聯(lián)集定義,在此基礎(chǔ)上把含某些指定邊環(huán)補關(guān)聯(lián)集向量及自環(huán)補關(guān)聯(lián)集向量的不重并組成矩陣,這樣就可減少很多不必要的運算,從而準確快捷地得到指定的全部生成樹.在本文中,若非特別聲明,大寫字母G一般表示一個圖,G(p,q)一般表示一個具有p個頂點q條邊的圖.另外,還用到下面概念和運算.

關(guān)聯(lián)集: 設(shè)v是圖G的一個頂點,與v關(guān)聯(lián)的所有邊的集合,稱為頂點v的關(guān)聯(lián)集,記作S(v).

集合環(huán)和運算: 設(shè)A,B是兩個集合,則稱集合{x|x∈(AB)Y(BA)}為集合A與B的環(huán)和或?qū)ΨQ差,記為A?B,并稱符號?為集合的環(huán)和運算.

模2加法: 0+0=0,1+0=1,1+1=0.

1 幾個基本概念

在本節(jié)我們定義本文要用到的幾個基本概念即相關(guān)關(guān)聯(lián)集、環(huán)補關(guān)聯(lián)集、環(huán)補關(guān)聯(lián)矩陣、參考環(huán)補關(guān)聯(lián)矩陣和環(huán)和矩陣等.

定義2 設(shè)邊a1,a2,…,ak(1≤k≤p-1)是具有p個頂點q條邊的圖G(p,q)的給定的k條邊,如果G的一個關(guān)聯(lián)集S(v)含指定邊ai1,ai2,…,ail,其中{ai1,ai2,…,ail}?{a1,a2,…,ak},則稱該關(guān)聯(lián)集為圖G(p,q)與指定邊a1,a2,…,ak相關(guān)的關(guān)聯(lián)集,記為Sai1ai2…ail(v),其中1≤l≤k.

定義3 對于圖G(p,q)的指定邊a1,a2,…,ak(1≤k≤p-1),若圖G的幾個關(guān)聯(lián)集作環(huán)和運算所得的結(jié)果中含全部指定邊a1,a2,…,ak,則稱這幾個關(guān)聯(lián)集為圖G的關(guān)于指定邊a1,a2,…,ak的互為環(huán)補關(guān)聯(lián)集.

特別地,若一個關(guān)聯(lián)集本身含有指定邊a1,a2,…,ak,則稱這個關(guān)聯(lián)集關(guān)于指定邊a1,a2,…,ak還是自環(huán)補的.

定義4 一個圖G(p,q)的關(guān)于指定邊a1,a2,…,ak(1≤k≤p-1)的所有互為環(huán)補關(guān)聯(lián)集的對應(yīng)的關(guān)聯(lián)向量以及所有自環(huán)補的關(guān)聯(lián)集的對應(yīng)的關(guān)聯(lián)向量的不重并叫圖G的關(guān)于指定邊a1,a2,…,ak(1≤k≤p-1)的環(huán)補關(guān)聯(lián)矩陣,記為M(G(a1,a2,…,ak));從M(G(a1,a2,…,ak))中任意刪去一行所得到的矩陣叫圖G的關(guān)于指定邊a1,a2,…,ak的參考環(huán)補關(guān)聯(lián)矩陣,記為M′(G(a1,a2,…,ak));刪去的一行所對應(yīng)的G的頂點叫參考點.

定理1 一圖G(p,q)的任意兩個關(guān)聯(lián)集的環(huán)和等價于它們所對應(yīng)的關(guān)聯(lián)向量在{0,1}域上作模2加法.

設(shè)S(v1)∩S(v2)={ajk,ajk+1,…,ajl},即aik=ajk,aik+1=ajk+1,…,ail=ajl,其中1≤k≤l≤min{m,n},

則

S(v1)?S(v2)={ai1,…,aik-1,ail+1,…,aim,aj1,…ajk-1,ajl+1,…ajn},

圖1 一個(4,5)的連通標定圖

故

反之亦然.

定義5 對于圖G(p,q)的指定邊a1,a2,…,ak(1≤k≤p-1),把它的參考環(huán)補關(guān)聯(lián)矩陣中各個自環(huán)補關(guān)聯(lián)集以及各種互為環(huán)補的關(guān)聯(lián)集作環(huán)和一起構(gòu)成的矩陣叫圖G關(guān)于指定邊a1,a2,…,ak的環(huán)和矩陣,記作A.

例1 對圖1所示的圖G指定a,b邊,求圖G關(guān)于a,b的相關(guān)關(guān)聯(lián)集、環(huán)補關(guān)聯(lián)集、環(huán)補關(guān)聯(lián)矩陣及環(huán)和矩陣.

圖G的關(guān)聯(lián)集為

S(1)={a,d,e};S(2)={a,b};S(3)={b,c,e};S(4)={c,d}.

因為圖G指定邊為a,b,所以圖G關(guān)于a,b的相關(guān)關(guān)聯(lián)集為

Sa(1)={a,d,e};Sa,b(2)={a,b};Sb(3)={b,c,e}.

又因為

Sa(1)?Sb(3)={a,b,c,d};Sa,b(2)??={a,b};Sa(1)?Sb(3)?S(4)={a,b}.

所以圖G關(guān)于指定邊a,b的環(huán)補關(guān)聯(lián)集為

Sa(1)與Sb(3);Sa(1),Sb(3)與S(4).

自環(huán)補關(guān)聯(lián)集為

Sa,b(2)={a,b}.

因此圖G關(guān)于指定邊a,b的環(huán)補關(guān)聯(lián)矩陣為

從M(G(a,b))中刪去第四行即參考點為頂點4得到圖G關(guān)于指定邊a,b的參考環(huán)補關(guān)聯(lián)矩陣為

于是,圖G關(guān)于指定邊a,b的環(huán)和矩陣為

2 連通圖含某些指定邊的生成樹的生成

引理1[4]設(shè)G是具有q條邊的a1,a2,…,aq的p階連通圖,其增廣關(guān)聯(lián)矩陣是C,則由G的p-1條邊aj1,aj2,…,ajp-1導(dǎo)出的G的子圖T=aj1aj2…ajP-1是G的一棵生成樹的充要條件是在C中存在唯一的一行,使得這行在第j1,j2,…,jp-1列處的元素都是1.

定理2 設(shè)G(p,q)具有q條邊a1,a2,…,aq的p階連通圖,aj1,aj2,…,ajk(1≤k≤p-1)是G的k條指定邊且由這k條邊導(dǎo)出的G的子圖不含圈,又設(shè)關(guān)于這k條邊的一個環(huán)和矩陣為A,則T=ai1ai2…aip-1是G的一棵含指定邊aj1,aj2,…,ajk生成樹的充要條件是在A中存在唯一一行,使得這行在第i1,i2,…,ip-1列處元素都是1,其中有k個1元素在指定邊所對應(yīng)列上.

證明設(shè)圖G的增廣關(guān)聯(lián)矩陣C是與G的環(huán)和矩陣A具有相同的參考點的G的一個增廣關(guān)聯(lián)矩陣.由于圖G的環(huán)和矩陣A是它的增廣關(guān)聯(lián)矩陣C的所有行向量集合的一個子集組成的矩陣,因此矩陣A是與C同列且具有相同的參考點的C的子矩陣.

下面證明C在第j1,j2,…,jk列的所有元素都為1的每個行向量都在A中.

設(shè)α是C的在第j1,j2,…,jk位置元素都為1的行向量,令這個行向量對應(yīng)的邊集合為S,則S含有所有指定邊,這樣S有且僅有以下兩種情況:

若S是G的一個自環(huán)補的關(guān)聯(lián)集,由定義5則它對應(yīng)的關(guān)聯(lián)向量就在A中;

若S是G的幾個關(guān)于指定邊互為環(huán)補的關(guān)聯(lián)集的環(huán)和,由定義5則它所對應(yīng)的關(guān)聯(lián)向量在A中.

必要性: 設(shè)T=ai1ai2…aip-1是G的一棵含指定邊aj1,aj2,…,ajk的生成樹,則由引理1[4]知,在矩陣C中存在唯一一行使得這行在第i1,i2,…,ip-1列的元素都為1.特別地在第j1,j2,…,jk列的元素都為1,因此這樣的行向量必在A中.又由于A是C的子矩陣,故這個行向量在A中是唯一的.

圖2 一個(5,8)的連通標定圖

充分性: 設(shè)α是A中唯一一行在第i1,i2,…,ip-1列的元素都為1且其中有k個1在指定邊aj1,aj2,…,ajk所對應(yīng)列上,則α同時也在C中.由引理[4]知T=ai1ai2…aip-1是G的一棵生成樹.由于C中這樣的α在第j1,j2,…,jk列的元素都為1,所以T含有指定邊aj1,aj2,…,ajk,即T是含有指定邊aj1,aj2,…,ajk的G的一棵生成樹.

例2 對圖2所示的圖G指定a,b邊,求圖G含指定邊a,b生成樹.

圖G的關(guān)聯(lián)集為

S(1)={a,b};S(2)={b,c,g,h};S(3)={c,d,f};S(4)={d,e,g};S(5)={a,e,f,h}.

圖G對于指定邊a,b的相關(guān)關(guān)聯(lián)集為

Sa,b(1)={a,b};Sb(2)={b,c,g,h};Sa(5)={a,e,f,h}.

因為

Sa,b(1)?φ={a,b};Sb(2)?Sa(5)={a,b,c,e,f,g};

Sb(2)?S(3)?Sa(5)={a,b,d,e,g};

Sb(2)?S(4)?Sa(5)={a,b,c,d,f};Sb(2)?S(3)?S(4)?Sa(5)={a,b}.

所以圖G對于指定邊a,b的環(huán)補關(guān)聯(lián)集為

S(2)與S(5);S(2)、S(3)與S(5);S(2)、S(4)與S(5);S(2)、S(3)、S(4)與S(5).

自環(huán)補關(guān)聯(lián)集為

Sa,b(1)={a,b}.

圖G對于指定邊a,b的環(huán)補關(guān)聯(lián)矩陣為

從M(G(a,b))中刪去第五行即選參考點為頂點5得圖G對于指定邊a,b的參考環(huán)補關(guān)聯(lián)矩陣為

圖G對于指定邊a,b的環(huán)和矩陣為

由定理2可知圖G中含指定邊a,b生成樹有

abcd,abdf;abde,abdg;abce,abcg,abef,abfg.

[1] Johson D E, Johonson J R. Graph Theory with Engineering Application[M]. NewYork: Ronald Press,1972.

[2] Mayeda W. Graph Theory[M]. NewYork: Wiley-Intrsience, 1972.

[3] 朱紹文, 陳洪陶. 全部生成樹的一種生成方法[J]. 蘭州大學(xué)學(xué)報:自然科學(xué)版,1988,24(4):64-70.

[4] 胡茂林, 藺勇. 全部生成樹的組合生成法[J]. 陜西科技大學(xué)學(xué)報,2004,22(1):124-126.

TheRingSumMatrixGeneratingMethodofSpanningTreesContainingCertainAppointedEdgesinConnectedGraph

SUN Wen-jing1,2, HU Mao-lin2

(1.School of Mathematics and Computer Science, Ningxia University, Yinchuan Ningxia 750001, China)(2.School of Mathematical Science, Huaiyin Normal University, Huaian Jiangsu 223300, China)

In this paper, the generating problem of the spanning tree containing some prescribed edges is posed and discussed. This paper gives and proves the generating method after defining the related definitions and notations of the ring complement in-cidence matrix and ring sum matrix. The method, step and the accuracy, immediacy of the method seeking the particular spanning tree using the ring sum matrix method is also further discussed

prescribed edges; spanning trees; ring complement incidence set; ring complement incidence matrix; ring sum matrix

2013-04-05

孫文靜(1985-), 女, 江蘇宿遷人, 碩士研究生, 研究方向為圖論.

O157.5

A

1671-6876(2013)03-0208-05

[責任編輯李春紅]