文档介绍：该【图论电子科大杨春】是由【太丑很想放照片】上传分享，文档一共【38】页，该文档可以免费在线阅读，需要了解更多关于【图论电子科大杨春】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。本次课主(Zhu)要内容
(一)、相关(Guan)概念
(二)、图的点色数的几个结论
(三)、四色与五色定理
图的顶点着色
(四)、顶点着色的应用
*
第一页,共三十八页。
跟图的边着色问题一样,生活中的很多问题,可以模型为图的顶点(Dian)着色问题来处理。例如课程安排问题。
(一)、相关(Guan)概念
课程安排问题:某大学数学系要为这个夏季安排课程表。要开设的课程为:图论(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的顶点,两顶点连(Lian)线当且仅当有某个学生同时选了这两门课程。
GT
MA
G
AC
LA
S
选课状态图
*
第三页,共三十八页。
如果我们用同一颜色给同一时段的课程顶点染色,那(Na)么,问题转化为在状态图中求所谓的点色数问题。
GT
MA
G
AC
LA
S
选课状态图
*
第四页,共三十八页。
定义1设G是一个图(Tu),对G的每个顶点着色,使得相邻顶点着不同颜色,称为对G的正常顶点着色;
如果(Guo)用k种颜色可以对G进行正常顶点着色,称G可k正常顶点着色;
对图G正常顶点着色需要的最少颜色数,称为图G的点色数。图G的点色数用表示。
例1说明下图的点色数是4。
GT
MA
G
AC
LA
S
GT
MA
G
AC
LA
S
*
第五页,共三十八页。
解:一方面,由(You)图的结构特征容易知道
另一方面,通过具体着(Zhuo)色,用4种颜色可以得到该图的一种正常点着色,则:
GT
MA
G
AC
LA
S
所以,
*
第六页,共三十八页。
注:对图的正常顶点着色,带来的是图的顶点集合的一种划分方式。所以,对应的实际问题也是分类问题。属于同一种颜色的顶点集合称为一个色组,它们彼此不相邻接,所以又(You)称为点独立集。用点色数种颜色对图G正常着色,称为对图G的最优点着色。
定义2色数为k的图(Tu)称为k色图。
(二)、图的点色数的几个结论
定理1对任意的图G,有:
分析:事实上,定理结论容易想到,因为任意一个顶点度数至多为Δ,因此,正常着色过程中,其邻点最多用去Δ种颜色,所以,至少还有一种色可供该点正常着色使用。
*
第七页,共三十八页。
证明:我们对顶(Ding)点数作数学归纳证明。
当n=1时,结论(Lun)显然成立。
设对顶点数少于n的图来说,定理结论成立。考虑一般的n阶图G。
任取v∈V(G),令G1=G-v,由归纳假设:
设п是G1的一种Δ(G)+1正常点着色方案,因为v的邻点在п下至多用去Δ(G)种色,所以给v染上其邻点没有用过的色,就把п扩充成了G的Δ(G)+1着色方案。
对于G来说,可以给出其Δ(G)+1正常点着色算法。
*
第八页,共三十八页。
G的Δ(G)+1正(Zheng)常点着色算法
设G=(V,E),V={v1,v2,…,vn},色集合(He)C={1,2,…,Δ+1},着色方案为п。
(1)令п(v1)=1,i=1;
(2)若i=n,则停止;否则令:
设k为C-C(vi+1)中的最小整数,令
(3)令i=i+1,转(2)。
*
第九页,共三十八页。
例2给出下图的Δ+1正常(Chang)点着色。
v5
v4
v3
v2
v1
v6
解(Jie):色集C={1,2,3,4,5}
*
第十页,共三十八页。