16染色问题(2)

6阶完全子图.

事实上，设在k10中去掉的4条边分别为e1,e2,e3,e4，所得的图为G，那么我们在G中依次去掉e1的一个端点，e2的一个端点，e3的一个端点，e4的一个端点以及与这些端点相邻的边，这样我们就在G中去掉了4个顶点及与这4个顶点相邻的边. 显然，保留下来的图是一个完全图k6，从而知G中有6阶完全子图. 由于k6二染色后必含同色三角形，所以将G二染色必含同色三角形，这表明

m?4

（1）

又设k10的顶点为v1,v2,?,v10，在k10中去掉5条边v1v2,v3v4,v5v6,v7v8,v9v10，并把所得的图按图6所给的方式二染色，则在该二染色图中不含同色三角形. 所以

m?4

由（1），（2）知m?4.

（2）

例4 求最小正整数n，使得在任何n个无理数 中，总有3个无理数，它们中任两数之和都是无理数.

分析 如果用n个点代表n个无理数，由于要考 虑两个顶点所代表的数的和是无理数还是有理数，所以 需用两种颜色的边表示这两种状态，因而应用染色图

来模拟这一问题. 图6

解 显然，2,2,?2,?2这4个数中任何3个数中都含有一对相反数，这对相反数的和为0，所以n?5.

设a,b,c,d,e是5个无理数，我们用5个点A,B,C,D,E分别代表这5个数.若两数之和为有理数，则在代表这两个数的顶点间连一条红边；若两数之和为无理数，则在代表这两个数的顶点间连一条兰边，得到一个二染色的k5. 下证k5必含有一个兰三角形.

事实上，如果k5中含有一个红三角形，不妨设三角形ABC为红三角形，则

a?b,b?c,c?a均为有理数，又

a?1??a?b???c?a???b?c???， 2?这说明a为有理数，矛盾. 这个矛盾表明k5中不含红三角形.

c若k5含有长为5的红圈，不妨设为ABCDE，则?a?b?,b??均为有理数，又

,?d??cd,??e?e,?a??? 6

?a?b???e?a???c?d???b?c???d?e??2a，

这表明a为有理数，矛盾. 这个矛盾表明k5中不含长为5的红圈. 由定理1知k5含同色三角形，又k5不含红三角形，故k5中必含兰三角形. 由于兰边表示的是两数之和为无理数，这表明这个兰三角形的三顶点代表的3个无理数中任何两个的和仍为无理数，所以n的最小值为5.

例5 证明：在二染色的平面上，?a?R?，一定存在斜边长为a且三个内角分别为

30?,60?,90?的三顶点同色的三角形.

分析 直角三角形的顶点在以斜边为直径的圆上，为了找到满足条件的3个顶，可在圆的六等分点中去找.

证 由定理4知，二染色平面上存在距离为a的同色点.不妨设平面上的点用红兰两种颜色染，且平面上存在距离为a的两个红点A,B. 以AB为直径作圆，如图7，用A,B,C,D,E,F 将圆六等分. 若C,D,E,F中有一个红点，譬如C 为红点，则?ABC满足要求；若C,D,E,F全为

兰点，则?DEF满足要求. 图7

例6 将11?11的棋盘（共12?12个格点）的格点用红兰白三种颜色去染，每个格点只染一种颜色，求证存在一个矩形，它的边与棋盘的边平行且四角上的格点同色.

分析 只要证明有位于两列的两个同色格点对位于相同的行即可. 证 因为

144?48，由抽屉原则知必有一种颜色至少染了48个格点. 不妨设红格点不3少于48个，其中第i行有ai个，i?1,2,?,12，则

?ai?112i?48.

12对于第i列的红点，可组成C个红格点对，因此12列上的红色格点对共有结论1知

2ai?Ci?12ai个. 由

?Ci?1122ai2??C4?6?12?72. i?112 7

又由于12行组成的行对共有C12?66个，72?62，故由抽屉原则知必有两个红格点对位于相同的行对，因而以这四点为顶点的矩形满足要求.

例7 用不在多边形内部相交的对角线将凸n?n?4?边形分割成若干个三角形，求证：可用三种颜色给凸n边形的顶点着色，每个顶点染一种颜色，使分割所得的每个三角形的三个顶点的颜色均不相同.

分析 我们可对四边形，五边形寻找满足条件的染色方法，不难发现n边形的染色可化为?n?1?形的染色，因而想到用数字归纳法.

证 设凸n边形共分割成x个三角形，则180??x??n?2?180?，?x?n?2. 设这n?2个小三角形中有k1个恰含凸n边形的两条边，k2个恰含凸n边形的一条边，则

2k1?k2?n?2 （1）

又 2k1?k2?n （2） 由（1），（2）中消去k2，得

k1??n?2k1??n?2，

?k1?2.

故至少有两个三角形恰含凸n边形的两条边. 这表明，对于凸n边形的任意一个分割方案，分割成的小三角形中至少有两个小三角形恰含凸n边形的两条边. 下面利用这一结论对

n行归纳.

当n?4时，如图8知结论成立，其中1,2,3分别代表3 种颜色. 假设对n结论成立，那么对于?n?1?，由上面的证

明知，?n?1?边形分割成小三角形后必有一个小三角形含凸

?n?1?边形的两条边，不妨设这个三角形为?A1AnAn?1，那 图8

么凸n边形A1A2?An被不相交的对角线分成?n?2?个小三角形，由归纳假设知，可将

A1，A2，?，An用三种颜色染色，使每个小三角形的顶点的颜色全不相同. 由于A1,An是同

一小三角形的顶点，所以A1,An的颜色不同，故An?1可用不同于A1,An的颜色染，这样所有

8

的小三角形的顶点的颜色均不相同，故对n?1结论成立. 由归纳法原理知结论成立.

习题16

1. 试证二染色的k6中至少有2个同色三角形.

2. 两个航空公司为10个城市通航，使得任何两个城市之间恰有一个公司开设直达航班进行往返服务. 试证至少有一个公司能提供两个不相交的旅游圈，每个圈可游览奇数个城市.

3. 能否将k2n?1二染色，使得每个顶点引出的红边和兰边各有n条.

9

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