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