《着色问题分析》PPT课件

《《着色问题分析》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论及其应用第六章着色问题6.1边色数k-边着色（k-edgecoloring）CC是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-边可着色的(pk).G的边色数（edgechromaticnumber）(G)=min{kG为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。。。ev为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……ev（v=v0）为G的一Euler环游。与(A)②一样定义C=（E1，E2），易见C’=(E1E，E2E）满足要求。记号

4、c(v)=边着色C表现于v的不同颜色数。易见，c(v)d(v)vV。C为正常边着色c(v)=d(v)vV。称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[EiEj]中含u的分支是一奇圈。证明：令H为G[EiEj]中含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)vu，∴，这与C为最优矛盾。6图论及其应用6.1边色数定理6.1设G为偶图，则=。证明：（Wilson）对进行归纳。当=1时显然成立。假设对

6、集。由于在G’中u与v都不是其最大度顶点，从而有Au,Av①当Au∩Av时：将Au∩Av之一色着在边e上，即得G的(G)-正常边着色。②AuAv=时：任取色iAu及色jAv。令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的任一边割中(任SV)，3-种色边的奇偶性相同。（提示：考虑G[EiEj]，ij，其中C=(E1,E2,E3)