图论电子科大杨春跟图得边着色问题一样,生活中得很多问题,可以模型为图得顶点着色问题来处理。例如课程安排问题。A10:GT,S。如果我们用同一颜色给同一时段得课程顶点染色,那么,问题转化为在状态图中求所谓得点色数问题。定义1设G就是一个图,对G得每个顶点着色,使得相邻顶点着不同颜色,称为对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)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。在此路口处安置了交通灯。当交通灯处于某个相位时,亮绿灯得车道上得车辆就可以安全通过路口。为了(最终)让所有得车辆都能够安全通过路口,对于交通灯来说,所需要得相位得最小数就是多少？解:车道模型为顶点,两点连线当且仅当两个车道上得车不能同时安全地进入路口。另一方面,通过尝试,用4种色实现了正常点着色。