16染色问题

16染色问题

染色是将一组对象进行分类的一种直观描述. 例如，我们将集合A中的一部分元素染成红色，另一部分元素染成兰色，再把剩下的元素全染成黄色，这时我们就把集合的元素分成了红、蓝、黄三类.由于这种描述方法形象直观，因而在竞赛数学中得到广泛的应用. 下面我们主要讨论图的染色、平面染色及网格染色问题. 1．基本原理

为了说话方便，我们作如下约定：若将图G的边用k种颜色染，每条边恰染一种颜色，则把这种染色图称为k染色图.若将图G的顶点用k种颜色染，每个顶点恰染一种颜色，则把这种染色图称为k顶点染色图. 若将平面上的点用k种颜色染，每个点恰染一种颜色，则把这种染色平面称为k染色平面.若将m?n的棋盘的?m?1??n?1?个格点用k种颜色染，每个格点恰染一种颜色，则把这种染色的棋盘称为k染色的网格.需要说明的是，将一组对象用k种颜色染色时，并不要求染色完后每种颜色的对象都要出现. 另外，我们还约定：在对图的边染色之后，边的颜色全相同的r阶完全子图称为同色kr，同色k3又称为同色三角形.

定理1 二染色的k6必有同色三角形. 完全图k5可以二染色使其不含同色三角形. 二染色的k5不含同色三角形的充要条件是k5由2个颜色相异的长为5的同色圈构成.

证 不妨设k6的边用红、蓝两种颜色染. 取k6的一个顶点v1，与v1相邻的边有5条，两种颜色，由抽屉原则知必有3条同色. 不妨设v1v2,v1v3,v1v4同为红色，那么当v2,v3,v4中有两点间连红边时，则得一个红三角形；当v2,v3,v4中任两点间的连边均不是红边时，则以

v2,v3,v4为顶点的k3的三条边全为兰色，从而有一个蓝三角形，故结论成立.

若k5用红兰两色染后不含同色三角形，则每个顶点连出的4要边必是两红两兰.事实上，若k5的某一个顶点引出了3条同色边，则由上面的证明知k5中必含同色三角形，这与k5不

?，则k5?的每个顶点的度为2，含同色三角形矛盾. 现考虑二染色的k5中由红边组成的子图k5?是一个长为5的欧拉圈. 同理可证k5中由兰边组成的子图k5??也是一个长为5的欧从而知k5k5中显拉圈. 故必要性成立. 又当k5二染色后是由2个颜色相异的长为5的同色圈构成时，

然不能含同色三角形.

定理2 三染色的k17必含同色三角形，k16可以二染色使其不含同色三角形.

1

证 设k17的边用红、兰、黄三种颜色染，取k17的顶点v1，v1连出16条边，共3种颜色，由抽屉原则知必有6条边同色. 不妨设v1v2,v1v3,v1v4,v1v5,v1v6,v1v7同为黄色，那么在

v2,v3,v4,v5,v6,v7这6个点中，若有两个顶点之间连黄边，则可得一个黄三角形. 若

则以这6个点为顶点的完全图k6的边只有v2,v3,v4,v5,v6,v7中任两点间的连边均不是黄色，

红、兰两种颜色，由定理1知这个k6中必含同色三角形，从而知k17中含同色三角形.

又对于k16，我们可以给出一种三染色的方法，使其染色后不含同色三角形（见熊斌，郑仲义编著的图论P66页）.

定理3 若能将kn的边用t种颜色染，使其不含同色三角形，又能将km的边用r种颜色染使其不含同色三角形. 则可将kmn的边用r?t种颜色染，使其不含同色三角形.

证设kmn??V,E?. 令V?V1?V2???Vn，使得当1?i?j?n时，

Vi?Vj??,V?i. m将以Vi为顶点的完全图记为km,i?1,2,?,n. 因km可用r种颜色染

ii使其不含同色三角形，故可将每一个km均用前r种颜色染，使其不含同色三角形. 现将每个

i?. 因kn可用t种km收缩（或包装）成一个点vi，则得一个以v1,v2,?vn为顶点的完全图kn?用后t种颜色染使其不含同色三角形后，若kn?中颜色染，使其不含同色三角形. 那么将kn的边vivj染第l种颜色，则集合Vi的点与Vj的点之间的连边均染第l种颜色. 可以证明上述

r?t种颜色染的kmn中不含同色三角形.

注 上述证明中用到图的收缩（或包装）方法是处理图论问题的一个重要的方法. 定理4 对于任意正实数d，二染色平面上必存在距离为d的同色点；若两种颜色的点都存在，则一定存在距离为d的两个颜色相异的点.

证 取边长为d的正三角形ABC，由于3个顶点A,B,C染成两种颜色，故由抽屉原则知必有两点同色，这两个同色点的距离为d.

又设A,B为平面上两个异色点，将点A,B用线段长为d的折线段相连接. 由于点A、

B异色，因此这条折线段上必有一条线段的两个端点异色，故结论成立.

定理5 对于任意的正实数a，在二染色的平面上，必存在边长为a或3a且三顶点同色的正三角形.

2

证 若二染色平面上所有点的颜色均相同，则结论显然成立. 若二染色平面上两种颜色的点均存在，不妨设平面上的点是用红兰两种颜色染. 由定理4知，平面上存在距离为2a的两个异色点A,B. 如图1，不妨设A为红点，B为兰点， 取AB的中点C，则C必与A,B之一同色. 不妨设C 与A同为红色，以AC为边作正?ACE和正三角形

ACD. 若E,D中有一个为红点，则得到一个边长为a

的三顶点同为红色的正三角形. 若E与D均为兰点，由 图1 于B也为兰点，则?EDB是边长为3a的三顶点同色的正三角形.

