证明图中是否有哈密顿回路并利用定义证明是否是哈密顿图的方法

邓联龙

摘要：哈密顿回路是一个初级回路，而且是图中最大的初级回路。我们可以通过寻找图中最大的初级回路，判断它是不是一个哈密顿回路，如果是，则图中有哈密顿回路，如果不是，则没有哈密顿回路。所以我一共有三个主要的论点：1、初级回路中如果有两点不相邻还可以连线，那么这条连线可以把这个初级回路分为更小的初级回路，直到图内没有不相邻的两点相连。（这种最小的初级回路，我称为“最小泡泡”）2、“最小泡泡”能够通过相邻的边合并成更大的初级回路，直至无法合并成更大的初级回路。（这种初级回路我称为“极大的初级回路”，图中可能不止一个极大的初级回路。）3、极大的初级回路如果包含了图中所有的点，则是哈密顿回路，如果没有包括所有的点，则不是哈密顿回路。

关键词：最小泡泡;边合并;极大的初级回路

0引言

哈密顿回路是一个初级回路，而且是图中最大的初级回路。我们可以通过寻找图中最大的初级回路，判断它是不是一个哈密顿回路，如果是，则图中有哈密顿回路，如果不是，则没有哈密顿回路。下面就笔者的论点进行介绍。

1论点一：初级回路中如果有两点不相邻还可以连线，那么这条连线可以把这个初级回路分为更小的初级回路，直到图内没有不相邻的两点相连。这种最小的初级回路，我称为“最小泡泡”。

如图是一个初级回路，中间两点尚未连接但是图中存在这条线，是存在图中却不存在于回路中的线。……