第67讲图论问题一习题导学案教案奥数实战演练习题Word文件下载.docx

第67讲图论问题一习题导学案教案奥数实战演练习题Word文件下载.docx

《第67讲图论问题一习题导学案教案奥数实战演练习题Word文件下载.docx》由会员分享，可在线阅读，更多相关《第67讲图论问题一习题导学案教案奥数实战演练习题Word文件下载.docx（23页珍藏版）》请在冰点文库上搜索。

在点v1连出的5条线中，由抽屉原理知，必有某色线连有3条或3条以上．不妨设红线连了至少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．

说明题⑴是早期匈牙利的一个图论竞赛题．解这类“实际问题”时，重要的是会用图的语言解释题意，把实际问题改写为图的问题．

⑵用异色角来解相关问题是较好的方法．

例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

＝（n－1－w1）2＋（n－1－w2）2＋…＋（n－1－wn）2

＝n（n－1）2＋w

－2（w1＋w2＋…＋wn）（n－1）

＝w

＋n（n－1）2－2´

（n－1）（n－1）

＝w

说明本题的证明方法与《奇偶分析》中的例6相似．

例4平面上给定7个点，用一些线段连接它们，每三个点中至少有两点相连，问至少要有多少条线段？

试给出一个图．（1989蒙古数学竞赛）

分析首先找到连线条数的下界（即至少要连出多少条线），再寻找是否可能达到这个下界，可以分别枚举可能的连线方法，讨论每种方法的连线条数，得到最小的结果．

解7个点中共有三点组C

=35个．每条线段共与其余5点组成5个三角形．故线段条数≥

＝7条．

如果有一个点没有连线，则其余6点两两都必须连线，要C

＝15条．

如果有一点只连了一条线，其余5点必须两两连线，连线数＞C

＝10条．

设某点只连了2条线，如点A只连了AB、AC这2条线，则其余4点均未与A连线，于是它们必须两两互连，应连C

=＝6条．此时，取B、C两点及其余4点中的任一点，尚不满足条件，故BC应连线，此时连了9条线，所得图形满足题目要求．

若每点都至少连出3条线，则总度数≥21，即至少连了[

]+1＝11条线．

所以，至少连9条线．

例5九名数学家在一次国际会议上相遇，发现他们中的任三人中至少有两人能用同一种语言对话，如果每个数学家至多会用三种语言．证明：

至少有三人可用同一种语言对话．（1978年美国数学竞赛）

分析9个人用9个点表示．证法1中，多种语言则用多种颜色的线来表示，转译结论“三人可用同一种语言对话”时，应注意：

如果从一点向另两点连出了同色的两条线，表示另两人也能用相应的语言对话，从而就出现了同色三角形．所以，只要证明从一点一定引出了同色的线即可．而在证法2中，改设若二人不能对话就连1条线（即不存在二人都会的语言）．此时结论就应转译为“存在三点，两两都没有连线”．

证法1用9个点表示这9个人，某二人如能用第r种语言交谈，则在表示此二人的点间连一条线，并涂上第r种颜色，于是，本题即是证明，存在一个同色的三角形．

首先，若v1与v2、v1与v3间都连了第k种颜色线，则v2与v3间也要连第k种颜色线．此时即出现同色的三角形．所以只要证明从其中某一点出发的线中必有两条线的颜色相同．

反设从任一点出发的线中没有同色的线，由于每个人至多会用三种语言．即degvi≤3，于是v1至少与5个点不邻接，设为v2、…、v6，同样，v2至少与5个点不相邻接，于是v3、…、v6中至少有一点与v2不相邻接．设为v3，于是v1、v2、v3不相邻接．与已知“任三人中都至少有两人能用同一种语言对话”矛盾．故证．

证法2取9个点v1，v2，…，v9表示9个人，如果某二人不能对话，则在表示此二人的点间连一条线，于是在任何三点间，都有两个点不相邻，即不存在三角形．

如果有人至少与4个点不连线，由于他最多只能讲三种语言，则他必与其中某两人讲同一种语言．于是相应三人可以用同一种语言来对话．

