电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

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

离散数学图论与关系中有图题目_第1页
1/16
离散数学图论与关系中有图题目_第2页
2/16
离散数学图论与关系中有图题目_第3页
3/16
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。 (考试排考或老师排课让选修的学生避免冲突...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

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

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部