2012江苏省数学竞赛《提优教程》教案：第67讲_图论问题(一)

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

1、第67讲图论问题(一)本节主要内容是：把一个具体问题用图形表示出来，利用图形的直观性可能更有利于问题的解决．有关的一些概念：由若干个不同的点及连接其中某些点对的线所组成的图形就称为图．图中的点的集合称为图的点集，记为V：V＝{v1，v2，…，vn，…}；图中的线的集合称为图的线集(边的集合)，记为E：E＝{vivj}(vi，vj∈V)．故一个图由其点集V和线集E所决定，若用G表示图，则记为G＝G(V；E)．含有n个点的图称为n阶图．在一个图中，如果某点v共连了k条线，则说此点的“次数”(或“度数”)为k，记为degv＝k.如果一个p阶图的每两个顶点间都连且只连了1

2、条线，则称该图为p阶完全图，记为Kp．若对每条线确定一个方向(即确定了线的两个端点中一个为“起点”，另一个为“终点”．这时，线是点的“有序对”)，则得到“有向图”；对有向图的一个顶点v，degv＝k，若v是其中n条边的起点，m条边的终点(m＋n＝k)，则称v的出次为n，入次为m．链：若在一个图G＝(V；E)中取n+1个顶点v1、v2、…、vn+1，每两个相邻的顶点vi、vi+1间连有一条边li,则边l1,l2,…,ln就称为从v1到vn+1的一条链．n称为链的长度．A类例题例1⑴证明任意的六人中一定有三个人互相认识或互不认识(约定甲认识乙就意味着乙认识甲)．⑵K6

3、的边染成红蓝两色，求证：其中必有两个三角形，其三边同色．分析⑴以点表示人，连红、蓝两色的线分别表示“认识”与“不认识”，问题转化成图的问题．要会把题目的语言转译成图的语言：“三人互相认识”就表示三点间都连红线，“三人互不认识”就表示三点间都连蓝线．⑵考虑每个异色三角形的三个角，其中两个角是异色角，而同色三角形的三个角都是同色角．证明⑴用6个点v1，v2，…，v6表示这6个人，如果某两人相互认识，则在表示此二人的点间连一条红线，否则连一条蓝线．于是问题转化为证明此6点间一定连出了三边均为红色或蓝色的三角形．在点v1连出的5条线中，由抽屉原理知，必有某色线连有3条或3

4、条以上．不妨设红线连了至少3条．设v1与v2、v3、v4连的红线．现考虑点v2、v3、v4连线的情况，如果此三点间有任两点连的红线，则出现红色三角形(例如v2v3连红线，则v1v2v3是红色三角形)，如果这三点间都不连红线，则出现蓝色三角形(v2v3v4是蓝色三角形)．故证．⑵考虑K6共连了C＝15条线，共得到C＝20个三角形．设第i个顶点连了ri(0≤i≤5)条红线，5－ri条蓝线．由于ri(5－ri)≤6．所以，连出的异色角个数≤6×6＝36个．由于每个异色的三角形有2个异色角，所以图中异色三角形个数≤18，故图中同色三角形个数≥20－18＝2．说明题⑴是早期

5、匈牙利的一个图论竞赛题．解这类“实际问题”时，重要的是会用图的语言解释题意，把实际问题改写为图的问题．⑵用异色角来解相关问题是较好的方法．例2由5人组成一个公司，其中任意三人总有2人彼此认识，也总有2人彼此不认识．证明：这五人可以围桌而坐，使每人两旁都是他认识的人．(1978年保加利亚数学竞赛)证明用5个点表示这5个人，若两人互相认识，则在表示这2个人的点间连1条线．题目的条件即是：任三点间至少连1条线，但不能连3条线．首先，每点都至少连了2条线，若点v1只连出1条线，则它至少与某三点(设为v2、v3、v4)未连线，则此3点间都要连线(若v2与v3没有连线，则v1

6、与v2、v3就都没有连线，与已知矛盾)．出现了以v2、v3、v4为顶点的三角形，矛盾．其次，若某点连出了3条线，则此三点间都不能连线，与已知矛盾．故知：每点都恰连2条线．它不能连成三角形，也不能连成四边形，否则余下的点无法连线，故只能如图所示，证毕．说明仔细体会上述两例的特点，明白什么时候应该用图来解相关的题：当涉及多个元素的某些相互关系时，就可能用图来解释．情景再现1．在例1中，把6个人改为5个人，结论是否一定成立？2．图G有n个顶点，n+1条边，证明：图G至少有一个顶点的次数≥3．B类例题例3设竞赛图(每两个点都连了1条线的有向图)中，点Ak的出次与入次分别为

7、wk与ek(k＝1，2，…，n)，证明w＋w＋…＋w＝e＋e＋…＋e．分析根据竞赛图的特点可知：⑴每点的出次与入次的和都等于n－1，⑵所有点的出次的和与入次的和相等．由此可以推出：所有点的出次和与入次和都等于n(n－1)．这是两个基本的性质．在要证的式子中把ek用n－1－wk代替．证明对于每个点，出次与入次的和都是n－1，即wk＋ek＝n－1(k＝1，2，…，n)，①所有出次的和与所有入次的和相等，且都等于图中弧的条数：w1＋w2＋…＋wn＝e1＋e2＋…＋en＝n(n－1)．②所以e＋e＋…＋e＝(n－1－w1)2＋(n－1－w2)2＋…＋(n－1－wn)2＝n

8、(n－1)