离散数学图论与系中有图题目
———————————————————————————————— 作者： ———————————————————————————————— 日期：
2
图论中有图题目 一、 4个结点、6个结点和8个结点的三次正则图没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。Welch-Powell给出了一个使颜色数尽可能少（不一定最少）的结点着色方法，在实际使用中比较有效： 第1步、 将图的结点按度数的非增顺序排列；第2步、用第1种颜色给第1个结点着色，并按照结点排列顺序，用同一种颜色给每个与前面已着色的结点不邻接的结点着色；第3步、换一种颜色对尚未着色的结点按上述方法着色，如此下去，直到所有结点全部着色为止。 例1 分别求右面两图的色数
（1）由于（1）中图G中无奇数长的基本回路，由定理可知??G??2。 （2）由于（2）中图G含子图轮图W4，由于??W4??4，故??G??4。又因
为此图的最大度??G??4，G不是完全图，也不是奇数长的基本回路，由定理可知（对n阶轮图Wn，n为奇数时有??Wn??3，n为偶??G????G??4，因而??G??4。
数时有??Wn??4；对n阶零图Nn，有??Nn??1；完全图Kn，有??Kn??n；对于二部图G??V1,V2,E?,E??时即??Nn??1，E??时即??G??2；在彼得森图G中，存在奇数长的基本回路，因而??G??3，又彼得森图既不是完全图也不是长度为奇数的基本回路，且??G??3，由定理??G??3，故??G??3） 例2 给右边三个图的顶点正常着
色，每个图至少需要几种颜色。 答案：（1）
(1)(2)??G??2；（2）
（3）??G??4 ??G??3；
例3 有8种化学品A,B,C,D,P,R,S,T
(2)(1)(3)要放进贮藏室保管。出于安全原因，
下列各组药品不能贮在同一个室内：A-R, A-C, A-T, R-P, P-S, S-T, T-B, B-D, D-C, R-S, R-B,
3
离散数学图论与系中有图题目
