《提优教程》2012江苏省高中数学 第68讲 图论问题(二)竞赛教案.doc

《《提优教程》2012江苏省高中数学 第68讲 图论问题(二)竞赛教案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第68讲图论问题(二)本讲主要内容：本讲将继续研究用图来解决问题的方法．偶图取图G＝(V，E)，如果V＝X∪Y，X∩Y＝Æ，其中X＝{x1，x2，…，xn}，Y＝{y1，y2，…，ym}，且xi与xj(1≤i＜j≤n)，ys与yt(1≤s＜t≤m)均互不相邻，则称G为偶图．色数：将图G的顶点涂上颜色，如果至少要k种颜色才能使任意两个相邻的顶点颜色不同，则称G的色数为k．显然，偶图的色数≤2．即偶图色数不超过2．A类例题例1在空间中给定2n个不同的点A1，A2，…，A2n，n＞1，其中任意三点不共线．设M是n2+1条以给定的点为端点的线段的集合．⑴证明：存在一个三角形，其顶点为给定的点，其

2、边都属于M．⑵证明：若集合M的元素不超过n2个，则这样的三角形可能不存在．(1973年奥地利数学竞赛)分析可以从简单的情况开始试验，发现规律再证明．从K4(4阶完全图，见67讲)共有多少条线及多少个三角形、擦去1条线去掉几个三角形入手得出结论，对于K5、K6也能用此法得到结论，但对于p＞6，Kp难用此法，如何过渡到一般情况？可以用数学归纳法．证明：n＝2时，在4个点间连了5条线，由于4阶完全图在4个点间共可连出6条线，这6条线连出了4个以此4点中的某3点为顶点的三角形．而每条线的两个端点与(除这条线的两个端点外的)另两个顶点可以连出共2个三角形，故去掉任何一条边都使连出三角形数减少2，于

3、是在4个点间连5条线必连出了以此4点中的3点为顶点的三角形．设n＝k时，2k个点间连有k2＋1条线时，必有三角形出现．则当n＝k＋1时，2(k＋1)个点间连了(k＋1)2＋1条线．此时，任取两个相邻的顶点v1，v2，如果在其余的顶点中有某个顶点与v1，v2都连了线，例如v3与v1，v2都连了线(图4(1))，则出现了三角形．如果其余所有的点与此二点都至多连出1条线(图4(2))，则去掉点v1，v2及与这两点相邻的边，此时，余下2k个点，至多去掉了2k＋1条边，余下至少(k＋1)2＋1－(2k＋1)＝k2＋1条边，由归纳假设知，其中必有三角形．综上可知，命题成立．说明若2n个点间连了n2条

4、边，可以把这2n个点分成两组，每组n个点，规定同组的点间都不连线，不同组的任何两点都连1条线，这样得到了一个完全偶图Kn，n，此时共计连了n2条线，但任取三点，必有两点在同一组，它们之间没有连线，于是不出现三角形．例2一个舞会有n(n≥2)个男生与n个女生参加，每个男生都与一些女生(不是全部)跳过舞，而每个女生都至少与1名男生跳过舞，证明，存在男生b1，b2与女生g1，g2，其中b1与g1跳过舞，b2与g2跳过舞．但b1与g2没有跳过舞，b2与g1没有跳过舞．分析就是要给出一种选择方法，按此方法操作，即可选出满足要求的两个男生与两个女生．可以用极端原理来证明这样的存在性命题．证明取所有男

5、生中与女生跳舞人数最多的一个，设是b1．b1至少与1名女生没有跳过舞，取没有与b1跳过舞的一名女生为g2，g2至少与1名男生跳过舞，设为b2，显然b1不是b2，现在考虑所有没有与b2跳过舞的女生，她们不能都没有与b1-12-跳过舞，(否则没有与b1跳舞的女生人数就比没有与b2跳舞的人数多，b1就不是与女生跳舞人数最多者)．即至少有1个女生没有跟b2跳过舞但跟b1跳过舞．这个女生即为g1．说明这里就得到了一个偶图{b1，b2}∪{g1，g2}．(图中，括号内的数字表示证明中出现的先后顺序)．极端原理常用于证明存在性命题．情景再现1．求证：顶点多于1的树是偶图．2．证明偶图的色数≤2，反之，

6、色数≤2的图是偶图．B类例题例3某镇有居民1000人，每人每天把昨天听到的消息告诉自己认识的人，已知任何消息只要镇上有人知道，都会经过这样的方式逐渐地为全镇的人所知道．证明可以选出90名代表，使得同时向他们报告一个消息，经过10天，这一消息就为全镇的人知道．分析就是要给出一个把1000个点的连通图分成90个子图的方法，使每个点都在其中一个子图中，且每个子图的最长的链的长度不超过10．这样，只要把每个子图的最长链的一个端点选为“代表”，就能完成这个任务．证明用1000个点代表1000个居民，两名居民相识，则在两点之间连一线，如此可得一图，依条件，这个图是连通图．若图中有圈，则我们去掉圈中的

7、一边使圈被破坏而不影响图的连通性，经过有限次这种手续，可得树T1000．在T1000中取一条主干v1v2…vn，取v11作为1个代表，把边v11v12去掉，则此图分成了2个连通分支，在含有v1的一棵树中，每点到v11的路的长度都不超过10，否则v1v2…vn在T1000中不是主干，故v11知道的消息在10天内可以传遍它所在分支的点集所代表的居民；余下另一分支再取其主干，又按此法得出第二个代表v22，依此类推，则T1000分割成若干棵