哈密顿图
定义
通过图中所有顶点一次且仅一次的通路称为哈密顿通路。
通过图中所有顶点一次且仅一次的回路称为哈密顿回路。
具有哈密顿回路的图称为哈密顿图。
具有哈密顿通路而不具有哈密顿回路的图称为半哈密顿图。
性质
设
推论:设
完全图
完全图
充分条件
设
推论 1:设
推论 2:设
设
若
强连通的竞赛图为哈密顿图。
若
最后更新: May 6, 2023
创建日期: July 11, 2018
创建日期: July 11, 2018
通过图中所有顶点一次且仅一次的通路称为哈密顿通路。
通过图中所有顶点一次且仅一次的回路称为哈密顿回路。
具有哈密顿回路的图称为哈密顿图。
具有哈密顿通路而不具有哈密顿回路的图称为半哈密顿图。
设
推论:设
完全图
完全图
设
推论 1:设
推论 2:设
设
若
强连通的竞赛图为哈密顿图。
若