§1图的基本概念与模型 思考题 一个班级的学生共计选修A、B、C、D、E、F六门 课程，其中一部分人同时选修D、C、A,一部分人同时 选修B、C、F,一部分人同时选修B、E,还有一部分人 同时选修A、B,期终考试要求每天考一门课，六天内考 完，为了减轻学生负担，要求每人都不会连续参加考试， 试设计一个考试日程表。 2014-12-15 16
2014-12-15 16 §1 图的基本概念与模型 • 一个班级的学生共计选修A、B、C、D、E、F六门 课程，其中一部分人同时选修D、C、A，一部分人同时 选修B、C、F，一部分人同时选修B、E，还有一部分人 同时选修A、B，期终考试要求每天考一门课，六天内考 完，为了减轻学生负担，要求每人都不会连续参加考试， 试设计一个考试日程表。 思考题
§1图的基本概念与模型 思考题解答： 以每门课程为一个顶点，共同被选修的课程之间用边相 连，得图，按题意，相邻顶点对应课程不能连续考试，不相 邻顶点对应课程允许连续考试，因此，作图的补图，问题是 在图中寻找一条哈密顿道路，如C一E一A一F—D一B,就 是一个符合要求的考试课程表。 2014-12-15 17
2014-12-15 17 §1 图的基本概念与模型 思考题解答： 以每门课程为一个顶点，共同被选修的课程之间用边相 连，得图，按题意，相邻顶点对应课程不能连续考试，不相 邻顶点对应课程允许连续考试，因此，作图的补图，问题是 在图中寻找一条哈密顿道路，如C—E—A—F—D—B，就 是一个符合要求的考试课程表
§1图的基本概念与模型 学习要点： 1.掌握图的基本概念； 2.会用图论的观点去分析解决较简单的实际问题。 作业：(P170)6.3 2014-12-15 18
2014-12-15 18 §1 图的基本概念与模型 学习要点： 1.掌握图的基本概念； 2.会用图论的观点去分析解决较简单的实际问题。 作业：（P170） 6.3
§2树与图的最小树 树是图论中结构最简单但又十分重要的图。在自然和社会领 域应用极为广泛。树图的定义是无圈的连通图。 例乒乓球单打比赛抽签后，可用图来表示相遇情况，如下 图所示。 运动员A 2014-12-15 19
2014-12-15 19 §2 树与图的最小树 树是图论中结构最简单但又十分重要的图。在自然和社会领 域应用极为广泛。树图的定义是无圈的连通图。 例 乒乓球单打比赛抽签后，可用图来表示相遇情况，如下 图所示。 运动员 A B C D E F G H
§2树与图的最小树 例某企业的组织机构图也可用树图表示。 厂长 人事科 财务科 总工 生产副 经营副 程师 厂长 厂长 开发科 技术科 生产科 设备科 供应科 动力科 销售科 检验科 2014-12-15 20
2014-12-15 20 §2 树与图的最小树 例 某企业的组织机构图也可用树图表示。 厂长 人事科 财务科 总工 程师 生产副 厂长 经营副 厂长 开发科 技术科 生产科 设备科 供应科 动力科 销售科 检验科 厂长 人事科 财务科 总工 程师 生产副 厂长 经营副 厂长 开发科 技术科 生产科 设备科 供应科 动力科 销售科 检验科