南京大学：《图论与算法》课程教案讲稿（Graph Theory and Algorithms, GTA）第14周 染色

商有京大努 NANJING UNIVERSITY 第9章染色 程龚 2023/5/15

第9章 染色 程龚 2023/5/15 1

一对一辅导问题 每位教师对每位同学的一对一辅导需要一整天时间， 集训总共至少需要多少天？ 教师 同学 算法教师 赵同学 图论与算法 赵同学、钱同学 教师 高级算法 赵同学、钱同学、孙同学、 教师 李同学、周同学 数据结构 钱同学、孙同学 教师 计算复杂性 孙同学、李同学 教师 组合优化 李同学、周同学 教师 2023/5/15

2023/5/15 2 一对一辅导问题 n 每位教师对每位同学的一对一辅导需要一整天时间， 集训总共至少需要多少天？

一对一辅导问题 每位教师对每位同学的一对一辅导需要一整天时间， 集训总共至少需要多少天？ 教师 同学 算法教师 赵同学 图论与算法 赵同学、钱同学 V2 教师 高级算法 赵同学、钱同学、孙同学、 教师 李同学、周同学 数据结构 钱同学、孙同学 教师 计算复杂性 孙同学、李同学 V8 教师 组合优化 李同学、周同学 10 教师 2023/5/15

2023/5/15 3 一对一辅导问题 n 每位教师对每位同学的一对一辅导需要一整天时间， 集训总共至少需要多少天？

一对一辅导问题 每位教师对每位同学的一对一辅导需要一整天时间， 集训总共至少需要多少天？ ● 对每条边染“色”，使存在冲突关系的边的色不同 找色的数量最少的染色方案 教师 同学 算法教师 赵同学 图论与算法 赵同学、钱同学 V2 教师 高级算法 赵同学、钱同学、孙同学、 4 教师 李同学、周同学 数据结构 钱同学、孙同学 教师 计算复杂性 孙同学、李同学 教师 组合优化 李同学、周同学 10 教师 2023/5/15

2023/5/15 4 一对一辅导问题 n 每位教师对每位同学的一对一辅导需要一整天时间， 集训总共至少需要多少天？ l 对每条边染“色”，使存在冲突关系的边的色不同， 找色的数量最少的染色方案

参赛问题 ■每项比赛需要一整天时间，比赛总共至少需要多少天？ 比赛 员工 ①编程 小赵 ②算法 小赵、小钱 ③架构小赵、小钱、小孙、小李、小周 ④调参 小钱、小孙 ⑤测试 小孙、小李 ⑥理论 小李、小周 2023/5/15

n 每项比赛需要一整天时间，比赛总共至少需要多少天？ 2023/5/15 5 参赛问题

参赛问题 ■每项比赛需要一整天时间，比赛总共至少需要多少天？ 比赛 员工 ①编程 小赵 ②算法 小赵、小钱 6 ③架构 小赵、小钱、小孙、小李、小周 V2 ④调参小钱、小孙 ⑤测试 小孙、小李 ⑥理论 小李、小周 V4 2023/5/15

n 每项比赛需要一整天时间，比赛总共至少需要多少天？ 2023/5/15 6 参赛问题

参赛问题 ■每项比赛需要一整天时间，比赛总共至少需要多少天？ 。对每个顶点染“色”，使存在冲突关系的顶点的色不同， 找色的数量最少的染色方案 比赛 员工 ①编程 小赵 ②算法 小赵、小钱 6 ③架构小赵、小钱、小孙、小李、小周 ④调参 小钱、小孙 Vs ⑤测试 小孙、小李 ⑥理论 小李、小周 V4 2023/5/15

n 每项比赛需要一整天时间，比赛总共至少需要多少天？ l 对每个顶点染“色”，使存在冲突关系的顶点的色不同， 找色的数量最少的染色方案 2023/5/15 7 参赛问题

本次课的主要内容 9.1边的染色 9.2顶点的染色 2023/5/15

9.1 边的染色 9.2 顶点的染色 2023/5/15 8 本次课的主要内容

本次课的主要内容 9.1边的染色 9.2顶点的染色 2023/5/15

9.1 边的染色 9.2 顶点的染色 2023/5/15 9 本次课的主要内容

边的染色 ■边染色 ●函数ec:E→{1，，，值域代表种色 V2 2 3 (a) 2023/5/15 10

n k边染色 l 函数ec : E à {1, …, k}，值域代表k种色 2023/5/15 10 边的染色