欧拉图 离散数学一图论初步 南京大学计算机科学与技术系
欧拉图 离散数学─图论初步 南京大学计算机科学与技术系
殼壁嘉 内容提要 ●欧拉通路/回路 ●欧拉图的充要条件 。构造欧拉回路的Fleury2算法 ●哈密尔顿通路回路 。哈密尔顿图的必要和充分条件 ·哈密尔顿图的应用
内容提要 欧拉通路/回路 欧拉图的充要条件 构造欧拉回路的Fleury算法 哈密尔顿通路/回路 哈密尔顿图的必要和充分条件 哈密尔顿图的应用
线兔 Konigsberg-七桥问题 707 。问题的抽象： ●用顶点表示对象“地块” 。用边表示对象之间的关系“有桥相连” 。原问题等价于：“右边的图中是否存在包含每条边 一次且恰好一次的回路？” B
Königsberg七桥问题 问题的抽象： 用顶点表示对象-“地块” 用边表示对象之间的关系-“有桥相连” 原问题等价于：“右边的图中是否存在包含每条边 一次且恰好一次的回路？” C D A B A C B D
售嘉 “一笔划”问题 ？
“一笔划”问题 ？
&线 欧拉通路和欧拉回路 ●定义：包含图（无向图或有向图)中每条边的简单通 路称为欧拉通路。 注意：欧拉通路是简单通路（边不重复），但顶点可重复 ●定义：包含图中每条边的简单回路称为欧拉回路。 ·如果图G中含欧拉回路，则G称为欢拉图。如果图G中 有欧拉通路，但没有欧拉回路，则G称为半欧拉图。 ∥备注：通常假设G是连通的
欧拉通路和欧拉回路 定义：包含图（无向图或有向图）中每条边的简单通 路称为欧拉通路。 注意：欧拉通路是简单通路（边不重复），但顶点可重复 定义：包含图中每条边的简单回路称为欧拉回路。 如果图G中含欧拉回路，则G称为欧拉图。如果图G中 有欧拉通路，但没有欧拉回路，则G称为半欧拉图。 //备注：通常假设G是连通的