《图论》第6章-图的着色.ppt

该【《图论》第6章-图的着色 】是由【zhilebei】上传分享，文档一共【49】页，该文档可以免费在线阅读，需要了解更多关于【《图论》第6章-图的着色 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。图的着色包括对边、顶点和平面区域的着色。本章主要讨论简单图的顶点着色。[例]6种化学制品,某些不能放在同一仓库。用矩阵表示,例如(a,b)=1表示a和b不能放在同一仓库。问:最少需要几个仓库?第六章图的着色第一页,编辑于星期六:八点一分。[解]以该矩阵为邻接矩阵构造图如上所示。给图的顶点染色使得相邻点具有不同颜色,最少需要3种颜色。第六章图的着色acbdef第二页,编辑于星期六:八点一分。[着色]图G=(V,E)的一个k顶点着色指用k种颜色对G的各顶点的一种分配方案。若着色使得相邻顶点的颜色都不同,则称该着色正常,或称G存在一个正常的k顶点着色(或称一个k着色)。此时称G为k-可着色的。[色数]使G=(V,E)k-可着色的最小k值称为G的色数,记为?(G)。若?(G)=k,称G为k***。,编辑于星期六:八点一分。[例]三***,编辑于星期六:八点一分。[特殊图的色数]①零图:?(G)=1②完全图Kn:?(G)=n③G是一条回路:?(G)=2若|V|是偶数 ?(G)=3若|V|是奇数④G是一棵非平凡树:?(G)=2⑤?(G)=2的充要条件是:(a)|E|?1;(b)G中不存在边数为奇数的回路。(此时G为二部图)⑥若G1、G2为G的两个连通分支,则?(G)=max{?(G1),?(G2)},编辑于星期六:八点一分。⑤?(G)=2的充要条件是:(a)|E|?1;(b)G中不存在边数为奇数的回路。(此时G为二部图)[证明]必要性显然。充分性: 由(a)|E|?1知?(G)?2。 对G中的某一连通分支,找到其一棵生成树,对顶点做二染色。加上任意一条余树枝,得到对应的唯一回路。由(b)知该回路长度为偶数,该余树枝两个端点染的是不同颜色,添加该余树枝后仍然可以保持原来的二染色。加上所有余树枝,得到图G,二染色仍得到保持,即?(G)=2。,编辑于星期六:八点一分。[临界图]G=(V,E),若对G的任一真子图H均有?(H)<?(G),则称G为一个临界图。k色临界图称为k-临界图。[性质]①任何k***通过对边的反复删减测试最后可以得到其k-临界子图。②临界图是连通图。证:设G1、G2为临界图G的两个连通分支,则?(G)=max{?(G1),?(G2)}。不妨设?(G)=?(G1),而G1为G的真子图,与临界图的定义矛盾。,编辑于星期六:八点一分。[定理6-1-1]k-临界图G=(V,E),?=min{deg(vi)|vi?V},则??k-1。[证明]反证法:设G是一个k-临界图且?<k-1。又设v0?V,deg(v0)=?。由k-临界图的定义,G?v0是(k?1)可着色的,在一种k?1着色方案下,G?v0的顶点可按照颜色划分成V1,V2,…,Vk-1共k?1块,块Vi中的顶点被涂以颜色ci。由于deg(v0)<k?1,v0至少与其中一块Vj不邻接即与Vj中的任何顶点不邻接。此时可将v0涂以颜色cj,从而获得对G的一种k?1着色方案,与G的色数是k矛盾。,编辑于星期六:八点一分。[推论1]k***至少有k个度不小于k-1的顶点。[证明]设k***G的k-临界子图为G?,由定理,G?的最小度???k-1,故G的最小度?????k-1,即G的任何顶点的度不小于k-1。又G为k***,其中至少有k个顶点。,编辑于星期六:八点一分。[推论2]对G=(V,E),?=max{deg(vi)|vi?V},有?(G)??+1。[证明]设?(G)=k,由推论1,有v?V,使得 deg(v)?k-1 又:deg(v)?? 故:??k-1或???(G)-1 即:?(G)??+1推论2给出了色数的一个上限,但很不精确。[例]二部图可二染色,但是?可以相当大。,编辑于星期六:八点一分。