第68讲图论问题二Word格式文档下载.docx

第68讲图论问题二Word格式文档下载.docx

《第68讲图论问题二Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《第68讲图论问题二Word格式文档下载.docx（25页珍藏版）》请在冰点文库上搜索。

例2一个舞会有n（n≥2）个男生与n个女生参加，每个男生都与一些女生（不是全部）跳过舞，而每个女生都至少与1名男生跳过舞，证明，存在男生b1，b2与女生g1，g2，其中b1与g1跳过舞，b2与g2跳过舞．但b1与g2没有跳过舞，b2与g1没有跳过舞．

分析就是要给出一种选择方法，按此方法操作，即可选出满足要求的两个男生与两个女生．可以用极端原理来证明这样的存在性命题．

证明取所有男生中与女生跳舞人数最多的一个，设是b1．b1至少与1名女生没有跳过舞，取没有与b1跳过舞的一名女生为g2，g2至少与1名男生跳过舞，设为b2，显然b1不是b2，现在考虑所有没有与b2跳过舞的女生，她们不能都没有与b1跳过舞，（否则没有与b1跳舞的女生人数就比没有与b2跳舞的人数多，b1就不是与女生跳舞人数最多者）．即至少有1个女生没有跟b2跳过舞但跟b1跳过舞．这个女生即为g1．

说明这里就得到了一个偶图{b1，b2}∪{g1，g2}．（图中，括号内的数字表示证明中出现的先后顺序）．极端原理常用于证明存在性命题．

情景再现

1．求证：

顶点多于1的树是偶图．

2．证明偶图的色数≤2，反之，色数≤2的图是偶图．

B类例题

例3某镇有居民1000人，每人每天把昨天听到的消息告诉自己认识的人，已知任何消息只要镇上有人知道，都会经过这样的方式逐渐地为全镇的人所知道．证明可以选出90名代表，使得同时向他们报告一个消息，经过10天，这一消息就为全镇的人知道．

分析就是要给出一个把1000个点的连通图分成90个子图的方法，使每个点都在其中一个子图中，且每个子图的最长的链的长度不超过10．这样，只要把每个子图的最长链的一个端点选为“代表”，就能完成这个任务．

证明用1000个点代表1000个居民，两名居民相识，则在两点之间连一线，如此可得一图，依条件，这个图是连通图．若图中有圈，则我们去掉圈中的一边使圈被破坏而不影响图的连通性，经过有限次这种手续，可得树T1000．

在T1000中取一条主干v1v2…vn，取v11作为1个代表，把边v11v12去掉，则此图分成了2个连通分支，在含有v1的一棵树中，每点到v11的路的长度都不超过10，否则v1v2…vn在T1000中不是主干，故v11知道的消息在10天内可以传遍它所在分支的点集所代表的居民；

余下另一分支再取其主干，又按此法得出第二个代表v22，依此类推，则T1000分割成若干棵树：

同样，在含v22，v33，…的树中，v22，v33，…知道的消息在10天内都能传遍树的点集所代表的居民；

由于1000=11×

89+21，且每一个小分支树可能还有分支，从而其顶点数可能超过11，所以这样分法，至多分出89棵树并余下一个至多有21个点的树，该树的链长≤20，取此链的中心v，则该链上每个点到v的距离都≤10．现在取v11，v22，v33，…为代表，最后一棵树取其中心v为第90名代表，只要将消息告诉这些代表，则在10天之后，每个分支树的点集所表示的居民全都知道这个消息，问题已获解决．

说明注意每次在最长链上截去一段后，余下的链的主干不一定就是原来主干的截剩部分，所以每次都要重新确定主干．

例4一个国家的国王打算建n个城市且修（n－1）条道路，使每条道路连接两个城市而不经过其他城市．而每两个城市都可以互相到达，其间的最短距离恰是1，2，…，C＝n（n－1）这些数，问在下列情况下，国王的打算能否实现：

