二部圖的幾種判別方法

?

二部圖的幾種判別方法

路芳

(包頭師范學(xué)院 數(shù)學(xué)科學(xué)學(xué)院，內(nèi)蒙古 包頭 014030)

摘要：介紹了三種對(duì)二部圖進(jìn)行判別的方法，并將它們應(yīng)用于實(shí)例圖形，表明這些方法都是可行且有效的。其中，矩陣法的理論依據(jù)是：對(duì)于任意一個(gè)連通二部圖的鄰接矩陣，其最小特征值所對(duì)應(yīng)的特征向量的各分量是非零的，而且同號(hào)分量對(duì)應(yīng)著同一類頂點(diǎn)。

關(guān)鍵詞：二部圖；判別；矩陣

二部圖又叫作二分圖，是圖論中的一種特殊圖形。其定義是：若能將無(wú)向圖G=的頂點(diǎn)集合V分成兩個(gè)子集V1和V2, 這兩個(gè)子集滿足V1∪V2=V,V1∩V2=Φ,且G中任意一條邊e=(u,v),都有u(或v)∈V1,且v(或u)∈V2,則G是二部圖，記為G=?V1?V2?E?。圖1所示，(a)中是一個(gè)二部圖，頂點(diǎn)集為V={a,b,c,d,e,f},V1={a,d,e},V2={b,c,f},且滿足任意一條邊的兩個(gè)端點(diǎn)，一個(gè)屬于V1，另一個(gè)屬于V2。圖1(b)不是二部圖。

圖1

二部圖在實(shí)際問題中有廣泛的應(yīng)用，比如“考試安排”，“資源分配”等問題的求解，都要用到二部圖的知識(shí)，因此，二部圖的判別是一個(gè)相對(duì)重要的問題。本文就判斷一個(gè)無(wú)向連通圖是二部圖的三種方法進(jìn)行了研究和總結(jié)。

本文只研究簡(jiǎn)單無(wú)向連通圖，對(duì)于非連通圖, 可以分別在不同的連通分支中應(yīng)用判別方法。

1．定義法

二部圖的定義：設(shè)G=(V,E)是一個(gè)無(wú)向圖，如果頂點(diǎn)集合V可以分為兩個(gè)互不相交的子集V1,V2，并且圖中的每一條邊e=(u，v),其兩個(gè)端點(diǎn)u和v分別屬于這兩個(gè)不同的頂點(diǎn)集，則稱圖G是一個(gè)二部圖。依照此定義判斷圖形能否畫成互補(bǔ)頂點(diǎn)集的形式來(lái)判別其是否是二部圖。但這種方法必須再畫一個(gè)與待判別圖形同構(gòu)的新的圖形，換一種形式，可以在原圖形上標(biāo)示符號(hào)來(lái)達(dá)到相同的效果。

在G中任找一點(diǎn)u，將其標(biāo)定為A，與u點(diǎn)相鄰的所有的點(diǎn)標(biāo)定為B，再將與標(biāo)定為B的點(diǎn)相鄰的點(diǎn)標(biāo)定為A，以此類推，若能把所有的點(diǎn)都標(biāo)定好，則G是二部圖，若出現(xiàn)標(biāo)定為同字母的兩點(diǎn)相鄰的情況，則G不是二部圖。

如，圖2(a)是二部圖，(b)不是二部圖。

圖2

2．定理法

判定定理： 一個(gè)無(wú)向圖G=是二部圖當(dāng)且僅當(dāng)G中無(wú)奇數(shù)長(zhǎng)度的圈。即G至少有兩個(gè)頂點(diǎn)，且其所有圈的長(zhǎng)度均為偶數(shù)。

證明：先證必要性

設(shè)G為二部圖，由于V1,V2非空，所以G中至少有兩個(gè)頂點(diǎn)。若G中沒有回路，則結(jié)論顯然成立。若G中有回路，下邊證明G中沒有長(zhǎng)度為奇數(shù)的圈。設(shè)C為G中任意一個(gè)圈，令c=v0v1v2…vtv0，其中，若有vi∈V1(i為奇數(shù))，則一定有vj∈V2(j為偶數(shù))，因此，t必為奇數(shù)，從而c的長(zhǎng)度為t+1，是偶數(shù)，即c為偶圈。

再證充分性

V1∪V2=V(G),下邊只要證明V1中任意兩點(diǎn)不相鄰，V2中任意兩點(diǎn)也不相鄰。若存在vi,vj∈V1,且有(vi,vj)=e,e∈V(E),設(shè)v0到vi,vj的距離分別為l1,l2,則它們的長(zhǎng)度d(v0,vi),d(v0,vj)都是偶數(shù)，于是回路v0,…vi,vj,…v0的長(zhǎng)度是奇數(shù)。若是圈則為奇數(shù)長(zhǎng)度的圈，這與條件相矛盾，類似地可以證明，V2中也不存在相鄰的頂點(diǎn)，于是G為二部圖。

由判定定理可知，圖3中(a)中沒有奇圈，(b)中沒有圈，兩個(gè)圖都是二部圖

圖3

3．矩陣法

相關(guān)定理(Perron Frobenus)設(shè)A是n階不可約非負(fù)矩陣，則

(1)A的譜半徑ρ是A的特征值；

(2)A有一個(gè)對(duì)應(yīng)于ρ的正特征向量；

(3)A關(guān)于ρ的代數(shù)重?cái)?shù)multρ(A)等于1，即ρ是A的特征多項(xiàng)式的單根。

