第67讲图论问题竞赛教案.docVIP

第67讲 图论问题(一) 本节主要内容是：把一个具体问题用图形表示出来，利用图形的直观性可能更有利于问题的解决． 有关的一些概念：由若干个不同的点及连接其中某些的线所组成的图形就称为．图中的点的集合称为图的，记为V：V＝{v1，v2，，vn，}；图中的线的集合称为图的，记为E：E＝{vivj}(vi，vj∈V)．故一个图由其点集V和线集E所决定，若用G表示图，则记为G＝G(V；E)．含有n个点的图称为n．在一个图中，如果某点v共连了k条线，则说此点的“”(或“”)为k，记为degvk.如果一个p阶图的每两个顶点间都连且只连了1条线，则称该图为p阶完全图，记为Kp若对每条线确定一个方向(确定了线的两个端点中一个为“起点”，另一个为“终点”．这时，线是点的“有序对”)，则得到“有向图”；v，degv＝k，若v是其中n条边的起点，m条边的终点(m＋n＝k)，则称v的出次为n，入次为m． 链：若在一个图中取n+1个顶点 v1、v2、、vn+1，每两个相邻的顶点vi、vi+1间连有一条边li,则边l1,l2,,ln就称为从v1到vn+1的一条链n称为链的长度A类例题 例1 ⑴证明任意的六人中一定有三个人互相认识或互不认识(约定甲认识乙就意味着乙认识甲)⑴ 以点表示人，连红、蓝两色的线分别表示“认识”与“不认识”，问题转化成图的问题．要会把题目的语言转译成图的语言：“三人互相认识”就表示三点间都连红线，“三人互不认识”就表示三点间都连蓝线．⑵ 考虑每个异色三角形的三个角，其中两个角是异色角，而同色三角形的三个角都是同色角． 证明 ⑴ 用6个点v1v2，…，v6表示这6个人，如果某两人相互认识，则在表示此二人的点间连一条红线，否则连一条蓝线．于是问题转化为证明此6点间一定连出了三边均为红色或蓝色的三角形． 在点v1连出的5条线中，由抽屉原理知必有某色线有3条或3条以上．不妨设红线连了3条．设v1与v2、v3、v4连的红线．现考虑v2、v3、v4连线的情况，如果此三点间有任两点连的红线，则出现红色三角形v2v3连红线，则v1v2v3是红色三角形)，如果这三点间都不连红线，则出现蓝色三角形v2v3v4是蓝色三角形)．故证．＝15条线，共得到C＝20个三角形．设第i个顶点连了ri(0≤i≤5)条红线，5－ri条蓝线．由于ri(5－ri)≤6．所以，连出的异色角个数≤6×6＝36个．由于每个异色的三角形有2个异色角，所以图中异色三角形个数≤18，故图中同色三角形个数≥20－18＝2． 说明 题⑴是早期匈牙利的一个图论竞赛题．解这类“实际问题”时，重要的是会用图的语言解释题意，把实际问题改写为图的问题． ⑵ 用异色角来解相关问题是较好的方法． 例2 由5人组成一个公司，其中任意三人总有2人彼此认识，也总有2人彼此不认识．证明：这五人可以围桌而坐，使每人两旁都是他认识的人．(1978年保加利亚数学竞赛) 证明 用5个点表示这5个人，若两人互相认识，则在表示这2个人的点间连1条线．题目的条件即是：任三点间至少连1条线，但不能连3条线． 首先，每点都至少连了2条线，若点v1只连出1条线，则它至少与某三点(设为v2、v3、v4)未连线，则此3点间都要连线(若v2与v3没有连线，则v1与v2、v3就都没有连线，与已知矛盾)．出现了以v2、v3、v4为顶点的三角形，矛盾． 其次，若某点连出了3条线，则此三点间都不能连线，与已知矛盾． 故知：每点都恰连2条线．它不能连成三角形，也不能连成四边形，否则余下的点无法连线，故只能如图所示，证毕． 说明 仔细体会上述两例的特点，明白什么时候应该用图来解相关的题：当涉及多个元素的某些相互关系时，就可能用图来解释． 情景再现 1．在例1中，把6个人改为5个人，结论是否一定成立？2．图G有n个顶点，n+1条边，证明：图G至少有一个顶点的次数≥3． B类例题 例3 设竞赛图(每两个点都连了1条线的有向图)中，点Ak的出次与入次分别为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(n－1)2＋w＋w＋…＋w－2(w1＋w2＋…＋wn)(n－1) ＝w＋w＋…＋w＋n(n－1)