第十五章欧拉图与哈密顿图
欧拉图
15.1 1736年数学家欧拉发表了第一篇图论论文,解诀了哥尼斯堡七桥问题。
?
定义(欧拉通路和欧拉回路)
通过图(无向图或有向图)中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路
通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路
定义(欧拉图和半欧拉图)
具有欧拉回路的图称为欧拉图
具有欧拉通路无欧拉回路的图称为半欧拉图规定平凡图是欧拉图
例
(1)(2)(3)
(4)(5)(6)
1)为欧拉图。2)为半欧拉图。
3)即不存在欧拉通路,也不存在欧拉回路。4)为欧拉图。
5)即不存在欧拉通路,也不存在欧拉回路。6)即不存在欧拉通路,也不存在欧拉回路。
((((((
离散数学15 欧拉图与哈密顿图
第十五章欧拉图与哈密顿图欧拉图15.11736年数学家欧拉发表了第一篇图论论文,解诀了哥尼斯堡七桥问题。?定义(欧拉通路和欧拉回路)通过图(无向图或有向图)中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路定义(欧拉图和半欧拉图)<
推荐度:
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
点击下载文档文档为doc格式