定理6 设k为正实数，k?1，n为不小于3的正整数，则在r染色平面上一定存在两个n边形A1A2?An与B1B2?Bn，使得点A1,A2,?,An同色，点B1,B2,?,Bn同色，n边形A1A2?An与n边形B1B2?Bn相似，且相似比为k.

证 在r染色平面上任取一点O，以O为圆心作半径为1和半径为k的两个同心圆C1与C2. 将圆C1用点A1,A2,?,A?n?1?r2?1等分，连OAi并延长交圆C2于Bi，

i?1,2,?,?n?1?r2?1. 因为点A1,A2,?,A?n?1?r2?1的颜色不超过r，由抽屉原则知其中必

有?n?1?r?1个点同色.不妨设A1,A2,?,A?n?1?r?1同色，那么由于点B1,B2,?,B?n?1?r?1的颜色不超过r种，由抽屉原则知必存在n个点同色，不妨设B1,B2,?,Bn同色，则n边形

A1A2?An与n边形B1B2?Bn相似，相似比为k，A1,A2,?,An同色，B1,B2,?,Bn同色，

故结论成立. 3．方法解读

解染色问题时，经常用到的原理是抽屉原则. 对于图上的染色问题，常常要对同色边的条数，同色角（两边颜色相同的角）的个数、异色角（两边颜色相异的角）的个数进行计数与估值，从中寻求解决问题的方法. 另外，利用染色图中由某种颜色的边构成的子图及图论的基本原理也是解决问题的方式之一. 在解染色平面上的问题时，常常利用特殊图形去寻找问题的答案. 在解决网格问题时，常常对格点对进行计数与估值. 在下面的解题中，我们要用到如下结论：

结论1 已知ai为正整数，i?1,2,?,n，且a1?a2???an?t，则

?Ci?1n2ai取最小值的

3

充要条件是对于1?i?j?n，有ai?aj?1.

结论1 可用调整法证明.

例1 平面上给出10个不同的点，任三点不共线，每一对点间连线段. 能否用4种颜色将这些线段染色，每条线段染一种颜色，使得对于10点中的任意4个点，这4个点之间的线段均有4种颜色.

分析 将点看成图的顶点，所连线段看成图的边，则问题归结为能否将完全图k10用4种颜色染，使得染色后的k10的任意一个4阶完全子图k4中都含有4种颜色的边. 由于4阶完全子图可看成是由k10逐次删去一个顶点以及与这个顶点相邻的边而得到. 因此，在这个删去顶点及边的过程中，尽可能多地删去同一种颜色的边，再来观察删去6个顶点后的效果.

解 满足题意的染色方式不存在.

事实上，对于k10的一种4染色方式，因为k10的边有C10?45条，?2?45??11，所以必??4?有一种颜色的边不超过11条. 不妨设红边不超过11条，设A是连出红边最多的顶点，去掉顶点A及与顶点A相邻的边，得到一个9阶完全图k9，下证k9中的红边至多有8条.

事实上，若顶点A连出的红边数不小于3，则结论成立. 若顶点A连出的红边数为2，

2?10?10条，所以剩下的k9中至多有8条红边. 若顶点A连出的21?10红边数为1，则原来的k10中红边数??5，故结论成立.

2则原来的k10中红边数?再在k9中去掉一个连出红边最多的顶点及与这个顶点相邻的边，得到一个k8. 同理可证k8中红边数不超过6. 再在k8中去掉一个连红边最多的顶点及与这个顶点相邻的边，得到一个k7，同理可证k7中的红边数不超过4条. 再在k7中去掉一个连出红边最多的点，得到一个k6，同理可证k6中红边的条数不超过2. 再在k6中去掉分别与剩下2条红边（若存在的话）相邻的顶点及与这2个顶点相邻的边，得到一个k4，则这个k4中没有红边.

上述证明表明对于k10的任一个4染色方案，k10中必有一个4阶子图k4，使得k4中边的颜色至多有3种，故满足题意的染色方式不存在.

例2 试问二染色的k7中，最少存在几个单色三角形？

分析 若能建立单色三角形的个数y所满足的不等式，则可估计y的下界，进而求出y的最小值.

4

解 将两边颜色相同的角称为同色角，两边颜色相异的角称为异色角，设二染色的k7中同色三角形有y个，则异色三角形的个数为

3C7?y?35?y.

由于一个同色三角形恰有3个同色角，一个异色三角形恰有1个同色角，故二染色的k7中同色角的个数为

3y??35?y??2y?35

（1）

另一方面，设k7用红兰两种颜色染，k7的顶点分别为v1,v2,?,v7.对于i?1,2,?,7，

k7中与vi相邻的红边有xi条，则与vi相邻的兰边有?6?xi?条，从而以vi为顶点的同色角

有Cxi?C6?xi个，故k7中同色角的个数为

222?22???Ci?1272xi?C62?xi.

?又由结论1知，Cxi?C6?xi?C3?C3?6，从而有

??Ci?172xi?C26?xi???6?42 （2）

i?17由（1），（2）可得 2y?35?4，2 从而有 2y?7. 由于y为整数，所以y?4.

又如图5所示的二染色的k7恰有4个同色三角形， 图5 其中画出来的边染红色，未画出的边染兰色，故二染色的k7至少存在4个同色三角形.

例3 将k10任意去掉n条边后，得到的图任意二染色均含同色三角形，试求满足上述条件的n的最大值.

分析 二染色必含同色三角形的阶数最小的完全图是k6，因而若去掉边后所得的图含有6阶完全子图，那么该图二染色后必含同时三角形，因而可考虑最多去掉多少条边可保证所得的图中含有k6.

解 设所求的最大值为m. 我们先证明在k10中任意去掉4条边，所得的图G中必含有

5

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库16染色问题在线全文阅读。