哈尔滨理工大学呻斛生課程 离影数 第15章欧拉图与哈密顿图 计算机系
第15章 欧拉图与哈密顿图 离 散 数 学 哈尔滨理工大学本科生课程 计算机系
本章内容 15.1欧拉图 15.2哈密顿图 15.3带权图与货郎担问题 基本要求 作业
本章内容 15.1 欧拉图 15.2 哈密顿图 15.3 带权图与货郎担问题 基本要求 作业
15,1欧抗图 口历史背景一一哥尼斯堡七桥问题 B B D 口欧拉图是一笔画出的边不重复的回路
15.1 欧拉图 ❑ 历史背景－－哥尼斯堡七桥问题 ❑ 欧拉图是一笔画出的边不重复的回路
定义15.1通过图(无向图或有向图)中所有边一次且仅一次 行遍图中所有顶点的通路称为欧拉通路,通过图中所有边 次并且仅一次行遍所有顶点的回路称为欧拉回路。具有 欧拉回路的图称为欧拉图,具有欧拉通路而无欧拉回路的 图称为半欧拉图。 说明欧拉通路是图中经过所有边的简单的生成通路(经过所 有顶点的通路称为生成通路)。 欧拉回路是经过所有边的简单的生成回路
欧拉图 定义15.1 通过图（无向图或有向图）中所有边一次且仅一次 行遍图中所有顶点的通路称为欧拉通路，通过图中所有边 一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有 欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的 图称为半欧拉图。 说明 欧拉通路是图中经过所有边的简单的生成通路(经过所 有顶点的通路称为生成通路)。 欧拉回路是经过所有边的简单的生成回路
举例 欧拉图 半欧拉图 无欧拉通路 欧拉图 无欧拉通路 无欧拉通路
举例 欧拉图 半欧拉图 无欧拉通路 欧拉图 无欧拉通路 无欧拉通路