20101910072卢富毓——二部图的边染色问题

染色问题和覆盖问题第一部分。

染色问题例1.已知(2)n n >条直线把平面划分成为若干块，其中的一些区域被染上颜色，使得任何两个染色的区域都没有公共边界，求证：染色区域的数目不超过2.3n n + 解答：不妨假定这些直线有相交直线。

设有k 条边的染色区域的数目为(1,2,...,)k m k n =。

注意到2m 就是有两条边的区域，两个射线形成的角域。

至多有2n 个线段。

因为每一段（线段或射线）至多是一个染色区域的边界，所以 22323...n m m nm n +++≤。

因为一条直线上只有两段的射线部分才可能是有两条边的染色区域，所以2m n ≤。

22322323 (333)n n m m nm m n n m m m +++++++≤+≤。

注意：这里有个很关键的不等式2m n ≤需要说明一下。

设12,,...,n L L L 是平面上直线束，那么每一个直线上至多有两个被染色（如题目中定义的染色）的角域；同时每一个被染色的角域值只占有两个直线。

设12,,...,m ΩΩΩ是m 个被染色的角域。

如果某个直线i L 上被染色的角域少于两个，那么根据数学归纳法假设可以直接证明2m n ≤。

否则的话，每一个直线上面恰好有两个被染色的角域。

这样可以得到一个2-正则的二部图()1212,,,{,,...,},{,,...,}.(,)n m i j i j G X Y E X L L L Y L E L ===ΩΩΩΩ∈⇔Ω是的边界这个二部图一定有1-因子。

从而也有2m n ≤成立。

