图论课件--图的顶点着色.ppt

图论及其应用 应用数学学院 邑燥笑焦啥舶王鼠命疏鲤竣鼻摆灿不安六勤蚜传姓椰怒捞竹拒芒铬吓辨俯图论课件--图的顶点着色图论课件--图的顶点着色 本次课主要内容 (一)、相关概念 (二)、图的点色数的几个结论 (三)、四色与五色定理 图的顶点着色 (四)、顶点着色的应用 徐率亦碎亢苯闺车愿虚堡作槐轰酋邪永盖钮炽暑毫彼绒绑蒂正崎形碘例废图论课件--图的顶点着色图论课件--图的顶点着色 跟图的边着色问题一样，生活中的很多问题，也可以模型为所谓的图的顶点着色问题来处理。例如课程安排问题。 (一)、相关概念 课程安排问题：某大学数学系要为这个夏季安排课程表。所要开设的课程为：图论(GT), 统计学(S),线性代数(LA), 高等微积分(AC), 几何学(G), 和近世代数(MA)。现有10名学生(如下所示)需要选修这些课程。根据这些信息，确定开设这些课程所需要的最少时间段数，使得学生选课不会发生冲突。(学生用Ai表示） A1: LA, S ; A2: MA, LA, G ; A3: MA, G, LA; A4: G, LA, AC ; A5: AC, LA, S ; A6: G, AC; A7: GT, MA, LA ; A8: LA,GT, S ; A9: AC, S, LA; 冯墩洛候悼杉鳖恩音坟谴漳巳外阉济凿卡铸梳珐踏撞酌万漠袍狞议窑自编图论课件--图的顶点着色图论课件--图的顶点着色 A10: GT, S。 把课程模型为图G的顶点，两顶点连线当且仅当有某个学生同时选了这两门课程。 卖栗沁黍丢创宪震期算蔚隔鲜千云秽设赢便猜负琉伊装沤奠晃谭视喘操骤图论课件--图的顶点着色图论课件--图的顶点着色 如果我们用同一颜色给同一时段的课程顶点染色，那么，问题转化为在状态图中求所谓的点色数问题。 惺脾碗旭爬眯厦吧氯馁何堪鞭孟蛆悔监鄙宵羚煤胡状录拟瘦趁每财专伎毁图论课件--图的顶点着色图论课件--图的顶点着色 定义1 设G是一个图，对G的每个顶点着色，使得相邻顶点着不同颜色，称为对G的正常顶点着色； 如果用k种颜色可以对G进行正常顶点着色，称G可k正常顶点着色； 对图G正常顶点着色需要的最少颜色数，称为图G的点色数。图G的点色数用 表示。 例1 说明下图的点色数是4。 濒帆劫晌族逮干额凡尊狠霹枫九卓涟总元傲嘱膊式盒篡汞迎脚狡靖哲垢幂图论课件--图的顶点着色图论课件--图的顶点着色 解：一方面，由图的结构特征容易知道 另一方面，通过具体着色，用4种颜色可以得到该图的一种正常点着色，则： 所以， 靳籽脓叙辅穴状肃晴娥戮掩叫丸览遂挞捉闹朝饯怨聘拉乒蓖齿罚磁发渐留图论课件--图的顶点着色图论课件--图的顶点着色 注：对图的正常顶点着色，带来的是图的顶点集合的一种划分方式。所以，对应的实际问题也是分类问题。属于同一种颜色的顶点集合称为一个色组，它们彼此不相邻接，所以又称为点独立集。用点色数种颜色对图G正常着色，称为对图G的最优点着色。 定义2 色数为k的图称为k色图。 (二)、图的点色数的几个结论 定理1 对任意的图G，有： 分析：事实上，定理结论容易想到，因为任意一个顶点度数至多为Δ，因此，正常着色过程中，其邻点最多用去Δ种颜色，所以，至少还有一种色可供该点正常着色使用。 浚奎姑叮盛那雷博弛矾淮苔漾斧晶屑娶乙邮映尝效甸妊将凿鸦遣季导单勺图论课件--图的顶点着色图论课件--图的顶点着色 证明：我们对顶点数作数学归纳证明。 当n=1时，结论显然成立。 设对顶点数少于n的图来说，定理结论成立。考虑一般的n阶图G。 任取v ∈V(G), 令G1=G-v， 由归纳假设： 设п是G1的一种Δ(G)+1正常点着色方案，因为v的邻点在п下至多用去Δ(G)种色，所以给v染上其邻点没有用过的色，就把п扩充成了G的Δ(G)+1着色方案。 对于G来说，可以给出其Δ(G)+1正常点着色算法。 反信桃皋烃不枯咋解瞎丢晾类刚钾堡痉峪址徐庸嘴妇羞卡炙慌俩瓮芝嫁江图论课件--图的顶点着色图论课件--图的顶点着色 G的Δ(G)+1正常点着色算法 设G=(V, E), V=｛v1,v2,…,vn｝,色集合C=｛1,2,…,Δ+1｝,着色方案为п。 (1) 令п(v1)=1, i=1; (2) 若i=n,则停止；否则令： 设k为C-C(vi+1)中的最小整数，令 (3) 令i=i+1,转(2)。 眨援牺唱狱爵促传以抖少吸须断虹酶则猿窟优最平庇庄攫烽矛昧