图的基本概念与模型 Page 16 思考题 一个班级的学生共计选修A、B、C、D、E、F六门 课程，其中一部分人同时选修D、C、A,一部分人同时 选修B、C、F,一部分人同时选修B、E,还有一部分人 同时选修A、B,期终考试要求每天考一门课，六天内考 完，为了减轻学生负担，要求每人都不会连续参加考试， 试设计一个考试日程表
图的基本概念与模型 Page 16 一个班级的学生共计选修A、B、C、D、E、F六门 课程，其中一部分人同时选修D、C、A，一部分人同时 选修B、C、F，一部分人同时选修B、E，还有一部分人 同时选修A、B，期终考试要求每天考一门课，六天内考 完，为了减轻学生负担，要求每人都不会连续参加考试， 试设计一个考试日程表。 思考题
图的基本概念与模型 Page 17 思考题解答： 以每门课程为一个顶点，共同被选修的课程之间用边相 连，得图，按题意，相邻顶点对应课程不能连续考试，不相 邻顶点对应课程允许连续考试，因此，作图的补图，问题是 在图中寻找一条哈密顿道路，如C一E一A一F一D一B,就 是一个符合要求的考试课程表
图的基本概念与模型 Page 17 思考题解答： 以每门课程为一个顶点，共同被选修的课程之间用边相 连，得图，按题意，相邻顶点对应课程不能连续考试，不相 邻顶点对应课程允许连续考试，因此，作图的补图，问题是 在图中寻找一条哈密顿道路，如C—E—A—F—D—B，就 是一个符合要求的考试课程表
图的基本概念与模型 Page 18 A B E D
图的基本概念与模型 Page 18 A F E D C B
图的基本概念与模型 Page 19 A B
图的基本概念与模型 Page 19 A F E D C B
图的基本概念与模型 Page 20 图的基本性质： 定理1任何图中，顶点次数之和等于所有边数的2倍。 证明：由于每条边必与两个顶点关联，在计算点的次时，每条边 均被计算了两次，所以顶点次数的总和等于边数的2倍。 定理2任何图中，次为奇数的顶点必为偶数个。 证明：设V1和V2分别为图G中奇点与偶点的集合。由定理1可得： ∑4+w-4=2m 2m为偶数，且偶点的次之和∑()也为偶数，所以∑d,必为偶 数，即奇数点的个数必为偶数
图的基本概念与模型 Page 20 图的基本性质： 定理1 任何图中，顶点次数之和等于所有边数的2倍。 定理2 任何图中，次为奇数的顶点必为偶数个。 证明：由于每条边必与两个顶点关联，在计算点的次时，每条边 均被计算了两次，所以顶点次数的总和等于边数的2倍。 证明：设V1和V2分别为图G中奇点与偶点的集合。由定理1可得： d v d v d v m v V v V v V ( ) ( ) ( ) 2 1 2 + = = 2m为偶数，且偶点的次之和 也为偶数，所以 必为偶 数，即奇数点的个数必为偶数。 2 ( ) v V d v 1 ( ) v V d v