（1）n＝6；

（2）n＝1998．

分析就是要画一个树，使任两个顶点的距离都不能相同．对于顶点数少的情况估计是可能存在的，而要得到n＝6图可以用构造法．对于n＝1998，估计不会存在，所以可以用反证法证明．

为了得到n＝6的情形，长度为1与2的线段是要取的，否则得不到1，2，这两条线段连结可以得到长度3，为得到距离为15、14、…的线段，可以取某两个城市间距离为8（15的一半），此时8＋7＝15，8＋6＝14，8＋5＝13可以通过增加一条长度为5的线段如图得到，再增加一条长为4的线即可得到全部的15个数．

解

（1）n＝6时，国王的打算可以实现，城市和道路的分布可依据图所示．

⑵n＝1998时，国王的打算不能实现，因为符合要求的道路网存在的必要条件是：

n或（n－2）是完全平方数，证明如下：

用点表示城市，用线表示连接城市的道路，得到一个图G．由题设，知G是n阶连通图，又其线的数目恰为（n－1），故G是n阶树，因而G的任两点之间只存在唯一的通道．把G的顶点二染色：

任取一个点A，对于图中任一点，若它沿唯一的通道到A的距离是一个偶数，则把此点染红（A也应染红，因A到A的距离为0，0是偶数），否则染蓝．

设红点的数目为x，则蓝点的数目为y＝n－x．考虑距离为奇数的点对，易知：

两点之间的距离为奇数，当且仅当这两个点一红一蓝．由一个红点和一个蓝点组成的点对有xy个．又在1，2，…，n（n－1）中，当n（n－1）为偶数时，其中的奇数有n（n－1）个；

当n（n－1）为奇数时，奇数有[n（n－1）＋2]个．于是，如果国王的打算可以实现，则必须满足

xy＝n（n－1）①或xy＝[n（n－1）＋2]②．

此时，对于①，有4x（n－x）＝n（n－1），即4x2－4nx+n2－n＝0，

解得x＝，相应的y＝．

同样，对于②：

有x＝，y＝．

故只有n或（n－2）是完全平方数时，国王的愿望才可能实现．但1998和1998－2＝1996都不是完全平方数，故当n＝1998时，国王的打算不可能实现．

说明我们只证明了这个条件是必要条件，没有证明这个条件是充分的．对于n＝6，有6－2＝4是完全平方数，有可能存在满足要求的图，再通过构造出满足要求的图，才能确定解存在．

例5证明：

任意的9个人中，必有3个人互相认识或4个人互相不认识．

分析即证明，在任意的K9中，把边涂成红或蓝两种颜色，则必存在红色K3或蓝色的K4．或在一个有9个顶点的图G中，必存在K3，或在其补图中，存在K4．

证明⑴如果存在一个顶点，从这点出发的8条线中，有至少4条为红色，设从v1引出的4条线为红色，引到v2，v3，v4，v5．若此4点中的某2点间连了红色线，则存在红色K3，若此4点间均连蓝线，则存在蓝色K4．

⑵如果从任一点出发的8条线中，红色线都少于4条．于是从每点出发的蓝色线都至少5条．但由于任何图中的奇顶点个数为偶数，故不可能这9个顶点都引出5条蓝线．于是至少有一个顶点引出的蓝线≥6条，例如从v1到v2，v3，…，v7都引蓝线，则在v2，v3，…，v7这6个点的图中，必存在红色三角形或蓝色三角形，于是G中必有红色K3，或蓝色K4．

链接拉姆赛（Ramsey）问题

本题实际上说的是：

在有n个顶点的图G中，有一个K3，或在其补图中（在K9中去掉G的所有边后余下的图即G的补图）有一个K4，二者必有一成立．n＝9是保证这一个结论成立的n的最小值．一般的，在一个有t个顶点的图中存在Km，或在其补图中存在Kn，t的最小值是多少？

