离散数学图论与关系中有图题目VIP专享

1 图论中有图题目 一、 没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。Welch-Pow ell给出了一个使颜色数尽可能少（不一定最少）的结点着色方法，在实际使用中比较有效： 第 1 步、 将图的结点按度数的非增顺序排列；第 2 步、用第 1 种颜色给第 1 个结点着色，并按照结点排列顺序，用同一种颜色给每个与前面已着色的结点不邻接的结点着色；第 3步、换一种颜色对尚未着色的结点按上述方法着色，如此下去，直到所有结点全部着色为止。 例 1 分别求右面两图的色数 （1）由于（1）中图G 中无奇数长的基本回路，由定理可知  2G。 （2）由于（2）中图G 含子图轮图4W ，由于 44W，故  4G。又因为此图的最大度  4G，G 不是完全图，也不是奇数长的基本回路，由定理可知  4GG ，因而  4G。（对 n阶轮图nW ，n为奇数时有3nW，n为偶数时有4nW；对n阶零图nN ，有1nN；完全图nK ，有nKn；对于二部图12,,,GV V EE  时即 1nN， E  时即  2G；在彼得森图G 中，存在奇数长的基本回路，因而  3G，又彼得森图既不是完全图也不是长度为奇数的基本回路，且  3G，由定理  3G，故  3G） 例 2 给右边三个图的顶点正常着色，每个图至少需要几种颜色。 答 案 ：（ 1 ） 2G；（ 2 ） 3G；（3）  4G 例 3 有8 种化学品 A,B,C,D,P,R,S,T要放进贮藏室保管。出于安全原因，下列各组药品不能贮在同一个室内：A-R, A-C, A-T, R-P, P-S, S-T, T-B, B-D, D-C, R-S, R-B, 4个结点、6个结点和8个结点的三次正则图(2)(1)(3)(2)(1)2 P-D, S-C ,S-D，问贮藏这8 种药品至少需要多少个房间？ 解 以8 种药品作为结点，若两种药品不能贮在同一个室内，则它们之间有一条边，这样得右图，转化为图的正常着色问题。（1）对各结点按度数的递减顺序排列为SRDPCTAB；（2）对S 及不与之相邻点A，B 着1c色；（3）对R 及不与之相邻点D 着2c 色；（4）对P 和C 着3c 色。故着色数 3G；又因为因S,D,P 为3K 子图，故着色数 3G，从而 3G。因此贮藏这8 种药品至少需要3 个房间。贮藏方式之一为SAB, RDT, PC。 (考试排考或老师排课让选修的学生避免冲突...