加拿大硕士预科-铜陵学院分数线

广西民族学院学报(自然科学版)
第7卷第1期 JOURNALOFG UANGXIUNIVERSITYFORNATIONALITIESVol.7No.1
2001年 2月(NaturalScienceEdition) Feb.2001
文章编号:1007-0311(2001)01-0009-02
用矩阵判断哈密顿图的一个 充要条件
姚源果
(广西右江民族师范高等专科学校数学系,广西百色 533000)
*
摘 要:
给出了一个从图的邻接矩阵来判断有限无向连通图是否是哈 密顿图的充分必要条件.
关键词:
图论;哈密顿图;邻接矩阵;充要条件
中图分类号:
O151121
文献标识码:
A
寻找一个像判断欧拉图那样简单的 充要条件来
判断哈密顿图是非常困难的,判断哈密顿图的充要条
件仍然是图论中尚未解决的问题 .既然图论与计算机
联系的纽带是矩阵,那么可以设想通过矩阵来寻求一
个判断哈密顿图的充要 条件.
1 定义
定义1 设G=3V,E4是有限无向图,点集V
的元数为n,如果n 阶正方矩阵A(G)=[b
ij
]满足下
面条件:
b
ij
=
0, 当v
i
与v
j
不相邻
1, 当v
i与v
j
相邻
W(A)=
jj
,j
12
图1 无向连通图A
定义2 设A=[a
ij
]是一个n阶方阵,若
E
a< br>1j
1
a
2j
2
,a
nj
n
(其中 j
1
j
2
,j
n
是1,2,
n
3,,,n 的所有全排列且和式中任意一项不能同时出
现b
ij
和b
ji
),则 称W(A)为矩阵A的奇异和.
则A(G)称为图G的邻接矩阵.
例1 图1所示图G的邻接矩 阵为
01111
1
A(G)=1
1
1
0
1
0
0
10
01
10
11
0
1
1
0
2 定理及证明
定理1 设G=3V,E4是一个没有自回路的有
限无向连通图,V的 元数为n,A(G)=[b
ij
](i,j=
1,2,3,,,n)是G的邻接矩阵, 则G是哈密顿图的
充分必要条件是A(G)的奇异和W(A)不等于0.
证明: 必要性(]) 若图G是哈密顿图,则G
存在一条哈密顿回路,不妨设这条哈密顿回路为
*
收稿日期:
2000-08-15.
作者简介:
姚源果(1974-),男,广西田林人,广西右 江民族师范高等专科学校数学系助教.
9

广西民族学院学报(自然科学版) 2001年2月 第7卷
(v
1
,v
2
,v
3
,, v
n
,v
1
),即v
1
与v
2
,v
2
与v
3
,v
3
与
v
4
,,v
n-1
与v
n
,v
n
与v
1
都有边相连.A(G) =[b
ij
]
是G的邻接矩阵,所以b
12
=b
23
=b
34
=,=b
n-
=b
n1
=1,即b
12
b
23
b
34
,b
n-1n
b
n1
1n
所以W(A(G
1
))=X0
即图G
1
是哈密顿 图
(2)图2的邻接矩阵
0001
0
0
A(G
2
) =
1
0
1
00
00
10
11
00
1
0
0
0
1
0
1
1
0
0
0
1
1
10
00
00
11
01
00
00
00
=1.
由邻接矩阵的定义知,任意b
ij
=1或0.所以
W(A(G))X0.
充分性(a) A(G)=[b
ij
]是G的邻接矩阵 ,
若W(A(G))X0,而这个和式和每一项都是1或0,
所以必存在某一项为1,假设b< br>1j
1
b
2j
2
,b
nj
n
=1则 有
b
1j
1
=b
2j
2
=,=b
njn
=1
所以在图G中,存在n条边:
(v
1
-v
j1
),(v
2
-v
j
2
),,,(v
n
-v
j
n
)
因图G没有自回路,则1Xj
1
,2Xj2
,,,nXj
n
.而
j
1
,j
2
, ,,j
n
互不相等,是1,2,,,n的全排列,且b
ij
各b
ji
不同时出现,即上述n条边不重复.显然上述n
条边能构成一条哈密顿回路,即图G是哈密顿图 .
0001
0010
所以W(A(G
2
))=0
即图G
2
不是哈密顿图.
4 结 论
定理1虽然只是给出没有自回路的有限无向连
通图是否是哈密顿图的判断条件,但对于存在自 回路
的图只要将自回路删除即可,因为自回路不能作为哈
密顿回路的一部分,对判断哈密顿图没 有任何影响.
再者,如果是有向图,也可完全使用定理1,只要注意
一下邻接矩阵的定义就可以 了.
使用矩阵来判断一个图是否是哈密顿图肯定不
够直观,甚至更复杂,但对于计算机来说却是 方便处
理,事实上,依照定理1很容易编写一段计算机程序
来判断任意图是否是哈密顿图.3 例题
例2 判断下面图2和图3是否是哈密顿图.图
2无向连通图B图3无向连通图C
图2 无向连通图B 图3 无向连通图C
解:(1)图1的邻接矩阵
0
1
1
A(G
1
)=0
0
1
0
1
0
1
0
0< br>0
1
10
10
01
10
11
01
0 0
0
0
1
1
0
0
1
1
0
0
1
0
0
1
0
1
0
0
1
1
0
[参 考 文 献]
[1]马振华.离散数学导引[M].北京:清华大学出版社 ,1993.
[2]前田渡,伊东正安.陶思雨,王缉惠译.现代图论基础[M].北京:
高等 教育出版社,1987.
[责任编辑 黄祖宾]
[责任校对 曹满仙]
Judging anEssentialandPrerequisiteConditionofHamitonDiagra mbyMatrix
YAOYuan-guo
(ematicsofYoujiangTeac hersCollegeforNationalitiesofGuangxi,Beise533000,C hina)
Abstract:
Provingwhetherfiniteconnecti vediagramwithoutdirectionistheessentialandprerequi sitecon-
ditionofHamitondiagrambycontiguousmatr ix.
KeyWords:
Diagramism;HamitonDiagram;Cont iguousMatrix;EssentialandPrerequisiteCondition
10