这就是拉姆赛问题．记满足上述要求的t的最小值为r（m，n）．

则有r（m，n）＝r（n，m），

r（1，n）＝r（m，1）＝1，r（2，n）＝n，r（m，2）＝m．

并可证：

定理一在m≥2，n≥2时，r（m，n）≤r（m，n－1）＋r（m－1，n）．

现在已经求出的r（m，n）有：

r（3，3）＝6，r（3，4）＝9，r（3，5）＝14，r（3，6）＝18，r（3，7）＝23；

r（4，4）＝18．

定理二设完全图KN的边涂了n种颜色，则在N充分大时，KN中必有一个同色三角形．设rn是使KN中有同色三角形存在在N的最小值，则

⑴r1＝3，r2＝6，r3＝17；

⑵rn≤n（rn－1－1）＋2；

⑶rn≤1＋1＋n＋n（n－1）＋…＋＋＋n!

．

上述两个定理都是拉姆赛定理的特例，更一般的结论请参阅单墫教授的有关图论的著作．例如《趣味的图论问题》等

3．平面α上有n条直线，把α分成若干区域，证明：

可以用两种颜色就可使相邻的区域都涂上不同的颜色．

4．在8×

8的棋盘上填入1~64的所有整数，每格填一个数，每个数填一次．证明：

总能找到两个相邻的格子（有公共边的两个方格就是相邻的方格），这两个方格中填的数相差不小于5．

5．证明：

任意14人中，必有3人互相认识或有5人互相不认识．

C类例题

例61990个人分成n组，满足

（a）每个组中没有人认识同组的所有的人；

（b）每个组中，任意三人中至少有两人互不认识；

（c）每个组中两个互不认识的人，必可在同组中恰好找到一个他们都认识的人．

在每一组中，各人在该组中认识的人数都相同．并求分组个数n的最大值．（1990亚洲与太平洋地区数学竞赛）

分析条件都是针对某一组的，所以证明应在某个组内进行，由于两点或连线，或未连线，故可以分两点未连线及两点已连线的情况证明．

要求组数最多，应使每组的人数最少．故求应每组人数的最小值．

解取其中一组M，设|M|＝m，用m个点表示组M中的人，若两人认识，则在相应点间连一条线．于是题设条件可写为：

（a）M中任何一点，与M中其余的点没有都连线，即设x∈M，用d（x）表示x在M中的次数．则d（x）≤m－1．

（b）M中没有连出三角形；

（c）设x，y∈M．若x，y未连线，则存在唯一z∈M，与x，y均连线．

原题即求证：

M中每个点向M中点连的线数均相等．

由于M中没有点与其余所有的点都连了线，故存在x，y∈M，且x，y未连线．由（c）存在惟一z∈M，且z与x，y都连了线．

⑴记M中除z外与x连线的点集为A，与y连线的点集为B，由（c），A∩B=，且由（b），A、B中任何两点均不相邻．对于p∈A，由于p与y不相邻，则有唯一点与p及y都相邻，此点必在B中，设为q，同样，B中任何一点q，也必与A中唯一点p相邻．且若p1、p2∈A，则在B中与它们相邻的点q1、q2互不相同，否则与（c）矛盾（p1、p2若与B中的q都连线，则它们与两个不同的点x及q都连了线）．这说明A与B的元素有一

一对应关系，|A|=|B|．则d（x）=d（y）．

⑵若x，y连线，则由（a），存在u∈M，u与x未连线，则d（x）=d（u）．若u与y也未连线，则由上证，d（u）=d（x）=d（y）．若u与y连线，则存在v∈M，v与y未连线，d（v）=d（y），当v与x未连线时，d（x）=d（v）=d（y）；

当v与x连线时，由（c），v与u必不连线，于是d（v）=d（u），从而d（x）=d（y）．故每组中的人认识本组的人数相同．

