二部图的几种判别方法



二部图的几种判别方法

路芳

(包头师范学院 数学科学学院，内蒙古 包头 014030)

摘要：介绍了三种对二部图进行判别的方法，并将它们应用于实例图形，表明这些方法都是可行且有效的。其中，矩阵法的理论依据是：对于任意一个连通二部图的邻接矩阵，其最小特征值所对应的特征向量的各分量是非零的，而且同号分量对应着同一类顶点。

关键词：二部图；判别；矩阵

二部图又叫作二分图，是图论中的一种特殊图形。其定义是：若能将无向图G=的顶点集合V分成两个子集V1和V2, 这两个子集满足V1∪V2=V,V1∩V2=Φ,且G中任意一条边e=(u,v),都有u(或v)∈V1,且v(或u)∈V2,则G是二部图，记为G=?V1?V2?E?。图1所示，(a)中是一个二部图，顶点集为V={a,b,c,d,e,f},V1={a,d,e},V2={b,c,f},且满足任意一条边的两个端点，一个属于V1，另一个属于V2。图1(b)不是二部图。

图1

二部图在实际问题中有广泛的应用，比如“考试安排”，“资源分配”等问题的求解，都要用到二部图的知识，因此，二部图的判别是一个相对重要的问题。本文就判断一个无向连通图是二部图的三种方法进行了研究和总结。

本文只研究简单无向连通图，对于非连通图, 可以分别在不同的连通分支中应用判别方法。

1．定义法

二部图的定义：设G=(V,E)是一个无向图，如果顶点集合V可以分为两个互不相交的子集V1,V2，并且图中的每一条边e=(u，v),其两个端点u和v分别属于这两个不同的顶点集，则称图G是一个二部图。依照此定义判断图形能否画成互补顶点集的形式来判别其是否是二部图。但这种方法必须再画一个与待判别图形同构的新的图形，换一种形式，可以在原图形上标示符号来达到相同的效果。

在G中任找一点u，将其标定为A，与u点相邻的所有的点标定为B，再将与标定为B的点相邻的点标定为A，以此类推，若能把所有的点都标定好，则G是二部图，若出现标定为同字母的两点相邻的情况，则G不是二部图。

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

图2

2．定理法

判定定理： 一个无向图G=是二部图当且仅当G中无奇数长度的圈。即G至少有两个顶点，且其所有圈的长度均为偶数。

证明：先证必要性

设G为二部图，由于V1,V2非空，所以G中至少有两个顶点。若G中没有回路，则结论显然成立。若G中有回路，下边证明G中没有长度为奇数的圈。设C为G中任意一个圈，令c=v0v1v2…vtv0，其中，若有vi∈V1(i为奇数)，则一定有vj∈V2(j为偶数)，因此，t必为奇数，从而c的长度为t+1，是偶数，即c为偶圈。

再证充分性

V1∪V2=V(G),下边只要证明V1中任意两点不相邻，V2中任意两点也不相邻。若存在vi,vj∈V1,且有(vi,vj)=e,e∈V(E),设v0到vi,vj的距离分别为l1,l2,则它们的长度d(v0,vi),d(v0,vj)都是偶数，于是回路v0,…vi,vj,…v0的长度是奇数。若是圈则为奇数长度的圈，这与条件相矛盾，类似地可以证明，V2中也不存在相邻的顶点，于是G为二部图。

由判定定理可知，图3中(a)中没有奇圈，(b)中没有圈，两个图都是二部图

图3

3．矩阵法

相关定理(Perron Frobenus)设A是n阶不可约非负矩阵，则

(1)A的谱半径ρ是A的特征值；

(2)A有一个对应于ρ的正特征向量；

(3)A关于ρ的代数重数multρ(A)等于1，即ρ是A的特征多项式的单根。

判定方法：

利用二部图的邻接矩阵的特征向量的性质：最小特征值对应的向量的分量符号与相应顶点所在的点集有关，同号分量对应的点在同一个点集中，利用这个特点可以把顶点集合V划分成V1和V2。但在非二部图中，最小特征值对应的特征向量也会存在正负分量，所以，还要进一步计算与边数有关的参数t，当t与边数m相等时，可以确定图形G是二部图。

理论依据：

设矩阵A=(aij)m×n是图G的邻接矩阵，当图G为二部图时，A可通过置换变成如下形式：

(1)

其中分块矩阵B仅由0,1元素构成。

设邻接矩阵A的特征值是λ，特征方程为

Ax=λx2

(2)

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

进而得到

BBTx1=λ2x13

(3)

BTBx2=λ2x24

(4)

也就是有A2x=λ2x

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

由矩阵的对称性可以判断矩阵BBT，BTB是实对称矩阵，而且都是不可约的。因为若BBT为可约矩阵，则有

(5)

而A2中的元素aij表示G图中与vi和vj都相邻的顶点数，而5式说明点集V中存在着某些点与其它点没有相同的邻点，这与图G是连通图相矛盾，所以矩阵BBT是不可约的，同理BTB也是不可约矩阵。

由3和4两个公式可知，邻接矩阵A的最小特征值对应的特征向量x的两个分量x1,x2，应该是一个正的，一个负的向量。所有正的分量对应的顶点在同一个点集中，负的分量对应的顶点的另一个点集当中，这样可以将图G的顶点集合划分成两个不相交的集合。

当图G不是二部图时，它的邻接矩阵A的最小特征值对应的特征向量，也会出现有正分量和负分量同时存在的情况，所以仅由特征向量分量的符号来判断图G是否为二部图还不够，还要再判断由上一步骤划分的两个顶点集合间存在的边数是否等于图G的总边数，如果相等则说明同一顶点集中没有边，图形G是二部图。

(6)，

其中m为图的边数。

由矩阵法判定图4两个图形是否为二部图。

图4

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

对应的特征向量

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

依据v中各分量的符号写出向量

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

解得两点集间边数R=6=m

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

对应的特征向量v=(1.45926,-1.55887,-1.55887,1,1)T

依据v中各分量的符号写出向量S=(1,-1,-1,1,1?T，将S，A代入公式6

解得两点集间边数R=1≠m

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

〔参考文献〕

[1]屈婉玲，耿素云，张立昂. 离散数学[M]. 北京：高等教育出版社，2008.

[2]李小强，张宁. 应用特征值判别二部图的方法[J].科技资讯，2010,(12).

[3]陈跃辉，二部图的邻接矩阵的特征[J]. 漳州师范学院学报(自然科学版),1996,(2).

[4]刘晓辉，张超权.非负不可约矩阵最大特征值的迭代算法[J].桂林航天工业高等专科学校学报，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

中图分类号：O157.5

文献标识码：A

文章编号：1004-1869(2015)01-0005-03

作者简介：路芳(1970-)，女，山东长清人，副教授，研究方向：计算机软件与理论。

收稿日期：2014-11-04