考试时间编排问题 ·问题：排考试时间，一方面要总时间尽可能短（假设教室没问题）， 一方面一个同学所选的任意两门课不能同时间。 ·图模型：每门课程对应一个顶点。任意两点相邻当且仅当对应的两门 课程有相同的选课人。 ·解：用不同颜色给顶点着色。相邻的点不能同颜色。则最少着色数即 至少需要的考试时间段数（可以将颜色相同的点所对应的课程安排在 同一时间)
考试时间编排问题 • 问题：排考试时间，一方面要总时间尽可能短(假设教室没问题)，另 一方面一个同学所选的任意两门课不能同时间。 • 图模型：每门课程对应一个顶点。任意两点相邻当且仅当对应的两门 课程有相同的选课人。 • 解：用不同颜色给顶点着色。相邻的点不能同颜色。则最少着色数即 至少需要的考试时间段数(可以将颜色相同的点所对应的课程安排在 同一时间)
“巧渡河”问题 ·问题：人、狼、羊、菜用一条只能同时载两位的小船渡河，“狼羊”、 “羊菜”不能在无人在场时共处，当然只有人能架船。 ·图模型：顶点表示“原岸的状态”，两点之间有边当且仅当一次合理 的渡河“操作”能够实现该状态的转变。 ·起始状态是“人狼羊菜”，结束状态是“空”。 ·问题的解：找到一条从起始状态到结束状态的尽可能短的通路
“巧渡河”问题 • 问题：人、狼、羊、菜用一条只能同时载两位的小船渡河，“狼羊”、 “羊菜”不能在无人在场时共处，当然只有人能架船。 • 图模型：顶点表示“原岸的状态”，两点之间有边当且仅当一次合理 的渡河“操作”能够实现该状态的转变。 • 起始状态是“人狼羊菜”，结束状态是“空”。 • 问题的解：找到一条从起始状态到结束状态的尽可能短的通路
“巧渡河”问题的解 ·注意：在“人狼羊菜”的16种组合种允许出现 的只有10种。 人羊狼菜人狼菜人羊狼人羊菜人羊 狼菜 狼 菜 羊 空（成功）
“巧渡河”问题的解 • 注意：在“人狼羊菜”的16种组合种允许出现 的只有10种。 空(成功 ) 人羊狼菜 人狼菜 人羊狼 人羊菜 狼菜 狼 菜 人羊 羊
特别提醒：图论中有 很多小的术语（概念）， 一定要理解和记忆住
特别提醒：图论中有 很多小的术语(概念)， 一定要理解和记忆住
以下概念的区分 。Subgraph、proper subgraph ·Spanning subgraph、induced subgraph 。Walk ·Trail、Path、 。Circuit、Circle ·Distance、geodesic、diameter
以下概念的区分 • Subgraph、proper subgraph • Spanning subgraph、induced subgraph • Walk • Trail、Path、 • Circuit、Circle • Distance、geodesic、diameter