下面证明存在一点，其度不大于4．从而该点至少与4点不相邻．如果degv1≤4，则v1即为所求．若degv1＞4，则至少degv1＝5，即至少有5个点与之连线，设为v2，…，v6，由于这些点不能连出三角形，故v2，…，v6的任何两个之间都不能连线，从而v2与v3，…，v6均无连线，于是degv2≤4．即可证得原题．

说明两点间连了1条线，则说这两点相邻．

本题的两种证明方法从两个方向出发，一种是两人可用同一种语言通话，就在相应两点间连一条边，证法2是反过来，两人不能通话时则连一条边，都能应用图解决问题．

例6俱乐部里有14个人想打桥牌，已知过去每个人都与其中的5个人合作过，现在规定4个人中必须任两个人都没有合作过才准许在一起打1局桥牌，这样打了3局就无法再打下去了，如果这时又来了一人，他与原来的14个人都没有合作过，证明：

一定可以再打1局．

分析打桥牌时，4人分成合作的两对，合作的两人坐在相对的位置打牌．于是每局桥牌，都有两对人合作．

把题目的条件与结论都转述为图的语言，并找出结论的等价命题是：

找到三个人互相都没有合作过，即存在3个点互不相邻．

证明用14个点表示这14个人，若某两人合作过，则在表示这两人的点间连一条线，于是，题目条件即：

其中每个点都已连出了5条线，且在此14个点中，可以找出3组点（每组4个点），这三组点间，两两未连线，若这3组点之间共连出6条线后，对于任意4点，都至少有两点连了线．（14个点间一共连了41条线），证明此时一定存在3个点，两两都没有连线（从而添入第15个点后，可与此3点合成4点，两两无连线）．

由于14个点中的每个点原来都与（14－1－5＝）8个点不相邻．在又打3局连出了6条边以后，至多有12个点又连了线，所以至少还有2个点，每个点仍与8个点不相邻．设其中一点为v1．与v1不相邻的点集为S．

下面证明：

S中必有一点v2至少与7个点不相邻．反设不存在这样的点，则此8点中，每个点都至多与6个点不相邻，故此8个点都至少连了（14－6－1＝）7条边，于是此8点中的每个点又都新连了至少2条边，故又新连出了8×

2÷

2＝8条边（除以2是因为每条边可能在两个点端点处被计算了2次）．这与只连了6条边矛盾，所以存在S中的一点v2，至少与7个点不相邻．

但8+7＝15＞14，必有一点v3与v1，v2均未连线．此三点即为所求．

链接v3存在是根据容斥原理：

把这14个人的集合记为S，与v1相邻的点集记为A，与v2相邻的点集记为B，则A∪BS．故

card（A∪B）≤card（S）．

而card（A∪B）＝card（A）＋card（B）－card（A∩B），

故card（A）＋card（B）－card（A∩B）≤card（S），

现card（A）＋card（B）＝15，card（S）＝14，于是card（A∩B）＞0．

3．⑴右面的有向图由4个顶点及一些弧（有向线段）组成，指出各点的出次（引出的弧的条数）与入次（引入的弧的条数）．

⑵求出上题中所有各点的出次的和与入次的和，它们与弧的条数有什么关系？

⑶证明：

任一有向图中，出次的和与入次的和相等．

4．在n（n≥3）个点的竞赛图中，一定有两个点的出次相同吗？

5．在集合S的元素之间引入关系“→”．⑴对于任意两个元素a，b∈S，要么a→b，要么b→a，二者有且只有一个成立；

⑵对任意三个元素a，b，c，如果a→b，b→c，则c→a．问集合S中最多能有多少个元素？

（1972年英国数学竞赛）

6．证明：

⑴如果竞赛图中各点的出次不等，那么可将这些点排成一列，排在前面的点有弧到达排在后面的任一点（即排在前面的选手胜排在后面的所有选手）．

⑵如果点数n≥3的竞赛图中有三角形回路，那么，图中必有两点的出次相等．

C类例题

例7某足球赛有16个城市参加，每市派出2个队，根据比赛规则，每两队之间至多赛一场，同城两队之间不进行比赛．赛过一段时间后，发现除A城甲队外，其他各队已赛过的场数各不相同．问A城乙队已赛过几场?

证明你的结论．

分析注意分析“各队赛过场次各不相同”的含义，即能推知比赛场次的取值情况．再从比赛场次最多的队开始讨论，与之比赛的队是哪些队？

