概述
欧拉图及欧拉路径
- 欧拉图
- 如果图G上有一条经过所有顶点、所有边的闭路径（边不重复，顶点可以重复）
- 充分必要条件
- 无向图：G连通，所有顶点的度都是偶数
- 有向图：G弱连通，每个顶点出度与入度相等
- 欧拉路径
- 如果图G上有一条经过所有顶点、所有边的路径（边不重复，顶点可以重复）
- 充分必要条件
- 无向图：G连通，恰有两个顶点的度是奇数
- 有向图：G连通，恰有两个顶点的出度与入度不相等，其中一个出度比入度多1，另一个入度比出度多1。
哈密顿图及哈密顿通路
- 哈密顿图
- 如果图G上有一条经过所有顶点的回路（不要求经过所有的边，也称作哈密顿回路）
- 充分非必要条件：如果具有n个顶点的图G的每一对顶点度数之和不小于n，且n>=3
哈密顿通路
- 如果图G上有一条经过所有顶点的通路（非回路）
- 充分非必要条件：如果具有n个顶点的图G的每一对顶点度数之和不小于n-1，那么G中有一条哈密顿通路
哈密顿通路问题在上世纪七十年代被证明是“NP完全的”
图的连通性
- u可达v
- u=v或存在一条u到v的路径
- 连通的无向图
- 无向图中的任意两个顶点都是可达的
- 连通的有向图
- 有向图中的任意两个顶点都是互相可达的
- 单向连通的有向图
- 任意两个顶点至少从一个顶点到另一个顶点是可达的
- 弱连通的有向图
- 将有向图看作是无向图时是连通的
最后
以上就是酷酷乌冬面为你收集整理的欧拉图和哈密顿图的全部内容，希望文章能够帮你解决欧拉图和哈密顿图所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复