判定方法：

利用二部圖的鄰接矩陣的特征向量的性質(zhì)：最小特征值對(duì)應(yīng)的向量的分量符號(hào)與相應(yīng)頂點(diǎn)所在的點(diǎn)集有關(guān)，同號(hào)分量對(duì)應(yīng)的點(diǎn)在同一個(gè)點(diǎn)集中，利用這個(gè)特點(diǎn)可以把頂點(diǎn)集合V劃分成V1和V2。但在非二部圖中，最小特征值對(duì)應(yīng)的特征向量也會(huì)存在正負(fù)分量，所以，還要進(jìn)一步計(jì)算與邊數(shù)有關(guān)的參數(shù)t，當(dāng)t與邊數(shù)m相等時(shí)，可以確定圖形G是二部圖。

理論依據(jù)：

設(shè)矩陣A=(aij)m×n是圖G的鄰接矩陣，當(dāng)圖G為二部圖時(shí)，A可通過置換變成如下形式：

(1)

其中分塊矩陣B僅由0,1元素構(gòu)成。

設(shè)鄰接矩陣A的特征值是λ，特征方程為

Ax=λx2

(2)

于是有BTx1=λx2,Bx2=λx1

進(jìn)而得到

BBTx1=λ2x13

(3)

BTBx2=λ2x24

(4)

也就是有A2x=λ2x

其中x=(x1,x2)T,xi(i=1,2)是非零向量。

由矩陣的對(duì)稱性可以判斷矩陣BBT，BTB是實(shí)對(duì)稱矩陣，而且都是不可約的。因?yàn)槿鬊BT為可約矩陣，則有

(5)

而A2中的元素aij表示G圖中與vi和vj都相鄰的頂點(diǎn)數(shù)，而5式說明點(diǎn)集V中存在著某些點(diǎn)與其它點(diǎn)沒有相同的鄰點(diǎn)，這與圖G是連通圖相矛盾，所以矩陣BBT是不可約的，同理BTB也是不可約矩陣。

由3和4兩個(gè)公式可知，鄰接矩陣A的最小特征值對(duì)應(yīng)的特征向量x的兩個(gè)分量x1,x2，應(yīng)該是一個(gè)正的，一個(gè)負(fù)的向量。所有正的分量對(duì)應(yīng)的頂點(diǎn)在同一個(gè)點(diǎn)集中，負(fù)的分量對(duì)應(yīng)的頂點(diǎn)的另一個(gè)點(diǎn)集當(dāng)中，這樣可以將圖G的頂點(diǎn)集合劃分成兩個(gè)不相交的集合。

當(dāng)圖G不是二部圖時(shí)，它的鄰接矩陣A的最小特征值對(duì)應(yīng)的特征向量，也會(huì)出現(xiàn)有正分量和負(fù)分量同時(shí)存在的情況，所以僅由特征向量分量的符號(hào)來(lái)判斷圖G是否為二部圖還不夠，還要再判斷由上一步驟劃分的兩個(gè)頂點(diǎn)集合間存在的邊數(shù)是否等于圖G的總邊數(shù)，如果相等則說明同一頂點(diǎn)集中沒有邊，圖形G是二部圖。

(6)，

其中m為圖的邊數(shù)。

由矩陣法判定圖4兩個(gè)圖形是否為二部圖。

圖4

解得其最小特征值λmin=-2.44949

對(duì)應(yīng)的特征向量

v=(1,-1.22474,-1.22474,1,1)T

依據(jù)v中各分量的符號(hào)寫出向量

S=(1,-1,-1,1,1T，將S，A代入公式⑥

解得兩點(diǎn)集間邊數(shù)R=6=m

解得其最小特征值λmin=-2.17741

對(duì)應(yīng)的特征向量v=(1.45926,-1.55887,-1.55887,1,1)T

依據(jù)v中各分量的符號(hào)寫出向量S=(1,-1,-1,1,1?T，將S，A代入公式6

解得兩點(diǎn)集間邊數(shù)R=1≠m

因此，圖形(b)不是二部圖。

〔參考文獻(xiàn)〕

[1]屈婉玲，耿素云，張立昂. 離散數(shù)學(xué)[M]. 北京：高等教育出版社，2008.

[2]李小強(qiáng)，張寧. 應(yīng)用特征值判別二部圖的方法[J].科技資訊，2010,(12).

[3]陳躍輝，二部圖的鄰接矩陣的特征[J]. 漳州師范學(xué)院學(xué)報(bào)(自然科學(xué)版),1996,(2).

[4]劉曉輝，張超權(quán).非負(fù)不可約矩陣最大特征值的迭代算法[J].桂林航天工業(yè)高等?？茖W(xué)校學(xué)報(bào)，2007,(1).

The Methods of Decision and Properties of the Bipartite Graph

LU Fang

(Faculty of Mathematics, Baotou Teachers College; Baotou 014030)

Abstract:This article applied three methods in the decision of bipartite graph,one is labeling method that is from definition,the second is to use the decided theorem to decide. And the third is to use the adjacent matrix. and apply them to the instance graphic shows that these methods are effective.

Key words:bipartite graph; decision; matrix

中圖分類號(hào)：O157.5

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1004-1869(2015)01-0005-03

作者簡(jiǎn)介：路芳(1970-)，女，山東長(zhǎng)清人，副教授，研究方向：計(jì)算機(jī)軟件與理論。

收稿日期：2014-11-04