图论电子科大杨春（优选）图论电子科大杨春跟图的边着色问题一样，生活中的很多问题，可以模型为图的顶点着色问题来处理。例如课程安排问题。A10:GT,S。如果我们用同一颜色给同一时段的课程顶点染色，那么，问题转化为在状态图中求所谓的点色数问题。定义1设G是一个图，对G的每个顶点着色，使得相邻顶点着不同颜色，称为对G的正常顶点着色；A7:GT,MA,LA;A8:LA,GT,S;A9:AC,S,LA;注：由次大度的定义知：Δ2(G)≦Δ(G)其中N(u)为G中点u的邻域。解：色集C=｛1,2,3,4,5｝在此路口处安置了交通灯。这就是著名的4色定理。注：由次大度的定义知：Δ2(G)≦Δ(G)如果用k种颜色可以对G进行正常顶点着色，称G可k正常顶点着色；定理2(布鲁克斯，1941)若G是连通的单图，并且它既不是奇圈，又不是完全图，则：(1)求点色数(2)Welsh—Powell稍微对上面算法做了一个修改，着色时按所谓最大度优先策略，即使用上面算法时，按顶点度数由大到小的次序着色。2)对G中顶点进行如下排序：情形2设G是连通度为2的正则非完全图。这就是著名的4色定理。下设G是阶数为n的非正则连通单图。解：(1)因此，п可以扩充为G的5正常顶点着色。解：把课程模型为图G的顶点，两顶点连线当且仅当有某个学生同时选了这两门课程。注：对图的正常顶点着色，带来的是图的顶点集合的一种划分方式。所以，对应的实际问题也是分类问题。属于同一种颜色的顶点集合称为一个色组，它们彼此不相邻接，所以又称为点独立集。用点色数种颜色对图G正常着色，称为对图G的最优点着色。证明：我们对顶点数作数学归纳证明。G的Δ(G)+1正常点着色算法例2给出下图的Δ+1正常点着色。v5v5对于简单图G来说，数学家布鲁克斯(Brooks)给出了一个对定理1的色数改进界。这就是下面著名的布鲁克斯定理。当n=1时，结论显然成立；(3)Δ(G)≤2情形1设G是3连通的正则非完全图。由于G本身2连通，所以G-xn的每个仅含有一个割点的块中均有点与xn邻接。设分属于H1与H2中的点x1与x2，它们与xn邻接。由于x1与x2分属于不同块，所以x1与x2不邻接。又显然G-｛x1,x2｝连通。该顶点序列的特征是，对于1≦i≦n-1,xi与某个xi+k邻接。如果令：1、四色定理所以，下面只需证明：假设G是正则的，2连通的，最大度Δ≥3的简单图，且不是完全图或奇圈，有：若G1是正则单图，则Δ(G1)=Δ(G)-1。当n=1时，结论显然成立。如果我们用同一颜色给同一时段的课程顶点染色，那么，问题转化为在状态图中求所谓的点色数问题。任取v∈V(G),令G1=G-v，由归纳假设：泰特在此期间也研究4色问题，但其证明被托特否定。推论：设G是非空简单图，若G中最大度点互不邻接，则有：设H(i,j)表示着i和j色的点在G1中的点导出子图。对于简单图G来说，数学家布鲁克斯(Brooks)给出了一个对定理1的色数改进界。由归纳假设，G1是5可顶点正常着色的。1890年，英国数学家希伍德发表地图染色定理文章，通过构造反例，指出了肯普证明中的缺陷。则通过交换含x1的分支中的着色顺序，可得到G1的新正常点着色方案，使x1与x3着同色，于是由情形1，可以得到G的5正常顶点着色方案；所以，下面只需证明：假设G是正则的，2连通的，最大度Δ≥3的简单图，且不是完全图或奇圈，有：根据这些信息，确定开设这些课程所需要的最少时间段数，使得学生选课不会发生冲突。定义2色数为k的图称为k色图。1879年7月，业余数学家肯普(1849---1922）在英国自然杂志上宣称证明了4色定理。G2G21、四色定理1879年7月，业余数学家肯普(1849---1922）在英国自然杂志上宣称证明了4色定理。肯普是凯莱在剑桥大学的学生。Heesch估计不可约构形集合可能包含10000个元素，手工验证不太可能。于是他给出了一种可用计算机来验证的方法。2、五色定理令G1=G–u。由归纳假设，G1是5可顶点正常着色的。设п是G1的5着色方案。不失一般性，设п(xi)=i(1≦i≦5)。设x1与x3属于H(1,3)的相同分支。(四)、顶点着色的应用A10:GT,S。如果我们用同一颜色给同一时段的课程顶点染色，那么，问题转化为在状态图中求对应于点色数的着色。(2)求安排----具体着色例2交通灯的相位设置问题：如图所示，列出了繁华街道路口处的交通车道L1,L2,…,L9。在此路口处安置了交通灯。当交通灯处于某个相位时，亮绿灯的车道上的车辆就可以安全通过路口。为了(最终)让所有的车辆都能够安全通过路口，对于交通灯来说，所需要的相位的最小数是多少？解：车道模型为顶点，两点连线当且仅当两个车道上的车不能同时安全