证明用32个点表示这32个队，如果某两队比赛了一场，则在表示这两个队的点间连一条线．否则就不连线．

由于，这些队比赛场次最多30场，最少0场，共有31种情况，现除A城甲队外还有31个队，这31个队比赛场次互不相同，故这31个队比赛的场次恰好从0到30都有．就在表示每个队的点旁注上这队的比赛场次．

考虑比赛场次为30的队，这个队除自己与同城的队外，与不同城的队都进行了比赛，于是，它只可能与比赛0场的队同城；

再考虑比赛29场的队，这个队除与同城队及比赛0场、1场（只赛1场的队已经与比赛30场的队赛过1场，故不再与其它队比赛）的队不比赛外，与其余各队都比赛，故它与比赛1场的队同城；

依次类推，知比赛k场的队与比赛30－k场的队同城，这样，把各城都配对后，只有比赛15场的队没有与其余的队同城，故比赛15场的队就是A城乙队．即A城乙队比赛了15场．

说明有些题的已知条件讨论起来头绪纷繁，如果利用图来讨论则可以化繁为简．利用点与线的相邻与否来研究这一类题目需要一定的技巧，也需要相当的抽象概括能力与逻辑推理能力．请大家多做些练习．

例8n（n＞3）名乒乓球选手单打若干场后，任意两个选手已赛过的对手恰好都不完全相同，试证明：

总可以从中去掉一名选手，而使在余下的选手中，任意两个选手已赛过的对手仍然都不完全相同．（1987年全国高中数学联赛）

分析本题的求证暗示要用反证法，设去掉任一个选手，都会有两个选手赛过的对手完全相同．于是这两人组成一个点对．这样就会得到n个点对．每个点对连一条线，n个点连出了n条线，就可用图的性质得到圈，使问题得证．这是证法1的思路．

每个选手的对手可以组成集合，研究对手集的性质，用最小数原理来证明，这是证法2的思路．

证法1把这些选手编为1至n号，以n个点表示这n个人，各点也相应编为1至n号．

反设去掉任何一个选手后，都有两个选手的已赛过的对手完全相同．于是，如果先去掉1号选手，则有两个选手的已赛过的对手完全相同，设为第i号与第j号，在表示此二人的点间连一条线，并在线上注上“1号”．这说明，此二人在去掉1号选手之前必是一人与1号赛过，另一人与1号没有赛过．而且不可能在去掉1号后有三人都相同，否则，此三人与1号选手比赛的情况只有两种：

赛过或没有赛过，如果去掉1号后，此三人的情况完全相同，则去掉1号之前必有2人赛过的对手完全相同．（如果去掉1号后有不止一对选手的已赛过对手完全相同，则只任取其中的一对连线，其余的对则不连线．）

同样，如果再依次去掉2号、3号，…，直至n号，每去掉1个选手，都会在某两点之间连1条线．这样，就在n个点间连了n条线．且这些线上分别注了1至n号，每条线注了1个号码，每个号码只注在1条线上．

由于在10个点间连了10条线，故图中必存在一圈．

现从圈上一点i出发，经过点j、k、…最后回到点i．注意到点i与点j所代表的两个选手中1个是与1号比赛的，另一个是没有与1号比赛的，不妨设i号没有与1号比赛过，j号与1号比赛过．而j与k所连线上注的号码不是1，故j与k与1号比赛的情况相同，即k号与1号比赛过，…，这样沿线走一圈后回到i，就应该得出i号与1号比赛过，矛盾．故证．

证明2用A、B、…表示选手，而用α（A）、α（B）表示A、B已赛过的对手集合．显然，若A∈α（B），则B∈α（A）．

设A是对手集中元素最多的的选手．

若命题不成立，则存在两个选手B、C使去掉A后，B、C的对手集相同，由于α（B）≠α（C），故A必属于α（B）与α（C）之一．不妨设A∈α（B），于是，B∈α（A），CÏ

α（A）且α（C）＝α（B）\{A}．（在α（B）中去掉它的一个元素A后的集合表示为α（B）\{A}）

同样对于选手C后，存在D、E，使去掉C后，D、E的对手集相同，即去掉C后，α（D）＝α（E），又设C∈α（D）且CÏ