⑶为了求分组个数的最大值，应找出满足条件的组中人数的最小值，由（a），有x，y∈M，x与y不相邻．于是由（c），存在z∈M，与x、y都相邻．由（a），必还有u，u与z不相邻（否则z与同组的点都相邻）；

于是由（c），u必与x、y之一相邻，设u与x相邻，于是u与y不相邻．故又存在v与u、y相邻．这样就有了5个点．从而每组至少5个点．而图中5个点满足全部要求．

于是至多可分出1990÷

5＝398组．

例7给定平面上的点集P＝{P1，P2，…，P1994},P中任三点均不共线,将P中的所有的点任意分成83组，使得每组至少有3个点，且每点恰好属于一组，然后将在同一组的任两点用一条线段相连，不在同一组的两点不连线段，这样得到一个图案G，不同的分组方式得到不同的图案，将图案G中所含的以P中的点为顶点的三角形个数记为m（G）．

（1）求m（G）的最小值m0；

（2）设G*是使m（G*）＝m0的一个图案，若G*中的线段（指以P的点为端点的线段）用4种颜色染色，每条线段恰好染一种颜色．证明存在一个染色方案，使G*染色后不含以P的点为顶点的三边颜色相同的三角形．（1994年全国高中数学联赛）

分析估计当各组点数尽可能接近时三角形个数最少．因此只要证明当两组点数差≥2时，不能达到最小值．可以用逐步调整法来证明．第⑵小问可以用构造法来解．注意K5的边2染色时，可以找到不存在同色三角形的染色法，于是可以据此构造出满足要求的图来．

解：

设G中分成的83个子集的元素个数分别为ni（1≤i≤83），ni＝1994．且3≤n1≤n2≤…≤n83．

则m（G）=C．即求此式的最小值．

设nk+1＞nk+1．即nk+1－1≥nk+1．则C＋C－（C＋C）＝C－C＜0．这就是说，当nk+1与nk的差大于1时，可用nk+1－1及nk+1代替nk+1及nk，而其余的数不变．此时，m（G）的值变小．

于是可知，只有当各ni的值相差不超过1时，m（G）才能取得最大值．

1994=83×

24+2．故当81个组中有24个点，2个组中有25个点时，m（G）达到最小值．

m0＝81C＋2C＝81×

2024＋2×

2300＝168544．

⑵取5个点为一小组，按图1染成a、b二色．这样的五个小组，如图2，每个小圆表示一个五点小组．同组间染色如图1，不同组的点间的连线按图2染成c、d两色．这25个点为一组，共得83组．染色法相同．其中81组去掉1个点及与此点相连的所有线．即得一种满足要求的染色．

例8有n人聚会，已知每人至少认识其中的个人．而对任意的个人，或者其中有两人认识，或者余下的n－人中有两人相识．证明：

当n≥6时，这n个人中必有3人两两认识．（1996年全国联赛）

分析本题与例6类似，要通过分析连线的情况找出三角形来．由于题中给出了，故应分n为偶数或奇数的情况分别讨论．

证明作一个图，用n个点表示这n个人，凡二人认识，则在表示此二人的点间连一条线．问题即，在题设条件下，存在以这n点中的某三点为顶点的三角形．设点a连线条数最多，在与a连线的所有点中点b连线最多，与a连线的点除b外的集合为A，与b连线的点除a外的集合为B．

1°

设n＝2k，则每点至少连k条线，集合A、B中都至少有k－1个点．

⑴若存在一点c，与a、b都连线，则a、b、c满足要求；

⑵若没有任何两点与a、b二点都连线（图1），则由A∩B＝，|A∪B|≤2k－2，|A|≥k－1，|B|≥k－1，故得|A|＝|B|＝k－1，且图中每点都连k条线．若A中任何两点间均未连线，B中任两点也未连线，则A∪{b}中不存在两点连线，B∪{a}中也不存在两点连线．与已知矛盾．故在A（或B）中必存在两点，这两点间连了一条线，则此二点与a（b）连出三角形，

