哈密顿图同构的证明

姜咏江

一个图是不是著名的哈密顿图？采用图的01表示方法可以做到。将当前顶点用1表示，与其相邻的顶点用0表示，并将它们放在一张表中，这就是图的01表示法。

1.               证明过程

要证明下面的图1和图2同构，只要将其中的一个图的0和1表达的表列出，并复制一个，然后清除表头的标注。表1是哈密顿图，表2是对图2的操作表。我们在表2中用排列图2顶点的方法来证明图2与图1同构。

表1  哈密顿图

1	2	3	4	5	6	7	8	9	10	11	12	13	x14	15	16	17	18	19	20
1	0			0			0
0	1	0							0
	0	1	0								0
		0	1	0									0
0			0	1	0
				0	1	0								0
					0	1	0									0
0						0	1	0
							0	1	0								0
	0							0	1	0
									0	1	0							0
		0								0	1	0
											0	1	0						0
			0									0	1	0
					0								0	1	0
														0	1	0			0
						0									0	1	0
								0								0	1	0
										0							0	1	0
												0			0			0	1

 

操作：

（1）在图2中选择一个圈。这里选的顶点是qrihg。

（2）按照q的邻点，添写p。

（3）按照r的邻点，添写s。

（4）按照i的邻点，添写j。

（5）按照h的邻点，添写a。

（6）按照g的邻点，添写f。

表2  选择圈排列

q	r	i	h	g	f		p		s		j		a
1	0			0			0
0	1	0							0
	0	1	0								0
		0	1	0									0
0			0	1	0
				0	1	0								0
					0	1	0									0
0						0	1	0
							0	1	0								0
	0							0	1	0
									0	1	0							0
		0								0	1	0
											0	1	0						0
			0									0	1	0
					0								0	1	0
														0	1	0			0
						0									0	1	0
								0								0	1	0
										0							0	1	0
												0			0			0	1

 

表2中有黄色底纹的中间位置应是图2边上两点关联的顶点。例如，f、p共同关联的顶点是o，这叫添写共同关联顶点。

（6）添写已经确定顶点的共同关联顶点（见表3的黄色位置）。

（7）依据图2顶点的相邻关系，添写剩余的顶点位置（见表4的绿色位置）。

表3  选择关联顶点

q	r	i	h	g	f	o	p	t	s	k	j	b	a			n
1	0			0			0
0	1	0							0
	0	1	0								0
		0	1	0									0
0			0	1	0
				0	1	0								0
					0	1	0									0
0						0	1	0
							0	1	0								0
	0							0	1	0
									0	1	0							0
		0								0	1	0
											0	1	0						0
			0									0	1	0
					0								0	1	0
														0	1	0			0
						0									0	1	0
								0								0	1	0
										0							0	1	0
												0			0			0	1

 

表4  图2的0和1表示

q	r	i	h	g	f	o	p	t	s	k	j	b	a	e	d	n	m	l	c
1	0			0			0
0	1	0							0
	0	1	0								0
		0	1	0									0
0			0	1	0
				0	1	0								0
					0	1	0									0
0						0	1	0
							0	1	0								0
	0							0	1	0
									0	1	0							0
		0								0	1	0
											0	1	0						0
			0									0	1	0
					0								0	1	0
														0	1	0			0
						0									0	1	0
								0								0	1	0
										0							0	1	0
												0			0			0	1

当所有的顶点在表中添写完成之后，需要认真核对各顶点之间的相邻关系是否与图2一致。若完全一致，则证明图1与图2同构。图1与图2的顶点与顶点，边与边的一一对应关系，可由表1和表4立即得到。

2.               总结

本例的原哈密顿图同构才用先找“圈”来确定一些相互关联的顶点位置，然后再依据多点共同关联的顶点，再确定那个顶点的位置，逐步扩充安排顶点的位置，可一次性得到结果。

在用图的01表示法中，可能产生顶点的不同排列顺序，但这并不影响对图同构的证明。产生这种情况的原因，是因为图定义本身没有图形位置的概念。

 

2016-04-08

 

参考：http://blog.sciencenet.cn/blog-340399-968548.html

             http://blog.sciencenet.cn/blog-340399-958453.html

 

 

 

转载本文请联系原作者获取授权，同时请注明本文来自姜咏江科学网博客。
链接地址：https://blog.sciencenet.cn/blog-340399-968644.html

上一篇：图同构01表示的多项式时间证明方法
下一篇：证明两个图同构的例题