图的染色教学提纲.ppt

《图的染色教学提纲.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、图的染色四川师范大学数学与软件科学学院周思波边染色给定(p,q)图，考虑用k种颜色对G的q条边进行染色。这就是，把G的边集E(G)划分为k个子集Ei，Ei称为第i个色组，其中的边被认为染上了第i种颜色。实际上就是由G的边集E(G)到色集S={1,2,…,k}建立一个映射α。如果对于G的任何两条相邻的边ei,ej，都有α(ei)≠α(ej)，换句话说，对每个i，Ei都是图G的边无关集，那么α就称为G的一个正常k边染色。若图G有正常的k边染色，则称G为k边可染的。例子若图G是k边可染的，而l＞k，则G也是l边可染的。使图G具有正常边染色的最小颜色数，称为G的边色数，记作χ’(G)。χ’(G)

2、≥Δ(G)引理6.1设连通图G不是长度为奇数的回路，则G有一个2边染色，它的两种颜色在度至少为2的每个顶点都出现。证首先假设连通图G是Euler图。如果G的所有顶点度数均为2，那么G是回路。故G是长度为偶数的回路，此时定理显然成立。如果G的顶点度数不全是2，那么必有一个度数至少为4的顶点v。设e1e2…eq是G的Euler环游。令E1={ei

3、i是奇数}，E2={ei

4、i是偶数}。因为G的每个顶点都是环游的内部顶点，所以G的2边染色(E1,E2)具有所要求的性质。其次，假设G不是Euler图，那么添加一个新的顶点w，并把它和G的每一个奇顶点都连接起来，这样构成的图G*显然是Euler图。

5、we1e2…eqw是G*的Euler环游，同上面一样定义E1,E2。则(E1∩E,E2∩E)具有所要求的性质。最优k边染色给定图G的一个k边染色α之后，我们用Cα(v)表出在染色α下点v所出现的不同颜色的数目，显然有Cα(v)≤dG(v)，并且等号对所有顶点成立当且仅当α是正常k边染色。设图G有两个k边染色α和β，若有则称k边染色α优于β，如果不存在优于α的k边染色，就说α是最优的k边染色。引理6.2设α是图G的一个最优的k边染色。若存在G中的一个顶点u及两种颜色i和j，使得i不在u出现，而j至少在u出现两次。令Ei和Ej分别为G中以i和j着色的边的集合，则G[Ei∪Ej]中含有u的分支

6、B是长度为奇数的回路。定理6.3对于任何简单图G有Δ(G)≤χ’(G)≤Δ(G)+1证假设对于简单图G，有χ’(G)＞Δ(G)+1，令α是一个最优(Δ(G)+1)边染色，必有顶点u适合Cα(u)＜dG(u)，又dG(u)＜Δ(G)+1，因此按照α染色必有颜色i0在u不出现，而i1在u至少出现两次。设α(u,v)=i1，α(u,v1)=i1，因为dG(v1)=Δ(G)+1，所以有颜色i2在v1不出现，但i2必定出现。否则就可以把(u,v2)改用颜色i2，得到一个新的Δ(G)+1边染色优于α。这与对α的假设矛盾。又设α(u,v2)=i2，同上理由，有颜色i3在v2不出现而在u必出现，否则可以

7、把(u,v1)改用i2染色，把(u,v2)改用i3染色，于是得到另一个Δ(G)+1边染色优于α，引出矛盾。继续这个过程，构造出一个顶点序列v1,v2,…和一个颜色序列i1,i2,…，vi均与u邻接，使得vt均与u邻接，α(u,vt)=it，it+1不在vt出现(t=1,2,…,i)。由于dG(u)有限，因此有最小整数l，使得存在k

8、β(e)=

9、i0,e∈E(G)}，Eik={e

10、β(e)=ik,e∈E(G)}。由引理6.2，G[Ei0∪Eik]中包含u的分支B是一个长度为奇数的回路。由此可知对于边染色α，vk恰与G[Ei0∪Eik]的两条边关联，即vk在此导出子图中度为2。又定义G的另一个(Δ(G)+1)边着色γ:γ(u,vt)=vt+1(t=1,2,…,l)，对其它e∈E(G),γ(e)=α(e)。显然，对于任何v∈V(G)有Cγ(v)＞Cα(v)，因此γ也是一个最优(Δ(G)+1)边染色，令E’i0={e

11、γ(e)=i0,e∈E(G)}，E’ik={e

12、γ(e)=ik,e∈E(G)}。则G[E’i0∪E’ik]中包含u的分

13、支B’是一个长度为奇数的回路。比较回路B中各边在与下的染色，只有(u,vk)改变了颜色，因此vk在G[E’i0∪E’ik]中的度数为1，这与B’是奇回路矛盾，因此推知定理成立。定理6.4二分图属于第一类图，即χ’(G)=Δ(G)证G为二分图，假定χ’(G)=Δ(G)+1，设α是一个最优边染色，必有顶点u适合Cα(u)＜dG(u)。u显然满足引理6.2的条件，所以G包含一个长度为奇数的回路。因而不是二分图，导出矛盾。故χ’(G)=Δ(