图论

高中数学竞赛讲座二试内容251图论问题一．基本概念1．图的定义：由若干个不同的顶点与连接其中某些顶点的边所组成的图形叫做图。用G表示图，用V表示所有顶点的集合，E表示所有边的集合，并且记作G=（V，E）．2．同构图：如果两个图G与G‘的顶点之间可以建立起一一对应，并且当且仅当G的顶点vi与vj之间有k条边相连时，G’的相应顶点jivv与之间也有k条边相连，就认为G与G是相同的，称G与G是同构的图．2．子图：如果对图GEE,VV)E,V(G)E,V(G，则称有与是G的子图．3．其它有关概念：（1）若在一个图G中的两个顶点jivv与之间有边e相连，则称点jivv与是相邻的，否则就称jivv与是不相邻的．（2）如果顶点v是边e的一个端点，称点v与边e是相邻的．（3）如果顶点本身也有边相连，这样的边称为环．如果连接两个顶点的边可能不止一条，若两个顶点之间有k)2k(条边相连，则称这些边为平行边．（4）如果一个图没有环，并且没有平行边，这样的图称为简单图．竞赛中的图论问题涉及到的图一般都是简单图．（5）如果一个简单图中，每两个顶点之间都有一条边，这样的图称为完全图，通常将有n个顶点的完全图记为nK．（6）在图G=(V,E)中，顶点个数|V|和边数|E|都是有限的，则称图G是有限图；如果|V|或|E|是无限的，则称G为无限图．1v2v4v3v1v2v3v4v1v2v3v4v1G2G3G高中数学竞赛讲座二试内容252二．例题精选1．设S为平面上的一个有限点集（含点数不少于5），若其中若干个点涂红色，其余点涂上兰色，又设任何三个同色点不共线，求证：存在一个同色三角形，且它至少有一条边不含另一种颜色．证明：无穷递降法2．若平面上有997个点，如果两点连成一条线段，且中点涂成红色，证明：平面上至少有1991个红点，试找到正好是1991个红点的特例．证明：设997个点中M、N之间的距离最大，以M、N为圆心，2MN为半径作圆，如图，设P为其它995个点中的任意一个点，则PM、PN的中点R、Q都在圆M、N内，且这些点个不相同，所以至少有995×2+1=1991个点．特例：在x轴上横坐标依次为1，2，3，．．．，997的997个点，满足题设条件．3．正六边形被分为24个全等的三角形，在图中的19个结点处写上不同的数，证明：在24个三角形中，至少有7个三角形，其顶点处的三个数是按逆时针方向递增顺序书写的．证明：（１）正六边形的12条边中至少有一条逆边；（2）一个逆三角形有2条逆边，一个顺三角形有1条逆边；（3）除掉正六边形的边，图中有（24×3-12）÷2=30条边，没条边恰好是一个三角形的一条逆向边．综上，设24个三角形中有m个逆三角形，n个顺三角形，则有731224mnmnm，得证．RRRBBBMNPRQE逆三角形顺三角形123123高中数学竞赛讲座二试内容2534．在正n边形中，要求其每条边及每条对角线都染上任一种颜色，使得这些线段中任意两条有公共点的染不同颜色，为此，至少需要多少种颜色？证明：先考虑一个顶点Ａ出发的n－１条线段，如图，需要n种颜色．当n=3时，三种颜色即可．当n3时，作正n边形的外接圆，设MN是另外一条边或对角线，若MN//BC，则将MN染成与BC同色；若BCMN//，过A引直线直线m//MN，交圆于K，则弧KN=弧AM，所以K也是正n边形的顶点，即AK是由A出发的边或对角线，将MN染成与AK同色，所以n种颜色足够了．5．某次大型活动有2003人参加，已知他们每个人都至少和其中的一个人握过手，证明：必有一个人至少和其中的两个人握过手．证明：从5个点开始考虑奇数个点即可．如图6．现有九个人，已知任意三人中总有两个人互相认识，证明：必有四人互相之间都认识．证明：9个顶点的简单图，利用抽屉原理7．有n名选手n21A,,A,A参加数学竞赛，其中有些选手是互相认识的，而且任何两个不相识的选手都恰好有两个共同的熟人，若已知选手21AA与是互相认识，但他们没有共同的熟人，证明他们的熟人一样多．MNEPQR1A2A3A4A5AABCKMNA1A2A)(2An)(1AniAjA1A2A)(2An)(1AniAjAjAiA高中数学竞赛讲座二试内容254证明：的熟人一一对应与21AA8．有n（n3）个人，他们之间有些人互相认识，有些人互相不认识，而且至少有一个人没有与其他人都认识，问与其他人都认识的人数的最大值是多少？解：作图G：用n个点表示这n个人，当两人认识，则在两相应顶点之间连一线，否则之间不连线．由于至少有一个人与其他人不认识，所以图G中至少有两点之间没连线，设21AA与之间没连线，则图G的边数最多时，G为21AAKn，故最大值为n-2．9．次会议有n名教授n21A,A,A参加，证明可以将这n个人分为两组，使得每一个人Ai在另一组中认识的人数不少于他在同一组中认识的人数．证明：用n个点nAAA,,,21表示这n名教授，并在相互认识的人之间连一条边，且将同一组间的连线染成红色，不同组之间的线染成蓝色．将这n个点任意分成两组，只有有限种分法．考虑在两组之间的蓝线条数S，其中必存在一种分法，使S达到最大值，此时有iA在两组内引出的边的条数分别为),,2,1,(,nilllliiii，否则，若对iA有iill，将iA调到另一组，S增加了iill条，矛盾，得证．10．有三所中学，每所有学生n名，每名学生都认识其他两所中学的n+1名学生，证明：从每所中学可以选出一名学生，使选出来的3名学生互相认识．证：用3n个顶点表示这些学生，三所中学的学生组成的三个顶点集合分别记为A、B、C，设M和N是两所不同学校的学生，而且是互相认识的，则在M与N之间连一线，得一个简单图．记A中的元素x在B、C中的相邻元素个数为k和l，则k+l=n+1．设k与l中大的记作m(x)，让x跑遍A，m(x)的最大值记作Am，同理记CBmm,分别为集合B、C中的所有元素在另两个集合中相邻元素个数的最大值．记m是Am，CBmm,中最大者，不妨设m=Am，且的顶点相邻的顶点集和中和使得100,BxBAx数为m，于是C中与高中数学竞赛讲座二试内容255000,11xCzmnx与设相邻的顶点数为相邻．如果有中中的一个三角形．若是相邻，则与1000010BGzyxzBy每一个y与中相邻与．因此，相邻的顶点数与都不相邻，则AzmnzBz000的顶点数1)(1mmnn与m的最大性矛盾，得证．三．巩固练习1．有n个药箱，每个药箱里有一种相同的药，每种药恰好在两个药箱里出现，问有多少种药？)1(21nn2．18个队进行比赛，每一轮中每一个队与另一个队比赛一场，并且在其他轮比赛中这两个已赛过的队彼此不再比赛，现在比赛已进行完8轮，证明一定有三个队在前8轮比赛中，彼此之间尚未比赛过．3．某次会议有n名代表出席，已知任意的四名代表中都有一个人与其余的三个人握过手，证明任意的四名代表中必有一个人与其余的n-1名代表都握过手．4．空间１８个点，任三点不共线，它们的两两连线染上红色或兰色，每条线段仅染一色．试证明其中一定存在一个同色的完全四边形．图论问题（二）用图论解决问题躲基本思路：把要考察的对象作为顶点，把对象之间是否具有我们所关注的某种关系作为顶点连边地条件．这样，就可以把一个具体问题化归成图论问题，用图论的理论和方法进行探讨，即使在图论中没有现成定理直接给出问题的解答，也可以（1）借助图论的分析方法拓宽解题思路；（2）把抽象的问题化为直观问题；（3）把复杂的逻辑关系问题化为简明的数量分析问题。在具体讨论过程中，还要注意一般数学方法，如：反证法、数学归纳法、抽屉原理、染色法等。一．概念高中数学竞赛讲座二试内容256设G是n阶图，它的顶点集合为},,,{21nvvvV，（1）与顶点之间的连线的条数叫做边数，记作E；（2）顶点),3,2,1(ivi相关联的边的条数叫做顶点iv的度，记作)(ivd；（3）定理：n阶图G中所有顶点的度之和是它的边数的两倍，即有Evdnii2)(1推论：任何图G的奇顶点个数必为偶数。二．精选例题1．（1）一次乒乓球友谊比赛有14人参加，随后统计出各人比赛的场数为：3，3，3，3，3，4，6，6，6，6，6，6，6，6．证明：其中必有错误．关键：两人之间比过连一线，则总次数＝2×边数，矛盾。（2）有20名乒乓球运动员进行14场单打比赛，每人至少参加一场比赛，证明：必有6场比赛，其中12个参赛者互不相同．关键：将20名运动员用顶点2021,,,vvv表示，若两名运动员比赛过，则在相应顶点之间连一条边，得一个图G．则28142)(201iivd，在每个顶点iv处抹去1id条边，由于一条边可能同时被两端点处抹去，所以抹去的边数不超过：82028)1)((200iivd，所以抹去了这些边后，图中至少还有6条边，并且每个顶点的度至多是1，从而这6条边的12个顶点互不相同。2．一个俱乐部中有3n+1个人，每两个人可以玩网球、象棋或乒乓球．如果每个人都有n个人与他打网球，n个人与他下棋，n个人与他打乒乓球，证明：俱乐部中有3个人，他们之间玩的游戏是三种俱全．关键：分别在三种活动之间连三色线，得313nC个三角形，图中有23)13(nn个异色角，而313223)13(nCnn，得证。3．四个城市进行足球比赛，规定每个城市派出红、黄两个。规定每两个队之间之都赛一场，并且同一个城市的两个队不比赛。比赛进行若干天后进行统计，发现除A市红队以外，其余各队赛过的场数各不相同，问A市黄队已比赛过多少场？关键：1A0AA6A5A4A3A2A高中数学竞赛讲座二试内容2574．18个队进行比赛，在每一轮比赛中，每个队与另一个比赛一场，并且在以后的各轮中这两个队不再比赛，现在比赛进入第9轮，证明：在前8轮比赛中，一定有三个队，彼此之间尚未赛过．关键：5．如果认识是互相的，证明在任何一群中，至少有两个人在这群人中认识人数相同。关键：不共存与且10,1,,2,1,0)(nnAdi。6．某俱乐部共有99名成员，每一个成员都声称只愿意和自己认识的人一起打桥牌，已知每个成员都至少认识67名成员，证明：一定有4名成员，他们可以在一起打桥牌。关键：99个点的图G：67)(iAd，要证G中存在一个4K。0A1A2A3A4A5A6A7A9A8A10A情形二0A1A2A8A9A10A情形一BA313135高中数学竞赛讲座二试内容2587．设在平面上给定n个点，求证：其中距离为1的点对数不超过23224nn．关键：把n个点看作图G的顶点，记},,,{21nvvvV为G的顶点集，在距离为1的两点之间连一条边，则Evdnii2)(1。用为表示以iivC圆心，半径为1的圆，这n个圆中两两交点的总数不超过)1(22nnCn个。另一方面，若ijkvvv与,相邻，则2)(21,,,,ivdnijkiCCCCvCCv数中两圆的交点恰好被计作为因此，次，故得)1(2212)(nnCCnnivdi，而.2242)1(2)(21)(21232211212)(nnEEEnnnEEnvdvdCniiniinivdi解得：8．由n个点和这些点之间的l条连线段组成一个空间图形，其中12qqn，Nqqqql,2,1)1(212，已知此图中任四点不共面，每点至少有一条连线段，存在一点至少有q+2条连线段。证明：图中必存在一个空间四边形（即由A,B,C,D和AB、BC、CD、DA组成的图形）。证明：设这n个点滴集合为iinBAAAAV的所有邻点的集合为记},,,,{110，边形。条线段，则图中存在四中至少有一个点发出则之间的连线条数为：则条线段为：发出时，不妨设若存在，显然中点的个数为2,,,11)1)(1(21)(1)1(21