打印版
第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条线，则称该图为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的边染成红蓝两色，求证：其中必有两个三角形，其三边同色． 分析 ⑴ 以点表示人，连红、蓝两色的线分别表示“认识”与“不认识”，问题转化成图的问题．要会把题目的语言转译成图的语言：“三人互相认识”就表示三点间都连红线，“三人互不认识”就表示三点间都连蓝线．⑵ 考虑每个异色三角形的三个角，其中两个角是异色角，而同色三角形的三个角都是同色角．
打印版
打印版
证明 ⑴ 用6个点v1，v2，…，v6表示这6个人，如果某两人相互认识，则在表示此二人的点间连一条红线，否则连一条蓝线．于是问题转化为证明此6点间一定连出了三边均为红色或蓝色的三角形．
在点v1连出的5条线中，由抽屉原理知，必有某色线连有3条或3条以上．不妨设红线连了至少3条．设v1与v2、v3、v4连的红线．现考虑点v2、v3、v4连线的情况，如果此三点间有任两点连的红线，则出现红色三角形(例如v2v3连红线，则v1v2v3是红色三角形)，如果这三点间都不连红线，则出现蓝色三角形(v2v3v4是蓝色三角形)．故证．
⑵ 考虑K6共连了C6＝15条线，共得到C6＝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条线．它不能连成三角形，也不能连成四边形，
打印版
2
3
打印版
否则余下的点无法连线，故只能如图所示，证毕．
说明 仔细体会上述两例的特点，明白什么时候应该用图来解相关的题：当涉及多个元素的某些相互关系时，就可能用图来解释．
情景再现
1．在例1中，把6个人改为5个人，结论是否一定成立？
2．图G有n个顶点，n+1条边，证明：图G至少有一个顶点的次数≥3．
B类例题 例3 设竞赛图(每两个点都连了1条线的有向图)中，点Ak的出次与入次分别为wk与ek(k＝1，2，…，n)，
证明 w1＋w2＋…＋wn＝e1＋e2＋…＋en．
分析 根据竞赛图的特点可知：⑴ 每点的出次与入次的和都等于n－1，⑵ 所有点的出次的和与入次的和相等．由此可以推出：所有点的出次1
和与入次和都等于n(n－1)．这是两个基本的性质．在要证的式子中把ek
2用n－1－wk代替．
证明 对于每个点，出次与入次的和都是n－1，即
wk＋ek＝n－1(k＝1，2，…，n)， ①
所有出次的和与所有入次的和相等，且都等于图中弧的条数：
1
w1＋w2＋…＋wn＝e1＋e2＋…＋en＝n(n－1)．②
2所以 e1＋e2＋…＋en
＝(n－1－w1)2＋(n－1－w2)2＋…＋(n－1－wn)2
＝n(n－1)2＋w1＋w2＋…＋wn－2(w1＋w2＋…＋wn)(n－1)
打印版
2
2
2
2
2
2
2
2
2
2
2
2
人教版数学-江苏省数学竞赛第67讲 图论问题(一)