2°

设n＝2k+1．则每点至少连k条线，A、B中都至少有k－1个点．

⑵若没有任何两点与此二点都连线，且|A|≥k，则由|B|≥k－1（图2），A∩B＝，|A∪B|≤2k－1，可得|A∪B|＝2k－1，|A|＝k，|B|＝k－1，若A中任何两点间均未连线，B中任两点也未连线，则A∪{b}中不存在两点连线，B∪{a}中也不存在两点连线．与已知矛盾．故A（或B）中存在两点，这两点间连了一条线，则此二点与a连出三角形，

⑶若没有任何两点与此二点都连线，且|A|＝k－1，即每点都只连k条线．这时，必有一点与a、b均未连线，设为c（图3）．c与A中k1个点连线，与B中k2个点连线，k1+k2＝k，且1≤k1，k2≤k－1．否则若k2＝0，则A∪{b}中各点均未连线，B∪{a，c}中各点也未连线．矛盾．故k1，k2≥1．且由于n≥6，则k1＋k2≥3，故k1，k2中至少有一个不小于2，不妨设k1≥2，现任取B中与c连线的一点b1，由于b1与B中其余各点均未连线，若b1与A中的所有与c连线的点均未连线，则b1连线数≤2+k－1－k1≤k－1，矛盾，故b1至少与此k1个点中的一点连线．故证．

6．在正整数n与δ满足什么条件时，可以作出一个n阶δ正则图．

即是：

已知n个点，其中某些点间连了一条线，且每个点都恰好与δ个点连了线．问δ可以取什么样的数值？

7．某次体育比赛，每两名选手赛一场，每场一定决出胜负，通过比赛确定优秀选手，选手A被确定为优秀选手的条件为：

对任何其他选手B，或A胜B，或存在选手C，有A胜C而C胜B．如果按这个条件确定的优秀选手只有1名．求证：

这名选手胜所有其余的选手．（1988年中国数学冬令营）

8．给定空间中的9个点，任意4点不共面，每两点间连一线段．求最小的n值，使当对其中任意n条线段用红、蓝两色之一任意染色时，都一定出现一个三边同色的三角形．（1992中国数学奥林匹克）

习题13

1．⑴如果在偶图G=（X，Y，E）中，|X|>

|Y|，且X中每个顶点的次数都不小于δ，求证：

Y中至少有一个顶点的次数>

δ．

⑵若图G为偶图，且G有圈，则G的圈的长为偶数．反之，若图G有圈，且所有的圈长为偶数，则G为偶图．

2．设C是100阶3正则图，现用红、白两色给这100个点着色，其中红点40个，白点60个，如果一条线的两个端点都是红色，则将这条线也染成红色；

如果一条线的两个端点都是白色，则将这条线也染成白色，现已知红色线有38条，问白色线有多少条？

3．若干人相聚，其中有些人彼此认识，若⑴如果某两个人认识的人数相等，则他们没有共同的熟人；

⑵有一个人至少有100个熟人．证明：

可以找到一个参加聚会的人，他恰好有100个熟人．

4．有2n个学生，每天出去散步，每两人一组，如果每一对学生只在一起散步一次，这样的散步至多可以持续多少天？

5．20名选手参加14场单打比赛，每名选手都至少参加过1场．证明：

必有某6场比赛的参赛者是12名不同的选手．（1989年美国数学竞赛）

6．在nn棋盘的方格中分别填写1，2，…，n2（n≥2），每格一个数．证明：

必有两个相邻方格（有公共边的方格），方格中的两个数的差至少为n．（1988年捷克数学竞赛）

7．把Kn中的每条线段染上红色或蓝色．把某一点出发引出两条同色线段组成的角叫做同色角．证明：

同色角的总数不小于n（n－1）（n－3）．

8．用黑白两种颜色去涂正九边形的顶点，每个顶点只涂黑、白两色之一，证明：