α（E），于是D∈α（C），EÏ

α（C）．

由于AÏ

α（C），D∈α（C），故D≠A：

又D∈α（C），故D∈α（B），即B∈α（D）＝α（E）∪{C}，从而B∈α（E），CÏ

α（E），而去掉A后，B、C的对手集相同，从而E＝A．

于是α（A）＝α（E）＝α（D）\{C}，即α（A）比α（D）少一个元素C，这与A是“对手集中元素最多的”矛盾．故证．

说明证法1是根据如下结论：

如果n个点间连了n条线，则必出现“圈”：

即从某一点出发，沿边前进，最后还能回到出发点．

证法2用最小数原理对集合的元素进行讨论，较难理解，可对照图理解相应的结论．

链接树与圈

若在一个图G=（V；

E）中取n+1个顶点v1、v2、…、vn+1，每两个相邻的顶点vi、vi+1间连有一条边li,则边l1,l2,…,ln就称为从v1到vn+1的一条链．一个图中的任意两个顶点间如果都有一条链，该图就是连通的．一条链的两个端点v1与vn+1重合时，就称为圈．没有圈的连通图称为树．n阶树可以记为Tn．在一个图中，次数为1的顶点称为悬挂点．

定理1如果树T的顶点数≥2，那么，它至少有两个悬挂点．

从树的任何一个顶点出发，沿某个方向前进，已走过的边不重复走，由于树是无圈的，故每个顶点至多走过1次，如果，经过的一个顶点不是悬挂点，则还可以前进到下一个顶点，由于树的顶点只有有限个，故前进到某个顶点（如果图中共有n个顶点，则至多前进n－1步）后就无法再继续前进，即到达一个次数为1的顶点．此顶点即为一个悬挂点．再从此悬挂点出发，沿链走一次（第一步是按刚才的反方向前进），则又可以到达一个悬挂点．此悬挂点与刚才第一个悬挂点不同．即图中至少有两个悬挂点．

定理2一个n阶的连通图是1个树，当且仅当它有n－1条边．

先证明：

如果树T的顶点数为n，则其边数为n－1．

证明对于n＝1或2，定理显然成立．

设定理对于k个顶点时成立，即若一个树有k个顶点，则其边有k－1条．对于k+1个顶点的树，只要去掉一个悬挂点及与之相邻的一条边，就成为有k个顶点的情形，此时的树有k个顶点与k－1条边，此时再把去掉的1个顶点及1条边添入，就成为k+1个顶点，k条边的树．故证．

再证明：

如果图G是连通的，且有n个顶点与n－1条边，则G是一个树．

取G的生成树T，则此生成树有n个顶点，因是树，故有n－1条边．但TG，故T＝G．故证．

定理3树T具有以下性质：

⑴在T中去掉任一边后，所得的图是不连通的；

⑵在T中添上1条边后，所得的图有圈；

⑶T中的任两个顶点v1与v2间有且仅有1条链．

证明⑴设树T有n个顶点与n－1条边，在T中去掉1条边后得到图G，如果G仍连通，则G仍是一个树（因无圈且连通）．应有n－1条边，矛盾．

⑵如添上1边后仍无圈，则仍为树，有n个顶点与n条边，矛盾．

⑶由T连通，故v1与v2间必有链，若v1与v2间有不完全相同的两条链，则此图中有圈，即不是树．矛盾，故v1与v2间有且仅有1条链．

7．某个团体有1982个人，其中任意4人都至少有一人认识其他三个人，认识其他所有人的人数最少是多少？

（1982年美国数学竞赛）

8．⑴在一所房子里有10个人，其中任意3人中至少有2人互相认识，证明：

其中有4人，他们任意2人都互相认识．（1980英国数学竞赛）

⑵如果把⑴中的数10改为9，结论仍成立否？

（1977年波兰数学竞赛）

习题13

1．如果每个点的出次都是2，那么，一个点经过两条弧就可以到达的点至多有几个？

经过一条弧或两条弧可以到达的点至多有几个？

2．在竞赛图中必有一个点，从它到其它的顶点，只需经过一条弧或两条弧．

