哈密顿路径
定义
结果
由于确定是否存在哈密顿路径的问题与其他非常困难的问题是等价的,所以期望这样一条路径存在的必要和充分条件是很容易的。直观地说,如果相对于顶点的数量有“足够的”边,哈密顿路径就应该存在,因此许多充分条件给出了边的数量的下界。但它们不是必须的:会有一些图的哈密顿路径或循环位于这些条件的界限之外。
一个简单的图是这样一种图,任意两个不同的顶点之间最多有一条边,并且没有环路(开始和结束于同一顶点的边)。
的关闭图表上的 顶点的获取方法如下:找到一对顶点之间没有边,且其度数之和至少为 .在它们之间画一条边。继续,直到你找不到更多这样的配对。(练习:表明无论以何种顺序选择哪对组合,该过程都会产生相同的图。)
狄拉克,1952:一个简单的图(在任意一对顶点之间没有多条边,并且没有以同一顶点开始和结束的边) 如果每个顶点至少有次,则每个顶点都有一个哈密顿循环 .
矿石,1960:一个图表上 具有任意两个非相邻顶点的度数之和为的性质的顶点 有一个哈密顿循环。
Bondy-Chvatal, 1972:当且仅当图的闭包具有哈密顿环时,图具有哈密顿环。
注意,bondi - chvatal暗示了Ore,因为Ore定理中的图的闭包是完全图 每对顶点都由一条边连接,当然是完全图 顶点有一个哈密顿循环。
Ore意味着狄拉克,因为如果每个顶点都至少有度 ,则任意两个非相邻顶点的度数之和为 .
这些定理都不适用于,例如,循环 在 顶点,其中每个顶点都有度数 和结束 = :