欧拉图与哈密顿图
欧拉图
哈密顿图
定义
欧拉回路
欧拉图
欧拉通路
通过所有边一次且仅一次
行遍所有顶点
通过所有边一次且仅一次
行遍所有顶点
具有欧拉回路
半欧拉图
具有欧拉通路而没有欧拉回路
定理
无向图
连通图
没有奇度顶点
有向图
欧拉图
强连通
每个顶点的入度等于出度
半欧拉图
单向连通
恰有两个奇度顶点
一个顶点的入度比出度大1
另一个顶点的出度比入度大1
其余顶点的入度等于出度
Fleury算法
在图中找到所有边不重合的“小”回路
将第一步找到的“小”回路作为相应顶点的圈，到时候在“大”回路里绕一下就行
定义
必要条件，只能判断一个图不是哈密顿图，而不能证明是哈密顿图
哈密顿通路
通过所有顶点一次且仅一次的通路
哈密顿回路
通过所有顶点一次且仅一次的回路
哈密顿图
半哈密顿图
具有哈密顿回路的图
具有哈密顿通路而没有回路
无向图
环不影响图的欧拉性
环与平行边不影响哈密顿性
实质是能将图中的所有顶点排在同一个圈上
如果一个图是半哈密顿图，对于任意包含于图中的顶点集合（其实找一半就行），原图去掉顶点集合后剩下的连通分量的个数小于等于这个顶点集合中顶点的个数 + 1
如果一个图是哈密顿图，则对于任意包含于图中的顶点集合（其实找一半就行），原图去掉顶点集合后剩下的连通分量的个数小于等于这个顶点集合中顶点的个数
K(r, s)当r = s时才可能是哈密顿图
彼得松图虽然满足条件但不是哈密顿图
轮图（外围节点度数是3，中心节点度数是n-1)是哈密顿图
定理
充分条件
无向图
在任意n阶无向简单图中任意两个不相邻顶点度数之和>=n-1，则有哈密顿通路
推论
在n>=3的n阶无向简单图中对于任意两个不相邻的顶点度数之和>=n,则存在哈密顿回路，即为哈密顿图
n阶无向简单图G中两个不相邻的顶点，度数之和>=n,且G并上(u,v)为哈密顿
图，则G是哈密顿图
注：长度为n-1（n>=4)的路径构成的图不满足上述条件，但是半哈密顿图
长度是n的圈不满足上述条件，但依然是哈密顿图
n（n>=3)阶无向完全图均是哈密顿图
n阶竞赛图中存在哈密顿通路