欢迎来到天天文库
浏览记录
ID:41259140
大小:222.01 KB
页数:35页
时间:2019-08-20
《《着色问题分析》PPT课件》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、图论及其应用第六章着色问题6.1边色数k-边着色(k-edgecoloring)CC是k种色在图G的边集上的一种分配。C是E(G)的一个k-划分,即C=(E1,…,Ek)边着色C是正常的每个Ei都是G的一个匹配。G为k-边可着色的(k-edgecolorable)G有一正常k-边着色。存在E(G)的一个k-划分C=(E1,…,Ek),使每个Ei都是G的一个匹配。(注:允许Ei=)显然,G为k-边可着色的G为p-边可着色的(pk).G的边色数(edgechromaticnumber)(G)=min{kG为k-边可着色的}。G为k-边色的(k-edge
2、chromatic)(G)=k。2图论及其应用6.1边色数例:n个人举行一些两两会谈,每次会谈用一个单元时间。问最少要多少单元时间,才能安排完所有会谈?解:作一n顶点图G,其中两顶点相邻当且仅当对应的两人间要安排一次会谈。易见,所需时间单元数’(G)。称色i表现(represented)于顶点v与v相关联的某一边有色i。3图论及其应用6.1边色数引理6.1.1设连通图G不是奇圈,则G有一2-边着色,使该二色表现于G的每个度2的顶点。证明:不妨设G为非平凡的。(A)若G为Euler图:①若G为一个圈:则G为偶圈,从而G的一个正常2-边着色满足要求。②若G不是
3、一个圈:则一定存在顶点v0,使d(v0)4(∵Euler图每个顶点的度均为偶数)。令v0e1v1e2。。。ev为G一的Euler环游(v=v0)。令E1与E2分别为Euler环游中下标为奇数与偶数的边子集。则G的2-边着色C=(E1,E2)满足要求。4图论及其应用6.1边色数(B)若G为非Euler环游:往G中加一新顶点v0,并将v0与G中每个度为奇数顶点都用一新边连起来,得图G’。显然,G’为一Euler图。令v0e1v1e2……ev(v=v0)为G的一Euler环游。与(A)②一样定义C=(E1,E2),易见C’=(E1E,E2E)满足要求。记号
4、c(v)=边着色C表现于v的不同颜色数。易见,c(v)d(v)vV。C为正常边着色c(v)=d(v)vV。称G的k-边着色C’为其k-边着色C的一个改进。C为最优k-边着色(optimalk-edgecolouring)C不能再改进。5图论及其应用6.1边色数引理6.1.2设C=(E1,。。。,Ek)为G的一个最优k-边着色。若G中有一顶点u及色i与j,使i不表现于u,而j在u上至少表现2次。则G[EiEj]中含u的分支是一奇圈。证明:令H为G[EiEj]中含u的分支。假设H不是奇圈,由引理6.1.1.,H有一2-边着色,使该二色表现于H的每个度2
5、顶点上。以这方式,用色i与j对H重新边着色,得G的一个新的k-边着色C’。显然,c’(u)=c(u)+1,c’(v)c(v)vu,∴,这与C为最优矛盾。6图论及其应用6.1边色数定理6.1设G为偶图,则=。证明:(Wilson)对进行归纳。当=1时显然成立。假设对6、集。由于在G’中u与v都不是其最大度顶点,从而有Au,Av①当Au∩Av时:将Au∩Av之一色着在边e上,即得G的(G)-正常边着色。②AuAv=时:任取色iAu及色jAv。令H为G[Ei’Ej’]中含u的分支。易见,H是一条路,由色i与色j边交替组成。因此,v一定不在H上(不然,由于H的第一条边有色j,最后一边有i,其长为偶数。这导致G中含一奇圈H+e,矛盾。)对换H上的色i与j,得G’的另一正常(G’)-边着色,其中在u与v上色j都不表现。再将色j着在e上,即得G的正常(G)-边着色。7图论及其应用6.1边色数——习题6.1.1找出一适当的7、边着色以证明(Km,n)=(Km,n)。6.1.2(a)证明:任一偶图G都有一-正则偶母图。(不一定为生成母图!)(b)利用(a)给出定理6.1的另一证明。6.1.3叙述求偶图G的正常-边着色的好算法。6.1.4*证明:若偶图G有>0,则G有一-边着色,使所有种色在每一顶点上都表现。6.1.5每一简单、3-正则、H-图,都有’=3。6.1.6(Issacs引理)设G为3-正则图,且其上有一3-边着色,则在G的任一边割中(任SV),3-种色边的奇偶性相同。(提示:考虑G[EiEj],ij,其中C=(E1,E2,E3)
6、集。由于在G’中u与v都不是其最大度顶点,从而有Au,Av①当Au∩Av时:将Au∩Av之一色着在边e上,即得G的(G)-正常边着色。②AuAv=时:任取色iAu及色jAv。令H为G[Ei’Ej’]中含u的分支。易见,H是一条路,由色i与色j边交替组成。因此,v一定不在H上(不然,由于H的第一条边有色j,最后一边有i,其长为偶数。这导致G中含一奇圈H+e,矛盾。)对换H上的色i与j,得G’的另一正常(G’)-边着色,其中在u与v上色j都不表现。再将色j着在e上,即得G的正常(G)-边着色。7图论及其应用6.1边色数——习题6.1.1找出一适当的
7、边着色以证明(Km,n)=(Km,n)。6.1.2(a)证明:任一偶图G都有一-正则偶母图。(不一定为生成母图!)(b)利用(a)给出定理6.1的另一证明。6.1.3叙述求偶图G的正常-边着色的好算法。6.1.4*证明:若偶图G有>0,则G有一-边着色,使所有种色在每一顶点上都表现。6.1.5每一简单、3-正则、H-图,都有’=3。6.1.6(Issacs引理)设G为3-正则图,且其上有一3-边着色,则在G的任一边割中(任SV),3-种色边的奇偶性相同。(提示:考虑G[EiEj],ij,其中C=(E1,E2,E3)
此文档下载收益归作者所有