圖的連通分支數(shù)的鄰接矩陣判定

王曉

（商洛學(xué)院 數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院，陜西商洛726000）

圖的連通分支數(shù)的鄰接矩陣判定

王曉

（商洛學(xué)院 數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院，陜西商洛726000）

連通性是圖的基本性質(zhì)之一，由定義來判斷頂點(diǎn)數(shù)和邊數(shù)較大的圖的連通性和連通分支數(shù)比較困難。結(jié)合圖的鄰接矩陣，給出判斷圖的連通性的兩個(gè)充要條件，并給出判斷圖的連通分支數(shù)的一個(gè)充要條件和非負(fù)對(duì)稱不可約矩陣的一個(gè)充要條件。

圖的連通性；連通分支數(shù)；鄰接矩陣

圖的連通性[1-2]是圖論中基本概念之一，設(shè)G=(V(G)，E(G))表示一個(gè)圖，V(G)和E(G)分別表示圖G的頂點(diǎn)集和邊集。對(duì)u，v∈V(G)，圖G中連接頂點(diǎn)u與v的點(diǎn)和邊的交錯(cuò)序列稱為uv鏈，內(nèi)部點(diǎn)互不相同的鏈稱為路。圖G中若存在連接頂點(diǎn)u與v的路，則稱u與v是連通的。頂點(diǎn)集V(G)上頂點(diǎn)之間的連通關(guān)系是等價(jià)關(guān)系，這種等價(jià)關(guān)系將V(G)分成等價(jià)類V1，V2，…，Vω，使得u，v∈Vi當(dāng)且僅當(dāng)u和v是連通的。這些頂點(diǎn)子集的導(dǎo)出子圖G[V]1，G[V]2，…，G[V]ω稱為圖G的連通分支，ω稱為連通分支數(shù)，記為ω(G)。若ω(G)=1則稱為連通圖，否則稱為非連通圖。

圖的連通性是圖論中研究的經(jīng)典問題，一直是國內(nèi)外學(xué)者研究[3-5]的重點(diǎn),圖的很多性質(zhì)都與它連通性密切相關(guān)[6-8]。對(duì)于結(jié)構(gòu)簡單的圖判斷其連通性及連通分支數(shù)利用定義即可，但對(duì)于頂點(diǎn)和邊數(shù)較多的圖來說，就比較困難，尤其不利于應(yīng)用計(jì)算機(jī)程序來解決。圖的鄰接矩陣是研究圖的代數(shù)性質(zhì)很好工具[9-10]。本文利用圖的鄰接矩陣，給出判斷圖的連通性的兩個(gè)充要條件，并給出判斷圖的連通分支數(shù)的一個(gè)充要條件，最后給出判斷非負(fù)對(duì)稱不可約矩陣的一個(gè)充要條件。

1 圖的連通性的判定

圖G=(V(G)，E(G))的頂點(diǎn)集為

V(G)={v1，v2，…，Vn}，則圖G的鄰接矩陣為

A(G)=(aij)n×n，其中，由此，給出判斷圖的連通性的兩個(gè)充要條件。

命題1設(shè)A(G)為圖G的鄰接矩陣,則n(≥2)階圖G是連通圖的充要條件是(En+A)n-1＞0。

證明由于,即。

Akij表示連接頂點(diǎn)vi和vj的長為k的鏈的個(gè)數(shù),故圖G是連通圖時(shí),對(duì)G中任意兩點(diǎn)vi與vj有路相連(i=j時(shí)有鏈相連)。因此必存在k∈{1，2，…，n-1},使得Akij＞0(對(duì)i=j有A0ii=Eii＞0),所以,,即(En+A)n-1＞0。

反之,由(En+A)n-1＞0,必存在k∈{1，2，…，n-1},使得Akij＞0,即任意兩點(diǎn)vi與vj有鏈相連,故圖G是連通的。

設(shè)方陣A=(aij)n×n滿足：當(dāng)n=1時(shí),A唯一的元素為零；當(dāng)n≥2時(shí),記N={1，2，…，n},若N存在非空真子集K使得當(dāng)i∈N-K，j∈K時(shí),有aij=0,則A稱為可約矩陣,否則稱為不可約矩陣[11]。由此，有如下判斷圖的連通性的另一個(gè)充要條件。

命題2設(shè)A(G)為G的鄰接矩陣,則n(≥2)階圖G是連通圖的充要條件是A(G)為不可約矩陣。

證明原命題的等價(jià)命題為：n(≥2)階圖G是不連通的充要條件是A(G)為可約方陣。

設(shè)V(G)={v1，v2，…，vk}，由于G是不連通的，不妨設(shè)G的一個(gè)連通分支為G′且V(G′)= {v1，v2，…，vk}，k＜n。令N={1，2，…，n}，K={1，2，…，k}。由于G′中的點(diǎn)與G-G′中的點(diǎn)都沒有邊相連，所以在圖G的鄰接矩陣中，當(dāng)i∈N-K，j∈K時(shí),有aij=0。因此，A(G)為可約矩陣。反之，若A(G)為n(≥2)階可約矩陣，即存在N={1，2，…，n}的非空真子集K,使得當(dāng)i∈N-K，j∈K時(shí),有aij=0。設(shè)K={k1，k2，…，kr}，r＜n，記V={vk1，vk2，…，vkr}，則V中所有點(diǎn)與V(G)-V中的點(diǎn)都不相連。即圖G是不連通的。

2 圖的連通分支數(shù)的判定

首先給出由圖的鄰接矩陣來判定其連通分支數(shù)的一個(gè)結(jié)論。

