图的连通分支数的邻接矩阵判定

王晓

（商洛学院 数学与计算机应用学院，陕西商洛726000）

图的连通分支数的邻接矩阵判定

王晓

（商洛学院 数学与计算机应用学院，陕西商洛726000）

连通性是图的基本性质之一，由定义来判断顶点数和边数较大的图的连通性和连通分支数比较困难。结合图的邻接矩阵，给出判断图的连通性的两个充要条件，并给出判断图的连通分支数的一个充要条件和非负对称不可约矩阵的一个充要条件。

图的连通性；连通分支数；邻接矩阵

图的连通性[1-2]是图论中基本概念之一，设G=(V(G)，E(G))表示一个图，V(G)和E(G)分别表示图G的顶点集和边集。对u，v∈V(G)，图G中连接顶点u与v的点和边的交错序列称为uv链，内部点互不相同的链称为路。图G中若存在连接顶点u与v的路，则称u与v是连通的。顶点集V(G)上顶点之间的连通关系是等价关系，这种等价关系将V(G)分成等价类V1，V2，…，Vω，使得u，v∈Vi当且仅当u和v是连通的。这些顶点子集的导出子图G[V]1，G[V]2，…，G[V]ω称为图G的连通分支，ω称为连通分支数，记为ω(G)。若ω(G)=1则称为连通图，否则称为非连通图。

图的连通性是图论中研究的经典问题，一直是国内外学者研究[3-5]的重点,图的很多性质都与它连通性密切相关[6-8]。对于结构简单的图判断其连通性及连通分支数利用定义即可，但对于顶点和边数较多的图来说，就比较困难，尤其不利于应用计算机程序来解决。图的邻接矩阵是研究图的代数性质很好工具[9-10]。本文利用图的邻接矩阵，给出判断图的连通性的两个充要条件，并给出判断图的连通分支数的一个充要条件，最后给出判断非负对称不可约矩阵的一个充要条件。

1 图的连通性的判定

图G=(V(G)，E(G))的顶点集为

V(G)={v1，v2，…，Vn}，则图G的邻接矩阵为

A(G)=(aij)n×n，其中，由此，给出判断图的连通性的两个充要条件。

命题1设A(G)为图G的邻接矩阵,则n(≥2)阶图G是连通图的充要条件是(En+A)n-1＞0。

证明由于,即。

Akij表示连接顶点vi和vj的长为k的链的个数,故图G是连通图时,对G中任意两点vi与vj有路相连(i=j时有链相连)。因此必存在k∈{1，2，…，n-1},使得Akij＞0(对i=j有A0ii=Eii＞0),所以,,即(En+A)n-1＞0。

反之,由(En+A)n-1＞0,必存在k∈{1，2，…，n-1},使得Akij＞0,即任意两点vi与vj有链相连,故图G是连通的。

设方阵A=(aij)n×n满足：当n=1时,A唯一的元素为零；当n≥2时,记N={1，2，…，n},若N存在非空真子集K使得当i∈N-K，j∈K时,有aij=0,则A称为可约矩阵,否则称为不可约矩阵[11]。由此，有如下判断图的连通性的另一个充要条件。

命题2设A(G)为G的邻接矩阵,则n(≥2)阶图G是连通图的充要条件是A(G)为不可约矩阵。

证明原命题的等价命题为：n(≥2)阶图G是不连通的充要条件是A(G)为可约方阵。

设V(G)={v1，v2，…，vk}，由于G是不连通的，不妨设G的一个连通分支为G′且V(G′)= {v1，v2，…，vk}，k＜n。令N={1，2，…，n}，K={1，2，…，k}。由于G′中的点与G-G′中的点都没有边相连，所以在图G的邻接矩阵中，当i∈N-K，j∈K时,有aij=0。因此，A(G)为可约矩阵。反之，若A(G)为n(≥2)阶可约矩阵，即存在N={1，2，…，n}的非空真子集K,使得当i∈N-K，j∈K时,有aij=0。设K={k1，k2，…，kr}，r＜n，记V={vk1，vk2，…，vkr}，则V中所有点与V(G)-V中的点都不相连。即图G是不连通的。

2 图的连通分支数的判定

首先给出由图的邻接矩阵来判定其连通分支数的一个结论。

命题3若图的邻接矩阵,其中Ai(i=1，…，r)为0或为阶至少是2不可约方阵,则ω(G)=r。

证明设子阵Ai的阶为mi,Ai对应的顶点为vi1，vi2，…，vimi其中i=1，…，r。若mi=1，即Ai=0，则从矩阵的行或列看，顶点vi1与其他顶点都不相连，故vi1为孤立点，为一平凡的连通分支。若mi≥2，即Ai为阶至少是2不可约方阵，顶点不与中任何点相连，由命题2，故顶点为G的一个连通分支。所以ω(G)=r。

定理1设A(G)为n阶图G的邻接矩阵，则ω(G)=r的充要条件是存在n阶置换矩阵P,使得,其中Ai(i=1，…，r)为0或为阶至少为2不可约方阵。

证明必要性：设V(G)={v1，v2，…，vn},由图G有r个连通分支G1，G2，…，Gr，其中V(Gi)={vi1，vi2，…，vimi},mi=｜V(Gi)｜,i=1，…，r。在图G的邻接矩阵中交换第i，j两列同时交换第两行，相当于将顶点vi和vj次序交换而原有连边关系不变。经过若干次这样的变换，可以把连通分支G1中的顶点对应的行和列移动到前m1个位置，依次为连通分支G2，…，Gr中顶点对应的行和列。每一次变换等价于对A(G)右乘对应的初等置换矩阵同时左乘该初等置换矩阵的逆。上述若干个变换对应的初等置换矩阵的乘积记为P,则P为n阶置换矩阵P,且有，A1，A2，…，Ar分别为连通分支G1，G2，…，Gr的邻接矩阵。由命题2，即Ai(i=1，…，r)为不可约方阵。

充分性：n阶置换矩阵P可表示为若干个初等置换矩阵的乘积，即设P=P1P2·…·Pl，则有。

故将图G经过l次的移动，可使得重新排序后对应的邻接矩阵为，由命题3，即ω(G)=r。

由命题1和命题2，考虑有平行边和自环的无向图，易得对于非负对称矩阵得出定理2。

定理2设A为n阶非负对称矩阵，则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].应用数学学报,2013,36(2)：204-208.

[4]陆鸣盛,沈成康.图的连通性快速算法[J].同济大学学报,2001,29(4)：436-439.

[5]赵孜泷.全局最短路径计算和图的连通性及拓扑排序在邻接矩阵的方法[J].软件导刊,2010,9(2)：59-60.

[6]王 晓,段 芳.单圈图的解析[J].华东师范大学学报：自然科学版,2009,143：13-21.

[7]汪小黎,王 晓.轮形图K1∨Cn和扇形图K1∨Pn的解析[J].商洛学院学报,2013,27(2)：5-7.

[8]陈兆均,刘德丰,全梅花,等.单侧连通图与强连通图的判定[J].大学数学,2005,21(2)：76-77.

[9]扈生彪.图的邻接矩阵的行列式与积和式的递推表达式[J].数学的实践与认识,2011,41(15)：222-227.

[10]邢永丽,陈维兵,阎真真.矩阵理论在其他数学学科中的应用[J].湘潭师范学院学报：自然科学版,2005,27(4)：14-16.

[11]程云鹏.矩阵论[M].西安：西北工业大学出版社,1998.

（责任编辑：李堆淑）

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

陕西省教育厅专项科研计划项目（12JK0889）

王 晓，男，河南南阳人，硕士，讲师