3．一个有n个点的竞赛图，各点的出次为w1≥w2≥…≥wn．如果w1＝n－1，w2＝n－2，…，wk－1＝n－（k－1），但wk≠n－k（1≤k≤n）．证明：

wk＜n－k．

4．⑴如果在点数n≥3的竞赛图中，有两个点的出次相等．证明，图中必有三角形回路（即有三个选手A、B、C，其中A胜B，B胜C，C又胜A）．

⑵在一个n人参加的循环赛中，每两人比赛一场，如果没有平局，参赛者赢的场数分别是w1，w2，…，wn．求证：

出现三个参赛者A，B，C，满足A胜B，B胜C，C胜A的充分必要条件是

w

＜

5．亚洲区足球小组赛，每组有4个队，进行循环赛，每两个队赛一场，胜者得3分，负者得0分，平局各得1分，赛完后，得分最高的前两名出线．如果几个队得分相同，那么便抽签决定这些队的名次，问一个队至少要得多少分，才能保证一定出线？

6．条件同上题，问一个队如果出了线，它至少得了多少分？

7．在8×

8棋盘上填入1～64的所有整数，每格一数，每数只填一次，证明：

总可以找到两个相邻的方格（具有公共边的两个方格叫相邻），在此两个方格中填入的数的差不小于5？

8．平面上有n条直线，把平面分成若干个区域.证明:

用两色就足以使相邻的区域都涂上不同的颜色.

9．在某个国家，任意两个城市之间用下列交通工具之一进行联络：

汽车，火车和飞机．已知没有一个城市拥有这三种交通工具，并且不存在这样三个城市，其中任意两个在联络时都用同一种交通工具．而且这个国家用了这三种工具．这个国家最多有多少个城市？

（1981年保加利亚，美国数学竞赛）

10．一个大三角形的三个顶点分别涂红、黑、兰三色，在三角形内部取若干点也任意涂红、黑、兰三色之一，这些点间连有一些线段，把大三角形分成若干互相没有重叠部分的一些小三角形.求证:

不论怎样涂，都有一个小三角形，其三个顶点涂的颜色全不同.

11．证明：

在2色K6中一定存在两个同色三角形（即同色K3）．

12．某个国家有21个城市，由若干个航空公司担负着这些城市之间的空运任务．每家公司都在5个城市之间设有直达航线（无需着陆，且两城市间允许有几家航空公司的航线），而每两个城市之间都至少有一条直达航线．问至少应有多少家航空公司？

（1988年前苏联数学竞赛）

本节“情景再现”解答：

1．解如图的5个点即不存在同色三角形，故例2中把6个人改为5个人后，结论可能不再成立．

2．证明计算每个顶点引出的边的条数（次数），如果每个顶点的次数都≤2，则统计得到的边数≤2n，但每条边都被统计过2次，故应统计得到边数=2（n+1）．矛盾．故至少有一个顶点，其次数≥3．

3．解⑴点A：

出次3，入次1；

点B：

出次1，入次1；

点C：

出次0，入次2；

点D：

出次1，入次1．

⑵出次的和=3+1+0+1=5；

入次的和=1+1+2+1=5．

出次的和=入次的和．

⑶证明由于每条弧起点所是出次的点，终点都是入次的点，故出次和与入次和相等，都等于弧的条数．

4．解不一定，例如右面的一个图中，就没有两个点的出次相同．A、B、C、D四点的出次依次为3，2，1，0．

一般的n个点的竞赛图中，可以出现n个点的出次分别为n－1，n－2，n－3，…，2，1，0这n个值，于是不一定有两个点的出次相同．

5．解S中有3个元素是可以的，a→b→c→a．满足要求．

若S至少有4个元素，取其中4点，由⑴，S中每两点间都要连出1条有向线段，4点间连出6条有向线段．每条有向线段都记一个出次，共有6个出次．因此至少有一个点至少有2个出次．设a→b，a→c，则无论b→c或是c→b均引出矛盾．即S的元素个数≤3．故S最多有3个元素．

6．证明⑴设共有n个点，由于各点出次互不相等，故这n个点的出次取得0，1，2，…，n－1这n－1个值中的每个值．

把出次为0的点排在最后，其余各点均到达此点．出次为1的点必到达此点，由于出次为1