命題3若圖的鄰接矩陣,其中Ai(i=1，…，r)為0或?yàn)殡A至少是2不可約方陣,則ω(G)=r。

證明設(shè)子陣Ai的階為mi,Ai對(duì)應(yīng)的頂點(diǎn)為vi1，vi2，…，vimi其中i=1，…，r。若mi=1，即Ai=0，則從矩陣的行或列看，頂點(diǎn)vi1與其他頂點(diǎn)都不相連，故vi1為孤立點(diǎn)，為一平凡的連通分支。若mi≥2，即Ai為階至少是2不可約方陣，頂點(diǎn)不與中任何點(diǎn)相連，由命題2，故頂點(diǎn)為G的一個(gè)連通分支。所以ω(G)=r。

定理1設(shè)A(G)為n階圖G的鄰接矩陣，則ω(G)=r的充要條件是存在n階置換矩陣P,使得,其中Ai(i=1，…，r)為0或?yàn)殡A至少為2不可約方陣。

證明必要性：設(shè)V(G)={v1，v2，…，vn},由圖G有r個(gè)連通分支G1，G2，…，Gr，其中V(Gi)={vi1，vi2，…，vimi},mi=｜V(Gi)｜,i=1，…，r。在圖G的鄰接矩陣中交換第i，j兩列同時(shí)交換第兩行，相當(dāng)于將頂點(diǎn)vi和vj次序交換而原有連邊關(guān)系不變。經(jīng)過若干次這樣的變換，可以把連通分支G1中的頂點(diǎn)對(duì)應(yīng)的行和列移動(dòng)到前m1個(gè)位置，依次為連通分支G2，…，Gr中頂點(diǎn)對(duì)應(yīng)的行和列。每一次變換等價(jià)于對(duì)A(G)右乘對(duì)應(yīng)的初等置換矩陣同時(shí)左乘該初等置換矩陣的逆。上述若干個(gè)變換對(duì)應(yīng)的初等置換矩陣的乘積記為P,則P為n階置換矩陣P,且有，A1，A2，…，Ar分別為連通分支G1，G2，…，Gr的鄰接矩陣。由命題2，即Ai(i=1，…，r)為不可約方陣。

充分性：n階置換矩陣P可表示為若干個(gè)初等置換矩陣的乘積，即設(shè)P=P1P2·…·Pl，則有。

故將圖G經(jīng)過l次的移動(dòng)，可使得重新排序后對(duì)應(yīng)的鄰接矩陣為，由命題3，即ω(G)=r。

由命題1和命題2，考慮有平行邊和自環(huán)的無向圖，易得對(duì)于非負(fù)對(duì)稱矩陣得出定理2。

定理2設(shè)A為n階非負(fù)對(duì)稱矩陣，則A為不可約矩陣的充要條件是(En+A)n-1＞0。

[1]Bondy J A,Murty U S R.Graph Theory With Applications[M].Macmillan,London and Elsevier,New York,1976.

[2]Chris Godsil,Gordon Royle,Algebraic Graph Theory[M].Springer-Verlag New York,2001.

[3]郭利濤,覃城阜,郭曉峰.n-double圖的連通性[J].應(yīng)用數(shù)學(xué)學(xué)報(bào),2013,36(2)：204-208.

[4]陸鳴盛,沈成康.圖的連通性快速算法[J].同濟(jì)大學(xué)學(xué)報(bào),2001,29(4)：436-439.

[5]趙孜瀧.全局最短路徑計(jì)算和圖的連通性及拓?fù)渑判蛟卩徑泳仃嚨姆椒╗J].軟件導(dǎo)刊,2010,9(2)：59-60.

[6]王 曉,段 芳.單圈圖的解析[J].華東師范大學(xué)學(xué)報(bào)：自然科學(xué)版,2009,143：13-21.

[7]汪小黎,王 曉.輪形圖K1∨Cn和扇形圖K1∨Pn的解析[J].商洛學(xué)院學(xué)報(bào),2013,27(2)：5-7.

[8]陳兆均,劉德豐,全梅花,等.單側(cè)連通圖與強(qiáng)連通圖的判定[J].大學(xué)數(shù)學(xué),2005,21(2)：76-77.

[9]扈生彪.圖的鄰接矩陣的行列式與積和式的遞推表達(dá)式[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2011,41(15)：222-227.

[10]邢永麗,陳維兵,閻真真.矩陣?yán)碚撛谄渌麛?shù)學(xué)學(xué)科中的應(yīng)用[J].湘潭師范學(xué)院學(xué)報(bào)：自然科學(xué)版,2005,27(4)：14-16.

[11]程云鵬.矩陣論[M].西安：西北工業(yè)大學(xué)出版社,1998.

（責(zé)任編輯：李堆淑）

Judgment for Number of Connected Com ponents of Graph with Adjacency Matrix

WANG Xiao
(College of Mathematics and Computer Application,Shangluo University,Shangluo 726000,Shaanxi)

The connectivity is one of the basic properties for a graph.It is difficult to judge the number of connected component for graphs which have a large number of vertices and edges.With adjacency matrix of graphs,two necessary and sufficient conditions on the connectivity for graphs are given,a necessary and sufficient condition on judgment of the number of connected components for a graph is obtained,a necessary and sufficient condition on non-negative symmetric irreducible matrix is given.

connectivity of graphs；number of connected component；adjacency matrix

O157.5

：A

：1674-0033（2014）06-0006-02

10.13440/j.slxy.1674-0033.2014.06.002

2014-09-25

陜西省教育廳專項(xiàng)科研計(jì)劃項(xiàng)目（12JK0889）

王 曉，男，河南南陽人，碩士，講師