例2. 平面上给定了)2(≥n n 条直线，其中任何两条不平行，任何三条不共点。

它们将平面划分成为若干个小区域。

试在每一个区域内部填写一个绝对值不大于n 的非负整数，使得任何一条直线的同一侧所有区域中各数之和为零。

解：一个为人们关心的问题是：这个题目是怎样产生的？那个出题人为什么出这个题？它的背景是什么？如果我们将这个问题放在球面上去，让所有的直线对应于一些大圆（从拓扑学的观点看，这是完全允许的），将每一个交点看成一个节点。

第14讲 染色问题本节主要讲述用染色的方法解有关的竞赛题．染色，是一种辅助解题的手段，通过染色，把研究对象分类标记，以便直观形象地解决问题，因此染色就是分类的思想的具体化，例如染成两种颜色，就可以看成是奇偶分析的一种表现形式．染色，也是构造抽屉的一个重要方法，利用染色分类，从而构造出抽屉，用抽屉原理来解题．A 类例题例1⑴ 有一个6×6的棋盘，剪去其左上角和右下角各一个小格(边长为1)后，剩下的图形能不能剪成17个1×2的小矩形？⑵ 剪去国际象棋棋盘左上角2×2的正方形后，能不能用15个由四个格子组成的L 形完全覆盖？分析 把棋盘的格子用染色分成两类，由此说明留下的图形不能满足题目的要求．证明 ⑴如图，把6×6棋盘相间染成黑、白二色，使相邻两格染色不同．则剪去的两格同色．但每个1×2小矩形都由一个白格一个黑格组成，故不可能把剩下的图形剪成17个1×2矩形． ⑵如图，把8×8方格按列染色，第1，3，5，7列染黑，第2、4、6、8列染白．这样染色，其中黑格有偶数个．由于每个L 形盖住三黑一白或三白一黑，故15个L 形一定盖住奇数个黑格，故不可能．说明 用不同的染色方法解决不同的问题．例2 用若干个由四个单位正方形组成的“L ”形纸片无重叠地拼成一个m n 的矩形，则mn 必是8的倍数．分析 易证mn 是4的倍数，再用染色法证mn 是8的倍数．证明：每个L 形有4个方格，故4|mn ．于是m 、n 中至少有一个为偶数．设列数n 为偶数，则按奇数列染红，偶数列染蓝．于是红格与蓝格各有12mn 个，而12mn 是偶数．每个L 形或盖住3红1蓝，或盖住1红3蓝，设前者有p 个，后者有q 个．于是红格共盖住3p +q 个即p +q 为偶数，即有偶数个L 形．设有2k 个L 形．于是mn =2k ×4=8k ．故证．例例1(！)说明 奇偶分析与染色联合运用解决本题．情景再现1．下面是俄罗斯方块的七个图形：请你用它们拼出(A)图，再用它们拼出(B)图(每块只能用一次，并且不准翻过来用)．如果能拼出来，就在图形上画出拼法，并写明七个图形的编号；如果不能拼出来，就说明理由．2．能否用图中各种形状的纸片（不能剪开）拼成一个边长为75的正方形？（图中每个小方格的边长都为1）请说明理由．B 类例题例3 ⑴ 以任意方式对平面上的每一点染上红色或者蓝色．证明：一定存在无穷条长为1的线段，这些线段的端点为同一颜色．⑵ 以任意方式对平面上的每一点染上红色或者蓝色．证明：存在同色的三点，且其中一点为另两点中点．分析 任意染色而又要求出现具有某种性质的图形，这是染色问题常见的题型，常用抽屉原理或设置两难命题的方法解． 证明 ⑴取边长为1的等边三角形，其三个顶点中必有两个顶点同色．同色两顶点连成线段即为一条满足要求的线段，由于边长为1的等边三角形有无数个，故满足要求的线段有无数条．⑵ 取同色两点A 、B ，延长AB 到点C ，使BC =AB ，再延长BA 到点D ，使AD =AB ，若C 、D 中有一点为红色，例如点C 为红色，则点B 为AC 中点．则命题成立．否则，C 、D 全蓝，考虑AB 中点M ，它也是CD 中点．故无论M 染红还是蓝，均得证．说明 ⑴中，两种颜色就是两个“抽屉”，三个点就是三个“苹果”，于是根据抽屉原理，必有两个点落入同一抽屉．⑵中，这里实际上构造了一个两难命题：非此即彼，二者必居其一．让同一点既是某两个红点的中点，又是两个蓝点的中点，从而陷入两难选择的境地，于是满足条件的图形必然(5)(6)(7)(4)(2)(3)(1)(B)(A )存在．达到证明的目的．例4 ⑴ 以任意方式对平面上的每一点染上红色或者蓝色．证明：一定可以找到无穷多个顶点为为同一种颜色的等腰三角形．⑵ 以任意方式对平面上的每一点染上红色或者蓝色．证明：一定可以找到无穷多个顶点为为同一种颜色的等腰直角三角形．分析 ⑴同样可以设置两难命题：由于等腰三角形的顶点在底边的垂直平分线上，故先选两个同色点连成底边，再在连线的垂直平分线上找同色的点，这是解法1的思路．利用圆的半径相等来构造等腰三角形的两腰，这是解法2的思路．利用抽屉原理，任5个点中必有三点同色，只要这5点中任三点都是一个等腰三角形的顶点即可，而正五边形的五个顶点中任三个都是等腰三角形的顶点，这是解法3的思路．⑵连正方形的对角线即得到两个等腰直角三角形，所以从正方形入手解决相题第2问． ⑴ 证明1 任取两个同色点A 、B (设同红)，作AB 的垂直平分线MN ，若MN 上(除与AB 交点外)有红色点，则有红色三角形，若无红色点，则MN 上至多一个红点其余均蓝，取关于AB 对称的两点C 、D ，均蓝．则若AB 上有(除交点外)蓝点，则有蓝色三角形，若无蓝点，则在矩形EFGH 内任取一点K (不在边上)若K 为蓝，则可在CD 上取两点与之构成蓝色三角形，若K 为红，则可在AB 上找到两点与之构成红色三角形．证明2 任取一红点O ，以O 为圆心任作一圆，若此圆上有不是同一直径端点的两个红点A 、B ，则出现红色顶点等腰三角形OAB ，若圆上只有一个红点或只有同一直径的两个端点是红点，则圆上有无数蓝点，取两个蓝点(不关于红点为端点的直径对称)C 、D ，于是CD 的垂直平分线与圆的两个交点E 、F 为蓝点，于是存在蓝色顶点的等腰三角形CDE ． 证明3 取一个正五边形ABCDE ，根据抽屉原理，它的5个顶点中，必有三个顶点(例如A 、B 、C)同色，则△ABC 即为等腰三角形． ⑵证明 任取两个蓝点A 、B ，以AB 为一边作正方形ABCD ，若C 、D 有一为蓝色，则出现蓝色三角形．若C 、D 均红，则对角线交点E 或红或蓝， 出现红色或蓝色等腰直角三角形．显然按此作法可以得到无数个等腰直角三角形．(由本题也可以证明上一题．)例5 设平面上给出了有限个点(不少于五点)的集合S ，其中若干个点被染成红色，其余点被染成蓝色，且任意三个同色点不共线．求证：存在一个三角形，具有下述性质：⑴ 以S 中的三个同色点为顶点； ⑵ 此三角形至少有一条边上不含另一种颜色的点．分析 要证明存在同色三角形不难，而要满足第⑵个条件，可以用最小数原理．证明 由于S 中至少有五点，这些点染成两种颜色，故必存在三点同色．且据已知，此三点不共线，故可连成三角形．取所有同色三角形，由于S 只有有限个点，从而能连出的同色三角形只有有限个，故其A B C D E K HE N M D C A (2)(1)F E D C O B A O A B O C D E中必有面积最小的．其中面积最小的三角形即为所求．首先，这个三角形满足条件⑴，其次，若其三边上均有另一种颜色的点，则此三点必可连出三角形，此连出三角形面积更小，矛盾．说明 最小数原理，即极端原理．见第十二讲．例6 将平面上的每个点都染上红、蓝二色之一，证明：存在两个相似的三角形，其相似比为1995，且每一个三角形的三个顶点同色．(1995年全国联赛加试题)分析 把相似三角形特殊化，变成证明相似的直角三角形，在矩形的网格中去找相似的直角三角形，这是证法1的思路．证法2则是研究形状更特殊的直角三角形：含一个角为30˚的直角三角形．证明可以找到任意边长的这样的三角形，于是对任意的相似比，本题均可证．证法3则是考虑两个同心圆上三条半径交圆得的三组对应点连出的两个三角形一定相似，于是只要考虑找同心圆上的同色点，而要得到3个同色点，只要任取5个只染了两种颜色的点就行；而要得到5个同色点，则只要取9个只染了两种颜色的点即行． 证明 1 首先证明平面上一定存在三个顶点同色的直角三角形．任取平面上的一条直线l ，则直线l 上必有两点同色．设此两点为P 、Q ，不妨设P 、Q 同着红色．过P 、Q 作直线l 的垂线l 1、l 2，若l 1或l 2上有异于P 、Q 的点着红色，则存在红色直角三角形．若l 1、l 2上除P 、Q 外均无红色点，则在l 1上任取异于P 的两点R 、S ，则R 、S 必着蓝色，过R 作l 1的垂线交l 2于T ，则T 必着蓝色．△RST 即为三顶点同色的直角三角形．下面再证明存在两个相似比为1995的相似的直角三角形．设直角三角形ABC 三顶点同色(∠B 为直角)．把△ABC 补成矩形ABCD (如图)．把矩形的每边都分成n 等分(n 为正奇数，n >1，本题中取n=1995)．连结对边相应分点，把矩形ABCD 分成n 2个小矩形．AB 边上的分点共有n +1个，由于n 为奇数，故必存在其中两个相邻的分点同色，(否则任两个相邻分点异色，则可得A 、B 异色)，不妨设相邻分点E 、F 同色．考察E 、F 所在的小矩形的另两个顶点E '、F '，若E '、F '异色，则△EFE '或△DFF '为三个顶点同色的小直角三角形．若E '、F '同色，再考察以此二点为顶点而在其左边的小矩形，…．这样依次考察过去，不妨设这一行小矩形的每条竖边的两个顶点都同色．同样，BC 边上也存在两个相邻的顶点同色，设为P 、Q ，则考察PQ 所在的小矩形，同理，若P 、Q 所在小矩形的另一横边两个顶点异色，则存在三顶点同色的小直角三角形．否则，PQ 所在列的小矩形的每条横边两个顶点都同色．现考察EF 所在行与PQ 所在列相交的矩形GHNM ，如上述，M 、H 都与N 同色，△MNH 为顶点同色的直角三角形．由n=1995，故△MNH ∽△ABC ，且相似比为1995，且这两个直角三角形的顶点分别同色． 证明2 首先证明：设a 为任意正实数，存在距离为2a 的同色两点．任取一点O (设为红色点)，以O 为圆心，2a 为半径作圆，若圆上有一个红点，则存在距离为2a 的两个红点，若圆上没有红点，则任一圆内接六边形ABCDEF 的六个顶点均为蓝色，但此六边形边长为2a ．故存在距离为2a 的两个蓝色点． 下面证明：存在边长为a ，3a ，2a 的直角三角形，其三个顶点同色．如上证，存在距离为2a 的同色两点A 、B (设为红点)，l l以AB 为直径作圆，并取圆内接六边形ACDBEF ，若C 、D 、E 、F 中有任一点为红色，则存在满足要求的红色三角形．若C 、D 、E 、F 为蓝色，则存在满足要求的蓝色三角形． 下面再证明本题：由上证知，存在边长为a ，3a ，2a 及1995a ，19953a ，1995⨯2a 的两个同色三角形，满足要求．证明3 以任一点O 为圆心，a 及1995a 为半径作两个同心圆，在小圆上任取9点，其中必有5点同色，设为A 、B 、C 、D 、E ，作射线OA 、OB 、OC 、OD 、OE ，交大圆于A '，B '，C '，D '，E '，则此五点中必存在三点同色，设为A '、B '、C '．则∆ABC 与∆A 'B 'C '为满足要求的三角形．情景再现3．以任意方式对平面上的每一点染上红色或者蓝色．证明：一定存在一个矩形，它的四个顶点同色．4．以任意方式对平面上的每一点染上红色或者蓝色．证明：一定可以找到无穷多个顶点全为同一种颜色的全等三角形．5．图中是一个6×6的方格棋盘，现将部分1×1小方格涂成红色。

16染色问题染色是将一组对象进行分类的一种直观描述. 例如，我们将集合A 中的一部分元素染成红色，另一部分元素染成兰色，再把剩下的元素全染成黄色，这时我们就把集合的元素分成了红、蓝、黄三类.由于这种描述方法形象直观，因而在竞赛数学中得到广泛的应用. 下面我们主要讨论图的染色、平面染色及网格染色问题. 1．基本原理为了说话方便，我们作如下约定：若将图G 的边用k 种颜色染，每条边恰染一种颜色，则把这种染色图称为k 染色图.若将图G 的顶点用k 种颜色染，每个顶点恰染一种颜色，则把这种染色图称为k 顶点染色图. 若将平面上的点用k 种颜色染，每个点恰染一种颜色，则把这种染色平面称为k 染色平面.若将m n ⨯的棋盘的()()11m n ++个格点用k 种颜色染，每个格点恰染一种颜色，则把这种染色的棋盘称为k 染色的网格.需要说明的是，将一组对象用k 种颜色染色时，并不要求染色完后每种颜色的对象都要出现. 另外，我们还约定：在对图的边染色之后，边的颜色全相同的r 阶完全子图称为同色r k ，同色3k 又称为同色三角形.定理1 二染色的6k 必有同色三角形. 完全图5k 可以二染色使其不含同色三角形. 二染色的5k 不含同色三角形的充要条件是5k 由2个颜色相异的长为5的同色圈构成.证 不妨设6k 的边用红、蓝两种颜色染. 取6k 的一个顶点1v ，与1v 相邻的边有5条，两种颜色，由抽屉原则知必有3条同色. 不妨设121314,,v v v v v v 同为红色，那么当234,,v v v 中有两点间连红边时，则得一个红三角形；当234,,v v v 中任两点间的连边均不是红边时，则以234,,v v v 为顶点的3k 的三条边全为兰色，从而有一个蓝三角形，故结论成立.若5k 用红兰两色染后不含同色三角形，则每个顶点连出的4要边必是两红两兰.事实上，若5k 的某一个顶点引出了3条同色边，则由上面的证明知5k 中必含同色三角形，这与5k 不含同色三角形矛盾. 现考虑二染色的5k 中由红边组成的子图5k '，则5k '的每个顶点的度为2，从而知5k '是一个长为5的欧拉圈. 同理可证5k 中由兰边组成的子图5k ''也是一个长为5的欧拉圈. 故必要性成立. 又当5k 二染色后是由2个颜色相异的长为5的同色圈构成时，5k 中显然不能含同色三角形.定理2 三染色的17k 必含同色三角形，16k 可以二染色使其不含同色三角形.证 设17k 的边用红、兰、黄三种颜色染，取17k 的顶点1v ，1v 连出16条边，共3种颜色，由抽屉原则知必有6条边同色. 不妨设121314151617,,,,,v v v v v v v v v v v v 同为黄色，那么在234567,,,,,v v v v v v 这6个点中，若有两个顶点之间连黄边，则可得一个黄三角形. 若234567,,,,,v v v v v v 中任两点间的连边均不是黄色，则以这6个点为顶点的完全图6k 的边只有红、兰两种颜色，由定理1知这个6k 中必含同色三角形，从而知17k 中含同色三角形.又对于16k ，我们可以给出一种三染色的方法，使其染色后不含同色三角形（见熊斌，郑仲义编著的图论P66页）.定理3 若能将n k 的边用t 种颜色染，使其不含同色三角形，又能将m k 的边用r 种颜色染使其不含同色三角形. 则可将mn k 的边用r t +种颜色染，使其不含同色三角形.证设(),mn k V E =. 令12n V V V V = ，使得当1i j n ≤≠≤时，,i j i V V V m φ== . 将以i V 为顶点的完全图记为,1,2,,im k i n = . 因m k 可用r 种颜色染使其不含同色三角形，故可将每一个im k 均用前r 种颜色染，使其不含同色三角形. 现将每个im k 收缩（或包装）成一个点i v ，则得一个以12,,n v v v 为顶点的完全图nk '. 因n k 可用t 种颜色染，使其不含同色三角形. 那么将nk '用后t 种颜色染使其不含同色三角形后，若n k '中的边i j v v 染第l 种颜色，则集合i V 的点与j V 的点之间的连边均染第l 种颜色. 可以证明上述r t +种颜色染的mn k 中不含同色三角形.注 上述证明中用到图的收缩（或包装）方法是处理图论问题的一个重要的方法. 定理4 对于任意正实数d ，二染色平面上必存在距离为d 的同色点；若两种颜色的点都存在，则一定存在距离为d 的两个颜色相异的点.证 取边长为d 的正三角形ABC ，由于3个顶点,,A B C 染成两种颜色，故由抽屉原则知必有两点同色，这两个同色点的距离为d .又设,A B 为平面上两个异色点，将点,A B 用线段长为d 的折线段相连接. 由于点A 、B 异色，因此这条折线段上必有一条线段的两个端点异色，故结论成立.定理5 对于任意的正实数a ，在二染色的平面上，必存在边长为a 且三顶点同色的正三角形.证 若二染色平面上所有点的颜色均相同，则结论显然成立. 若二染色平面上两种颜色的点均存在，不妨设平面上的点是用红兰两种颜色染. 由定理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 ∆的三顶点同色的正三角形.定理6 设k 为正实数，1k ≠，n 为不小于3的正整数，则在r 染色平面上一定存在两个n 边形12n A A A 与12n B B B ，使得点12,,,n A A A 同色，点12,,,n B B B 同色，n 边形12n A A A 与n 边形12n B B B 相似，且相似比为k .证 在r 染色平面上任取一点O ，以O 为圆心作半径为1和半径为k 的两个同心圆1C 与2C . 将圆1C 用点()21211,,,n r A A A -+ 等分，连i OA 并延长交圆2C 于i B ，()21,2,,11i n r =-+ . 因为点()21211,,,n r A A A -+ 的颜色不超过r ，由抽屉原则知其中必有()11n r -+个点同色.不妨设()1211,,,n r A A A -+ 同色，那么由于点()1211,,,n r B B B -+ 的颜色不超过r 种，由抽屉原则知必存在n 个点同色，不妨设12,,,n B B B 同色，则n 边形12n A A A 与n 边形12n B B B 相似，相似比为k ，12,,,n A A A 同色，12,,,n B B B 同色，故结论成立. 3．方法解读解染色问题时，经常用到的原理是抽屉原则. 对于图上的染色问题，常常要对同色边的条数，同色角（两边颜色相同的角）的个数、异色角（两边颜色相异的角）的个数进行计数与估值，从中寻求解决问题的方法. 另外，利用染色图中由某种颜色的边构成的子图及图论的基本原理也是解决问题的方式之一. 在解染色平面上的问题时，常常利用特殊图形去寻找问题的答案. 在解决网格问题时，常常对格点对进行计数与估值. 在下面的解题中，我们要用到如下结论：结论1 已知i a 为正整数，1,2,,i n = ，且12n a a a t +++= ，则21ina i C=∑取最小值的充要条件是对于1i j n ≤<≤，有1i j a a -≤.结论1 可用调整法证明.例1 平面上给出10个不同的点，任三点不共线，每一对点间连线段. 能否用4种颜色将这些线段染色，每条线段染一种颜色，使得对于10点中的任意4个点，这4个点之间的线段均有4种颜色.分析 将点看成图的顶点，所连线段看成图的边，则问题归结为能否将完全图10k 用4种颜色染，使得染色后的10k 的任意一个4阶完全子图4k 中都含有4种颜色的边. 由于4阶完全子图可看成是由10k 逐次删去一个顶点以及与这个顶点相邻的边而得到. 因此，在这个删去顶点及边的过程中，尽可能多地删去同一种颜色的边，再来观察删去6个顶点后的效果.解 满足题意的染色方式不存在.事实上，对于10k 的一种4染色方式，因为10k 的边有21045C =条，45114⎡⎤=⎢⎥⎣⎦，所以必有一种颜色的边不超过11条. 不妨设红边不超过11条，设A 是连出红边最多的顶点，去掉顶点A 及与顶点A 相邻的边，得到一个9阶完全图9k ，下证9k 中的红边至多有8条.事实上，若顶点A 连出的红边数不小于3，则结论成立. 若顶点A 连出的红边数为2，则原来的10k 中红边数210102⨯≤=条，所以剩下的9k 中至多有8条红边. 若顶点A 连出的红边数为1，则原来的10k 中红边数11052⨯≤=，故结论成立.再在9k 中去掉一个连出红边最多的顶点及与这个顶点相邻的边，得到一个8k . 同理可证8k 中红边数不超过6. 再在8k 中去掉一个连红边最多的顶点及与这个顶点相邻的边，得到一个7k ，同理可证7k 中的红边数不超过4条. 再在7k 中去掉一个连出红边最多的点，得到一个6k ，同理可证6k 中红边的条数不超过2. 再在6k 中去掉分别与剩下2条红边（若存在的话）相邻的顶点及与这2个顶点相邻的边，得到一个4k ，则这个4k 中没有红边.上述证明表明对于10k 的任一个4染色方案，10k 中必有一个4阶子图4k ，使得4k 中边的颜色至多有3种，故满足题意的染色方式不存在.例2 试问二染色的7k 中，最少存在几个单色三角形？分析 若能建立单色三角形的个数y 所满足的不等式，则可估计y 的下界，进而求出y 的最小值.解 将两边颜色相同的角称为同色角，两边颜色相异的角称为异色角，设二染色的7k 中同色三角形有y 个，则异色三角形的个数为3735C y y -=-.由于一个同色三角形恰有3个同色角，一个异色三角形恰有1个同色角，故二染色的7k 中同色角的个数为()335235y y y +-=+（1）另一方面，设7k 用红兰两种颜色染，7k 的顶点分别为127,,,v v v .对于1,2,,7i = ，7k 中与i v 相邻的红边有i x 条，则与i v 相邻的兰边有()6i x -条，从而以i v 为顶点的同色角有()226i i x x C C -+个，故7k 中同色角的个数为()72261i i x x i CC -=+∑.又由结论1知，22226336i i x x C C C C -+≥+=，从而有()7722611642iix x i i CC-==+≥=∑∑ （2）由（1），（2）可得 23542y +≥， 从而有 27y ≥. 由于y 为整数，所以4y ≥.又如图5所示的二染色的7k 恰有4个同色三角形， 图5 其中画出来的边染红色，未画出的边染兰色，故二染色的7k 至少存在4个同色三角形.例3 将10k 任意去掉n 条边后，得到的图任意二染色均含同色三角形，试求满足上述条件的n 的最大值.分析 二染色必含同色三角形的阶数最小的完全图是6k ，因而若去掉边后所得的图含有6阶完全子图，那么该图二染色后必含同时三角形，因而可考虑最多去掉多少条边可保证所得的图中含有6k .解 设所求的最大值为m . 我们先证明在10k 中任意去掉4条边，所得的图G 中必含有6阶完全子图.事实上，设在10k 中去掉的4条边分别为1234,,,e e e e ，所得的图为G ，那么我们在G 中依次去掉1e 的一个端点，2e 的一个端点，3e 的一个端点，4e 的一个端点以及与这些端点相邻的边，这样我们就在G 中去掉了4个顶点及与这4个顶点相邻的边. 显然，保留下来的图是一个完全图6k ，从而知G 中有6阶完全子图. 由于6k 二染色后必含同色三角形，所以将G 二染色必含同色三角形，这表明4m ≥（1）又设10k 的顶点为1210,,,v v v ，在10k 中去掉5条边12345678910,,,,v v v v v v v v v v ，并把所得的图按图6所给的方式二染色，则在该二染色图中不含同色三角形. 所以4m ≤（2）由（1），（2）知4m =.例4 求最小正整数n ，使得在任何n 个无理数 中，总有3个无理数，它们中任两数之和都是无理数.分析 如果用n 个点代表n 个无理数，由于要考 虑两个顶点所代表的数的和是无理数还是有理数，所以 需用两种颜色的边表示这两种状态，因而应用染色图来模拟这一问题. 图6解 4个数中任何3个数中都含有一对相反数，这对相反数的和为0，所以5n ≥.设,,,,a b c d e 是5个无理数，我们用5个点,,,,A B C D E 分别代表这5个数.若两数之和为有理数，则在代表这两个数的顶点间连一条红边；若两数之和为无理数，则在代表这两个数的顶点间连一条兰边，得到一个二染色的5k . 下证5k 必含有一个兰三角形.事实上，如果5k 中含有一个红三角形，不妨设三角形ABC 为红三角形，则,,a b b c c a +++均为有理数，又()()()12a a b c a b c =+++-+⎡⎤⎣⎦， 这说明a 为有理数，矛盾. 这个矛盾表明5k 中不含红三角形.若5k 含有长为5的红圈，不妨设为ABCDE ，则()()()()(),,,,a b b c c d d e e a +++++均为有理数，又()()()()()2a b e a c d b c d e a +++++-+-+=，这表明a 为有理数，矛盾. 这个矛盾表明5k 中不含长为5的红圈. 由定理1知5k 含同色三角形，又5k 不含红三角形，故5k 中必含兰三角形. 由于兰边表示的是两数之和为无理数，这表明这个兰三角形的三顶点代表的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 将1111⨯的棋盘（共1212⨯个格点）的格点用红兰白三种颜色去染，每个格点只染一种颜色，求证存在一个矩形，它的边与棋盘的边平行且四角上的格点同色.分析 只要证明有位于两列的两个同色格点对位于相同的行即可. 证 因为144483=，由抽屉原则知必有一种颜色至少染了48个格点. 不妨设红格点不少于48个，其中第i 行有i a 个，1,2,,12i = ，则12148ii a=≥∑.对于第i 列的红点，可组成2ia C 个红格点对，因此12列上的红色格点对共有1221ia i C=∑个. 由结论1知12122241161272ia i i CC ==≥=⨯=∑∑.又由于12行组成的行对共有21266C =个，7262>，故由抽屉原则知必有两个红格点对位于相同的行对，因而以这四点为顶点的矩形满足要求.例7 用不在多边形内部相交的对角线将凸()4n n ≥边形分割成若干个三角形，求证：可用三种颜色给凸n 边形的顶点着色，每个顶点染一种颜色，使分割所得的每个三角形的三个顶点的颜色均不相同.分析 我们可对四边形，五边形寻找满足条件的染色方法，不难发现n 边形的染色可化为()1n -形的染色，因而想到用数字归纳法.证 设凸n 边形共分割成x 个三角形，则()1802180x n ︒⋅=-︒，2x n ∴=-. 设这2n -个小三角形中有1k 个恰含凸n 边形的两条边，2k 个恰含凸n 边形的一条边，则122k k n +≤- （1）又 122k k n += （2） 由（1），（2）中消去2k ，得()1122k n k n +-≤-，12k ∴≥.故至少有两个三角形恰含凸n 边形的两条边. 这表明，对于凸n 边形的任意一个分割方案，分割成的小三角形中至少有两个小三角形恰含凸n 边形的两条边. 下面利用这一结论对n 行归纳.当4n =时，如图8知结论成立，其中1,2,3分别代表3种颜色. 假设对n 结论成立，那么对于()1n +，由上面的证明知，()1n +边形分割成小三角形后必有一个小三角形含凸()1n +边形的两条边，不妨设这个三角形为11n n A A A +∆，那 图8么凸n 边形12n A A A 被不相交的对角线分成()2n -个小三角形，由归纳假设知，可将12n A A A ，，，用三种颜色染色，使每个小三角形的顶点的颜色全不相同. 由于1,n A A 是同一小三角形的顶点，所以1,n A A 的颜色不同，故1n A +可用不同于1,n A A 的颜色染，这样所有的小三角形的顶点的颜色均不相同，故对1n +结论成立. 由归纳法原理知结论成立.习题161. 试证二染色的6k 中至少有2个同色三角形.2. 两个航空公司为10个城市通航，使得任何两个城市之间恰有一个公司开设直达航班进行往返服务. 试证至少有一个公司能提供两个不相交的旅游圈，每个圈可游览奇数个城市.3. 能否将21n k +二染色，使得每个顶点引出的红边和兰边各有n 条.。

什么是染色问题这里的染色问题不是要求如何染色，然后问有多少种染色方法的那类题目，它指的是一种解题方法。

染色方法是一种将题目研究对象分类的形象化方法，通过将问题中的对象适当染色，我们可以更形象地观察分析出其中所蕴含的关系，再经过一定的逻辑推理，便能得出问题的答案。

这类问题不需要太多的数学知识，但技巧性、逻辑性较强，要注意学会几种典型的染色方法。

染色问题基本解法：三面涂色和顶点有关 8个顶点。

两面染色和棱长有关。

即新棱长（棱长-2）×12一面染色和表面积有关。

同样用新棱长计算表面积公式（棱长-2）×（棱长-2）*60面染色和体积有关。

用新棱长计算体积公式（棱长-2）×（棱长-2）×（棱长-2）长方体的解法和立方体同理，即计算各种公式前长、宽、高都要先减2再利用公式计算。

染色问题的解题思路染色问题是数奥解题中的难点，这类问题初看起来好像无从着手，其实只要认真思考问题也很容易解决，下面就染色问题的解题思路说一下。

图一首先，拿到一道题先认真观察，看这个题的突破点。

什么是染色问题的突破点呢？那就是找染色区域中的一个最多，这个最多是指一个区域，其他区域与它连接的最多。

例如图一中A区域A与B、C、D、E、 F连接最广所以A为特殊区域。

找到这个区域问题就容易解决了。

这个区域可以任意添色就是染最多的颜色。

本题中有4种颜色那么A可以染4种颜色了。

完成这个事件需要A、B、C、D、E、F6步所以用乘法原理。

这道题找到了最特殊的A 区域第二特殊区域和第三区域的确定也就容易了，C区域是与A相连，连接区域的数量仅次于A区域图一中的C和E区域都可以做第二个特殊区域了，但只能选一个，我们把C当成第二特殊的区域，则C可以染3种颜色。

区域B跟A、C相连那么 B可以染2种。

D与A、C、E相连则只能选1种，对吗？我们仔细观察，按顺序说A----4，C------3，B-------2，D 则连接A、C当A 选色后C有3种可能，D在A、C选色后只有2种可能。

v v v ,,...,129n 4[]2∈∈≠=u V v V i j i j K i j ,,;,1,2,...,=G V V V E k (,,...,;)12=G V V V E k (,,...,;)12==∅≠≤≤=V U V V V i j i j k i i i j k ,,,1,1=-C n n n 2(1)12K n K n v v v n ,,...,12v v v n ,,...,12一.知识与方法1.图平面上给定n 个点，其中某些点之间用边相连，得到的就是图，记作G 。

叫做图G 的顶点。

其集合记作V(G)，G 中所含的顶点个数n 叫做图G 的阶。

两个顶点u 和v 之间有边相连，则称所连得的边为uv 或（U,V ），而且说u 和v 相邻。

G 中的所有边构成的集合记作E （G ）。

所有以v 为端点的边数叫做顶点v 的度，记作d （v ）。

在本讲中，除非特别说明，任一条边的两个顶点不同，且两点之间最多有一条边，这样的图称为简单图。

定理1 设G 是n 阶图，则G 中n 个顶点的度数之和等于边数的两倍。

如果一个简单图中，每两个顶点之间都有一条边，这样的图称为完全图，通常将有n 个顶点的完全图记为。

完全图的边的数目是。

2.K 部图如果图G 的顶点集V 可以分解为K 个两两不交且非空的子集的并，即，并且没有一条边其两个端点都在上述同一子集内，我们称这样的图G 为K 部图，记作。

如果在一个K 部图中，任何两点，均有u 和v 相邻，则称G 是完全K 部图。

定理2. 有n 个顶点且不含三角形的图G 的最大边数为. 3.染色问题数学竞赛中的染色问题主要有两类：一类是问题本身就是用染色的方式给出的；另一类是借助于染色方式来解决问题。

这些问题通常涉及到组合中的存在性问题、最值问题、构造问题等。

常用的方法有抽屉原理、极端原理、数学归纳法、反证法、算两次或整体处理等。

二、典型例题选讲例1. 九名数学家在一次国际数学会议上相遇，发现他们中的任意三个人中，至少有两个人可以用同一种语言对话。

The Science Education Article Collects总第291期2014年9月(下)Total.291September 2014(C)基金项目：由专业建设———信息类特色专业建设（市级）项目（项目代码：PXM2014_014214_000017）支持。

摘要本文主要研究了平面二部图的无圈边染色问题。

证明出:对于平面二部图G ,如果任意一个度为3的顶点至多关联于一个度为4的面,那么其无圈边色数a '（G ）≤△（G ）+3。

关键词平面图平面二部图无圈边染色欧拉公式Acyclic Edge Coloring of Planar Bipartite Graphs //Wu YuwenAbstract This paper focuses on acyclic edge coloring of planar bipartite graphs.It is proved that,for a planar bipartite graph G,if any apex of 3degree is related to no more than one plane of 4de-gree,then the chromatic number of its acyclic edge is a '（G ）≤△（G ）+3.Key words planar graphs;planar bipartite graphs;acyclic edge coloring;Euler's formula1引言本文中考虑的是无向简单平面图。

V （G ），E （G ），δ（G ）和△（G ）分别表示图G 的顶点集、边集、最小度和最大度。

称度为k 的点（或面）为k-点（或k-面）；称度至少为k 的点(或面)为≥k-点(或≥k-面)；称度至多为k 的点(或面)为≤k-点(或k-面)。

图G 的一个正常的k-边染色是一个映射φ：E （G ）→1,2,…，k {}，使得对于G 中任意两条相邻的边e 1和e 2，都有φ（e 1）≠φ（e 2）。

第２１卷　第１期２０２２年　３月　广州大学学报（自然科学版）ＪｏｕｒｎａｌｏｆＧｕａｎｇｚｈｏｕＵｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ）Ｖｏｌ．２１　Ｎｏ．１Ｍａｒ．　２０２２ 基金项目：国家自然科学基金资助项目（１１７６１０６４，６１１６３０３７） 作者简介：汉大玮（１９９７—），女，硕士研究生．Ｅ ｍａｉｌ：ｈａｎｄａｗｅｉ２０２０＠１６３．ｃｏｍ 通信作者．Ｅ ｍａｉｌ：ｃｈｅｎｘｅ＠ｎｗｎｕ．ｅｄｕ．ｃｎ 引文格式：汉大玮，陈祥恩．完全二部图Ｋ１１，ｎ（１１≤ｎ≤８８）的点可区别Ｅ 全染色［Ｊ］．广州大学学报（自然科学版），２０２２，２１（１）：１０ １７．文章编号：１６７１ ４２２９（２０２２）０１ ００１０ ０８完全二部图Ｋ１１，ｎ（１１≤ｎ≤８８）的点可区别Ｅ 全染色汉大玮，陈祥恩（西北师范大学数学与统计学院，甘肃兰州　７３００７０）摘　要：设图Ｇ是简单图，如果给图Ｇ中相邻的２个顶点染有不同的颜色，并且让这２个顶点的每条关联边和关联边的端点染不相同颜色的一个全染色称为图Ｇ的一个全染色ｆ。

如果满足条件对 ｕ，ｖ∈Ｖ（Ｇ），ｕ≠ｖ，存在Ｃ（ｕ）≠Ｃ（ｖ），那么ｆ叫做图Ｇ的一个Ｅ 全染色，简称为ＶＤＥＴ染色。

文章利用反证法和分析法，讨论完全二部图Ｋ１１，ｎ（１１≤ｎ≤８８）的点可区别Ｅ 全染色问题，并利用构造染色法，给出完全二部图Ｋ１１，ｎ（１１≤ｎ≤８８）的最优点可区别Ｅ 全染色染色方案。

关键词：Ｅ 全染色；ＶＤＥＴ染色；ＶＤＥＴ染色色数；完全二部图中图分类号：Ｏ１５７．５ 文献标志码：ＡＶｅｒｔｅｘ ｄｉｓｔｉｎｇｕｉｓｈｉｎｇＥ ｔｏｔａｌｃｏｌｏｒｉｎｇｏｆａｃｏｍｐｌｅｔｅｂｉｐａｒｔｉｔｅｄｉａｇｒａｍＫ１１，ｎ（１１≤ｎ≤８８）ＨＡＮＤａ ｗｅｉ，ＣＨＥＮＸｉａｎｇ ｅｎ（ＳｃｈｏｏｌｏｆＭａｔｈｅｍａｔｉｃｓａｎｄＳｔａｔｉｓｔｉｃｓ，ＮｏｒｔｈｗｅｓｔＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｌａｎｚｈｏｕ７３００７０，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：ＬｅｔｕｓｓａｙＧｉｓａｓｉｍｐｌｅｇｒａｐｈ．ＴｈｅｃｏｌｏｒｉｎｇｆｏｆｄｉａｇｒａｍＧｉｓｃａｌｌｅｄａｎＥ ｔｏｔａｌｃｏｍｐｌｅｔｅｃｏｌｏｒｉｎｇｉｆｔｗｏａｄｊａｃｅｎｔｔｏｐｐｏｉｎｔｓｉｎｇｒａｐｈＧａｒｅｄｙｅｄｄｉｆｆｅｒｅｎｔｃｏｌｏｒｓ，ａｎｄｄｏｔｅａｃｈａｓｓｏｃｉａｔｅｄｅｄｇｅａｄｉｆｆｅｒｅｎｔｃｏｌｏｒｆｒｏｍｉｔｓｅｎｄ．ＦｏｒａｎＥ ｃｏｍｐｌｅｔｅｓｔａｉｎｃｏｌｏｒｉｎｇｏｆｇｒａｐｈＧ，ｉｆＣ（ｕ）≠Ｃ（ｖ）ｆｏｒａｎｙｔｗｏｄｉｆｆｅｒｅｎｔｖｅｒｔｉｃｅｓｕａｎｄｖｏｆＶ（Ｇ），ｗｅｓｈａｌｌａｂｂｒｅｖｉａｔｅｔｈｅ“ＶＤＥＴ”．Ｂｙｕｓｉｎｇａｎａｌｙｔｉｃａｌｍｅｔｈｏｄａｎｄｐｒｏｏｆｂｙｃｏｎｔｒａｄｉｃｔｉｏｎ，ｔｈｉｓｐａｐｅｒｄｉｓｃｕｓｓｅｓｔｈｅｖｅｒｔｅｘ ｄｉｓｔｉｎｇｕｉｓｈｉｎｇＥ ｔｏｔａｌ（ＶＤＥＴ）ｃｏｌｏｒｉｎｇｐｒｏｂｌｅｍｏｆａｃｏｍｐｌｅｔｅｂｉｐａｒｔｉｔｅｇｒａｐｈＫ１１，ｎ（１１≤ｎ≤８８），ａｎｄｔｈｅｓｔｒｕｃｔｕｒｅｓｔａｉｎｉｎｇｍｅｔｈｏｄｗａｓｕｓｅｄｔｏｇｉｖｅｔｈｅｂｅｓｔｓｔａｉｎｉｎｇｓｃｈｅｍｅｏｆｏｐｔｉｍａｌＶＤＥＴｃｏｌｏｒｉｎｇｏｆａｃｏｍｐｌｅｔｅｂｉｐａｒｔｉｔｅｇｒａｐｈＫ１１，ｎ（１１≤ｎ≤８８）．Ｋｅｙｗｏｒｄｓ：Ｅ ｔｏｔａｌｃｏｌｏｒｉｎｇ；ｖｅｒｔｅｘ ｄｉｓｔｉｎｇｕｉｓｈｉｎｇＥ ｔｏｔａｌｃｏｌｏｒｉｎｇ；ｔｈｅｖｅｒｔｅｘ ｄｉｓｔｉｎｇｕｉｓｈｉｎｇＥ ｔｏｔａｌｃｏｌｏｒｉｎｇｎｕｍｂｅｒ；ｃｏｍｐｌｅｔｅｂｉｐａｒｔｉｔｅｇｒａｐｈ 在图论研究中，图的染色问题具有极其重要的研究意义和应用价值，二部图的一系列点可区别是否正常边染色、点染色以及一系列未必正常全染色等好多问题，图论的研究者仍然追求解决这一系列有趣的难题。

图论——染⾊法判定⼆分图 ⾸先明确概念： ⼆分图：设G=(V,E)是⼀个⽆向图，如果顶点V可分割为两个互不相交的⼦集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为⼀个⼆分图。

奇数环：⼀个图中边数为奇数的环。

染⾊法原理： ⾸先任意取出⼀个顶点进⾏染⾊，和该节点相邻的点有三种情况: 1.如果未染⾊，那么继续染⾊此节点（染为另⼀种颜⾊） 2.如果已染⾊但和当前节点颜⾊不同，则跳过该点 3.如果已染⾊并且和当前节点颜⾊相同，返回失败(该图不是⼆分图) 明确⼆分图、奇数环、染⾊法之间的关系： 如果⼀个图中存在奇数环，那么这个图⼀定不是⼆分图；这⼀点显然成⽴。

如果⼀个图中不存在奇数环，那么这个图⼀定是⼆分图： 证明：⽤染⾊法。

从某个点开始逐层交叉染⾊，在染⾊过程中： 若发现有某条边的两个端点着⾊相同，则必定存在奇数环①，与题意相⽭盾。

若没有发现，则根据染⾊法原理，每⼀条边的两端着⾊必然不同，那么根据⼆分图的定义，就可知这个图是⼀个⼆分图。

①的证明： 不妨设这条边的两个端点着⾊都为1，且这两点必然是由同⼀个源点扩展⽽来。

那么根据染⾊法原理，因为这两个点的着⾊相同，那么从源点到这两个点所经过的边数（假设分别为x和y）的奇偶性必然相同，那么这个环的总边数为x+y+1，由数学知识得这个数必然是奇数。

　 证毕！ 模板题链接： 代码如下：#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>using namespace std;const int N = 100010, M = 200010;struct Edge{int to,next;}edge[M];int cnt;int n,m;int h[N],color[N];void add_edge(int u,int v){edge[++cnt].to=v;edge[cnt].next=h[u];h[u]=cnt;}bool dfs(int u,int c){color[u]=c;for(int i=h[u]; ~ i;i=edge[i].next){int to=edge[i].to;if(color[to]==c){return false;}else if(!color[to]&&!dfs(to,3-c))return false; }return true;}int main(){scanf("%d%d",&n,&m);memset(h,-1,sizeof h);for(int i=1;i<=m;i++){int a,b;scanf("%d%d",&a,&b);add_edge(a,b);add_edge(b,a);}bool flag=true;for(int i=1;i<=n;i++){if(!color[i]){if(!dfs(i,1)){flag=false;break;}}}if(flag)printf("Yes\n");else printf("No\n");}。

---------------------------------------------------------------范文最新推荐------------------------------------------------------ 图的染色问题在排课表中的应用+文献综述摘要图的染色问题是图论中的基本问题，现实生活中我们常用图的染色解决排课表问题、最短路径、最优安排、抽屉原理等问题。

图的边染色是图的染色中最基本的染色方法之一，即将图分解为互不相交的边独立集的并的方法。

随着社会的发展，各个学科对排课表问题的研究加深，单一智能算法的不足使得排课表问题未能完全解决，大学排课表仍是现今社会关注的问题。

本文首先介绍边染色和排课表问题，然后使用边染色对排课表问题进行应用，最后运用边染色解决教室无限制和教室有限制的排课问题的算法，使所得算法能解决教师、学生与教室的排课冲突，通过运行程序解决简单的排课表问题，从而使算法得到应用。

6661关键词：边染色；最优安排；排课表问题；算法1 / 10AbstractColoring is the basic problem of graph theory,we use coloring to solve the practical cases,such as curriculum schedule arrangement,the shortest route,best arrangement,drawer axiom and so on.Edge coloring is one of the basic way of graph coloring,which separates the graph into the combine of disjoint edge independent sets.With society developed,every subject go deep into the research of curriculum schedule arrangement,but the shortage of single brainpower arithmetic make it cannot go any farther,the arrangement still holds the social attention.This paper introduce edge coloring and curriculum schedule at the beginning,then solve it with edge coloring,and apply the edge coloring to curriculum schedule arrangements with unlimited-class and limited -class,so that we can solve the problems with teachers,students and classrooms.At last,we run the program to solve the simple problem,so that the algorithm can be put to use.---------------------------------------------------------------范文最新推荐------------------------------------------------------Key words:edge coloring; best arrangement; curriculum schedule arrangement; algorithm目录1摘要2Abstract2课表安排是一项十分繁重而复杂的工作，它涉及几十甚至上百个专业、几百门课程、几百名教师的合理安排。