词条 | 七色定理 |
释义 | 一。七色定理起源,人类在企图证明四色定理过程中,发现了在曲面上作图,反而更加容易。1974年德国的林格和美国的杨斯证明了:Np=[(7+√1+48P)12].(公式来自《图论导引》214页,机械工业出版社) P是指这个曲面的洞的个数,又叫亏格。当亏格为1时N1=[(7+√1+48×1)12].=7 外国数学家并且给出了这个需要7种颜色染色的图形:(参见右图)上下对折,再左右对折,形成一个汽车轮胎形状,就是有7个区域两两相连。 表明:在有一个洞的曲面上染色,6种颜色是不够的。如果能够将一个图G画在平面上,使得他的边仅仅在端点相交,则称这个图是可以嵌入平面的,或者称其为平面图。 二证明又叫Heawood定理。 人类在企图证明四色定理过程中,发现了在曲面上作图,反而更加容易。1974年德国的林格和美国的杨斯证明了:Np=[(7+√1+48P)/2].证明这个公式,数学家用了78年。P是指这个曲面的洞的个数,又叫亏格。当亏格为3时:N3=[(7+√1+48×3)/2]=9(公式来源: 《图论导引》214页,机械工业出版社, 《图论导引》258页,人民邮电出版社) 《图论和网络流理论》239页,高等教育出版社? 介绍 需要7种颜色染色的图形:下图是全景图,上图:上下对折,再左右对折,形成一个汽车轮胎形状,就是有7个区域两两相连。 表明:在有一个洞的曲面上染色,6种颜色是不够的。 如果能够将一个图G画在平面上,使得他的边仅仅在端点相交,则称这个图是可以嵌入平面的,或者称其为平面图。 证明部分在证明四色定理过程中, Heawood的文章不仅仅指出了Kempe的错误,而且也给出了五色定理的一个证明,然而他没有停留于此,Heawood继续考虑其它一些想法,Heawood文章的主要后续成果是征对于可嵌入到球面的图的最大色数问题。Heawood把注意力转移到其它曲面上图的色数确定问题上。 对于非负整数k,设 χ(Sκ)=max{χ(G)}. 其中,max取遍嵌入到Sx的所有图G,自Kempe的1879年的文章之后,大家都相信χ(Sò)=4,而在Heawood的1890年的文章之后,仅仅知道χ(Sò)=4,或者χ(Sò)=5. 1976年当Appel和Haken宣布其成果之后,确定了χ(Sò)=4(四色定理)。 在Heawood的1890年的文章中,他试图获得关于χ(Sκ)的一个公式,在其中k为正整数,事实上,他认为他已经做到了,然而,他所做的仅仅是获得了χ(Sκ)的一个上界。 定理; 对于每一个正整数k, χ(Sκ)≤[(7+√1+48K))/2] 证明:(直接证法)设G为看嵌入到Sκ的一个图,并且设 h=[(7+√1+48K)/2], 由h的定义可以证明: 6+12(k-1)/h=h-1 下面证明χ(G)≤h 在G的所有诱导子图中,设H具有最大的最小度,根据定理:对每个图G, X(G)<1+max{S(H)} 其中,max取遍G的所有诱导子图H。 可以得到X(G)≤1+δ(H),假设H的阶为n,边数为m,若n≤h,则δ(H)≤n-1,X(G)≤n≤h,因此我们可以假设n>h. 由于G可以嵌入到Sk,所以,H也能够嵌入到Sk,因此由推论可知 K>γ(H)≥m/6-n/2+1, 易见,m≤3n+6(k-1),因此nδ(H)≤Σdegu=2m≤6n+12(k-1)所以, δ(H)≤6+12(k-1)/n ≤6+12(k-1)/h=h-1。从而,X(G)≤1+δ(H)=h=[(7+√1+48k)/2]。 ,结论成立。 证明这个公式对于所有整数k成立又花费了78年。数学家Gerhard Ringel和Ted Young对这个公式的证明发挥了最主要的作用。 上下对折再左右对折就是一个轮胎形状,有7个区域两两相连。它有1个洞。1974年德国数学家林格(Gerhard Ringel)和美国数学家杨斯(Ted Youngs)证明:Np=[(7+√1+48k)/2];k表示洞的数目。N1=[(7+√1+48x1)/2]=7,当k=1时,N1=7。 三意义区域染色的意义十分重大,在实际生活中有广泛的应用。 |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。