第68讲图论问题(二)竞赛教案.docVIP

  1. 1、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。。
  2. 2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  3. 3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  4. 4、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  5. 5、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  6. 6、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  7. 7、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
第68讲图论问题(二)竞赛教案

第68讲 图论问题(二) 本讲主要内容:本讲将继续研究用图来解决问题的方法. 偶图 取图G=(V,E),如果V=X∪Y,X∩Y=(,其中Xx1,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条以给定的点为端点的线段的集合.⑴证明:存在一个三角形,其顶点为给定的点,其边都属于M.⑵证明:若集合M的元素不超过n2个,则这样的三角形可能不存在.(1973年奥地利数学竞赛) 分析 可以从简单的情况开始试验,发现规律再证明.从K4(4阶完全图,见67讲)共有多少条线及多少个三角形、擦去1条线去掉几个三角形入手得出结论,对于K5、K6也能用此法得到结论,但对于p>6,Kp难用此法,如何过渡到一般情况?可以用数学归纳法. 证明:n=2时,在4个点间连了5条线,由于4个点间共可连出6条线,这6条线连出了4个以此4点中的某3点为顶点的三角形.而每条线的两个端点与(除这条线的两个端点外的)另两个顶点可以连出共2个三角形,故去掉任何一条边都使连出三角形数减少2,于是在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条边,可以把这2n个点分成两组,每组n个点,规定同组的点间都连线,不同组的任何两点都连1条线,这样得到了一个完全偶图Kn,n,此时共计连了n2条线,但任取三点,必有两点在同一组,它们之间没有连线,于是不出现三角形. 一个舞会有n(n2)个男生与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个点代表1000个居民,两名居民相识,则在两点之间连一线,如此可得一图,依条件,这个图是连通图.若图中有圈,则我们去掉圈中的一边使圈被破坏而不影响图的连通性,经过有限次这种手续,可得树T1000. 在T1000中取一条主干v1v2vn,取v11作为1个代表,把边v11v12去掉,则此图分成了2个连通分支,在含有v1的一棵树中,每点到v11的路的长度都不超过10,否则v1v2vn在T1000中不是主干,故v11知道的消息在10天的点集所代表的居民;余下另一分支再取其主干,又按此法得出第二个代表v22,依此类推,则T1000分割成若干棵树:同样,在含v22,v33,的树中,v22,v33,知道的消息在10天树的点集代表的居民;由于1000=11×9+21,这样分法,至多分出89棵树余下至多21个点的链长20,取此链的中心v,则v的距离都≤10.现在取v11,v22,v33,为代表,最后一棵树取其中心v为代表,只要将消息告诉这些代表,则在10天之后,树的点集所表示的居民全都知道这个消息问题已获解决. 例4

文档评论(0)

2017ll + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档