电子科大图论课件——第7章.ppt

《电子科大图论课件——第7章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章图的着色§7.1图的边着色设A,B是两个集合，τ是A到B的一个映射，记为τ：A→B，对,令τ(A’)={τ(a)

2、a∈A’}，τ－1(B’)={x

3、τ(x)∈B’}特别地当B’＝{b}时，τ－1(B’)也记为τ-1(b)。定义1给定图G=(V,E),称映射π：E→{1,2,…,k}为G的一个k-边着色，简称边着色，称{1,2,…,k}为色集。若π为G的边着色且，当相邻时，π，则称该着色是正常的。图G的正常k-边着色的最小k值称为G的边色数，记为，简记为。下图中的(a),(b)表达了一个图的两个3-边着色，其中(b)为正常3-边着色，(a)(b)'c易知该图有=

4、3若图G存在一个正常k-边着色，则称G是k-边可着色的。设A是一个集合。A的一个子集族{A1,A2,…,Ak}若满足当i≠j时，Ai∩Aj=Φ,并且A1∪A2∪…∪Ak=A，我们则称{A1,A2,…,Ak}为A的一个分划。边着色问题，也是边集的分划问题。即将E分划为子集族{A1,A2,…,Ak},使Ai的边全着i色(称Ai为色组).很明显任何正常边着色中和任一顶点关联的各边必须着不同色，由此推知≥Δ'c(1.1)易知,若着色是正常的且G无环，则每个非空色组均为E的匹配.证明设Km,n的互补顶点子集为X={x0,x1,…,xm-1}和Y={y0,y1,…,yn-1}。

5、假定m≤n,此时Δ＝n.令φ：E(Km,n)→{0,2,…,n-1}例1给出Km,n的一个正常Δ-边着色，由此证明c’(Km,n)=Δ()nmjiKEyx,Î"记为＝使,φ(xiyj)=(i+j)(modn)i＋nj任取Km,n中两条邻边xiyj和xiyk,j≠k。若φ(xiyj)=φ(xiyk),则i＋nj=i＋nk,从而j＝k，矛盾。所以φ(xiyj)≠φ(xiyk)。同理，对邻边xiyj和xkyj,也有φ(xiyj)≠φ(xkyj)。以上表明φ是正常边着色。从而c’(Km,n)≤n≤Δ'c(Km,n)=Δ再连同(1.1)式便得设π是图G的某个子图的边着色，对G

6、的点u，如果与u相关联的边的着色未用到颜色i,那么我们称u缺i色。下文的边着色均指正常边着色。定理1若G图是偶图，则c’=Δ证明对边数m用归纳法。当m＝1时，Δ＝1，有c’=1＝Δ。设G是至少两条边的偶图。取uv∈E(G)，令G’=G-uv。由归纳假设c’(G’)＝Δ(G’)。因Δ(G’)≤Δ(G)，故G’存在一个Δ(G)-边着色π。在G中，对着色π,因边uv未着色，故u和v均至少缺少一种色。设u缺i色。若v也缺i色，则可给uv着i色,从而得到一个G的一个Δ(G)-边着色。设v不缺i色，而缺j色(j≠i)。令H(i,j)是由着i色的边和着j色的边导出的的子图。因H(

7、i,j)的点在H(i,j)中最多关联两条边，故H(i,j)的分支是路或圈。因v缺j色而不缺i色，故在H(i,j)中v的度为1。这表明H(i,j)的含v的分支是以v为起点的路Γ。我们说点u不在Γ中。这是因，一方面Γ是由着i色与着j色的边交替组成，另一方面u缺i色。所以若u在Γ中，则u只可能是Γ的终点。这样，Γ的长为偶。从而Γ+uv是G中－个奇圈，这与G是偶图无奇圈矛盾。引理1设G是简单图，x与y1是G中两个不相邻的顶点，π是G的一个正常k-边着色。若对该着色π，x,y1以及与x相邻的点均至少缺少一种颜色，则G＋xy1也是k-边可着色的。(证明略)在Γ中交换i色与j色，

8、再对边uv着i色便得G的一个Δ(G)-边着色。这表明c’(G)≤Δ(G)，再由(1.1)式知c’(G)=Δ(G)定理2若G是简单图，则c’=Δ或c’=Δ+1证明由(1.1)式，只须证c’≤Δ+1即可。设G是具有m条边的简单图，对m用归纳法。当m＝1时，Δ＝1，c’=1，有c’≤Δ+1。设m≥2,取G中一条边xy,令G’=G－xy。由归纳假设c’(G’)≤Δ(G’)+1。因Δ(G’)≤Δ(G)，故c’(G’)≤Δ(G)+1c’(G)≤k=Δ(G)+1。设Δ(G)+1=k,故存在G’的正常k-边着色π。在G’中，对π，显然每个点至少缺少一种颜色。于是由引理1G’+xy=

9、G是k-边可着色的，从而c’(G’)≤Δ(G’)+1=[Δ(G)-1]+1=Δ(G)推论1设G是Δ(G)>0的简单图。若G中恰有一个度为Δ(G)的点，或G中恰有两个度为Δ(G)的点并且这两个点相邻，则c’(G)=Δ(G)证明设G中恰有的两个度数等于Δ(G)的点为x与y,且x与y相邻。令G’=G-xy，显然Δ(G’)=Δ(G)-1，由定理2，从而存在G’的正常Δ(G)-边着色π。因对=Δ(G)-1故对G’，在π下每个点均至少缺少一种颜色，由引理1可知G’+xy=G是Δ(G)边可着色的。从而c’(G)≤Δ(G)，所以c’(G)=Δ(G)。当G中恰有一个度为Δ(G)的