离散数学15 欧拉图与哈密顿图

第十五章欧拉图与哈密顿图

欧拉图

15.1 1736年数学家欧拉发表了第一篇图论论文，解诀了哥尼斯堡七桥问题。

?

定义（欧拉通路和欧拉回路）

通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路

通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路

定义（欧拉图和半欧拉图）

具有欧拉回路的图称为欧拉图

具有欧拉通路无欧拉回路的图称为半欧拉图规定平凡图是欧拉图

例

（1）（2）（3）

（4）（5）（6）

1）为欧拉图。2）为半欧拉图。

3）即不存在欧拉通路，也不存在欧拉回路。4）为欧拉图。

5）即不存在欧拉通路，也不存在欧拉回路。6）即不存在欧拉通路，也不存在欧拉回路。

（（（（（（