在以这九点为顶点的所有三角形中，必有两个顶点同色的全等三角形．

9．⑴将完全图K5中的10条线段进行染色，使得有公共端点的线颜色不相同．至少要用几种颜色？

⑵将完全图K2n中的所有线段染上颜色，使得有公共端点的线颜色不相同．至少要用几种颜色？

⑶证明：

将完全图K2n－1中的所有线段染上颜色，使得有公共端点的线颜色不相同．至少要用2n－1种颜色．

10．某团体中任意两个认识的人都没有共同的熟人，而任意两个不认识的人都恰有两个彼此共同的熟人．证明：

该团体中每个人认识的人数都相同．（1975南斯拉夫数学竞赛）

11．某次体育比赛，每两名选手各赛一场，无平局．通过比赛确定优秀选手．设A为选手，如果对其他任意选手B，要么A胜B，要么存在选手C，使得A胜C，C胜B，则A即是优秀选手．证明：

如果按上述规则选出的优秀选手只有1名，则这名选手胜其他所有的选手．（1987年中国数学奥林匹克）

12．排球比赛中，每两队都各比赛一场．对两个球队A与B，如果A胜B，或者存在某个球队C，使得A胜C，C胜B，则称A优于球队B．比赛结束后，优于其他所有球队的球队即被授予冠军称号．比赛结束后能否恰有两个冠军队？

（1988年前苏联数学竞赛）

本节“情景再现”解答：

1．证明任取树T的一个悬挂点v1，把v1涂红，所有与v1距离为奇数的顶点都涂蓝，所有与v1距离为偶数的顶点都涂红，所有涂红的顶点组成集合X，所有涂蓝的顶点组成集合Y，则得到一个二色图，即为偶图．

2．证明设G＝（X，Y，E）是偶图，把X中的点全部涂成红色，把Y中的点全部涂成蓝色，则所得的图中，相邻的顶点涂色都不同，即只用2色即可涂完G的所有顶点，使相邻的顶点涂色不同．又如果G没有边，则只用1种颜色即可把G的所有顶点涂好，且没有任何相邻的顶点同色（因没有顶点相邻），故偶图的色数≤2．

反之若图G的色数≤2，若色数＝1，表示G中任何两顶点都不相邻，即G没有边，此时，设G为n阶的，可把G中k（1≤k≤n－1）个点涂成一种红色，另外n－k个点涂成蓝色，即得一个二色图，涂红的点集为X，涂蓝的点集为Y，即为偶图．若色数＝2，即用两种颜色可以把所有顶点涂色，且同色点都不相邻，则取涂一种颜色的点的集合为X，涂另一种颜色的点的集合为Y，则得到一个偶图．即色数≤2的图是偶图．

3．证明n=1时，1条直线把平面分成2部分，可用两种颜色涂．

设n=k时，k条直线把平面分成的区域有满足题意的涂色法，当n=k+1时，先画出其中k条直线，而暂把第k+1条直线擦去．这时k条直线把平面分成的区域可以涂色．涂好色后，把第k+1条直线画出，凡在这条直线某一侧的部分，涂色不动，而在直线另一侧的部分，把涂的色全部改为另一色，则所得涂色满足题意．即n=k+1时，命题成立．

4．证明取每个方格的中心，凡是相邻的两个方格，就把相应的中心连一条线．这样得到了一个图G（图中红线组成的图即为图G）．

图G的的直径=14，，故图G中任意两点的距离≤14．

若相邻两个方格中填的数相差<

5，则差≤4，于是图G中所填两个数的差≤14×

4=56．但图中填了1与64，此二数必有一条链相连，此链的长≤14．即其差≤56，与64－1=63矛盾．

以点表示人，红色线表示认识，蓝色线表示不认识．

⑴若存在一个点，从这点引出了至少5条红线，例如从v1向v2，v3，…，v6引出了5条