图论问题选讲答案

-1-图论问题讲义答案例1．空间6点，无3点共线，每两点连1条线，染红或蓝．⑴求证：必存在1个以其中三点为顶点的三角形．三边同色；⑵求证：必存在2个以其中三点为顶点的三角形．三边同色．证明：只证第⑵题：设这6个点各连出了di(i＝0，1，2，…，5)条红线及5－di条蓝线，则它们组成了di(5－di)个异色角．di(5－di)＝0，4，6．即di(5－di)≤6．从而图中的异色角≤6×6＝36个．由于一个三角形，若为同色三角形，则异色角数＝0，若不是同色三角形，则异色角数＝2．于是异色三角形数≤362＝18．由于共有C26＝20个三角形．故至少有2个同色三角形．⑶空间5点，无3点共线，每两点连1条线，染红或蓝，是否一定存在1个以其中三点为顶点的三角形．三边同色？解：不一定，如图，五边形ABCDE中，染了5条红边5条蓝边，其中没有同色三角形．⑷把数1，2，3，4，5任意分成两组，试证明：在这两组数中，总有一组数中存在两个数，它们的差(的绝对值)也在这一组中．解：任取6个点，分别标上1，2，3，4，5，6．每两点连一条线，并在这条线上注上这两点差的绝对值．就得到一个K4，且每条线上所注数字只能是1，2，3，4，5．若数1，2，3，4，5已分成了A、B两组，某条线上的数分入了A组，则把这条线染红，分入了B组，则相应的线染蓝，由于K6的线二染色，必出现同色三角形，即该同色三角形上的三个数分入了同一组，设这个同色三角形的三个顶点的数为a、b、c(a＞b＞c)，则三条线上的数为a－b，b－c，a－c．于是a－b，b－c，a－c分入同一组，即这三个数满足题目要求．例2．6人相互认识或相互不认识，只有当其中4人围坐一圈，相邻2人都互相认识或都互相不认识时，这4人才能坐在一起打牌，问能否找到4人，这4人能够在一起打牌．解用6个点表示这6个人，如果其中某两个人互相认识，则在表示这两个人的点之间连一条红线，否则即连一条蓝线．每点连出5条线，其中必有一种颜色线≥3条，即或红线≥3条或蓝线≥3条．把连出红线≥3条的点称为A类点，连出蓝线≥3条的点称为B类点，则A类点或B类点中必有一类的点数≥3，不妨设A类点数≥3，且v1，v2，v3为A类点，⑴设v1，v2间连蓝线：由于v1，v2都连出了至少3条红线，故其余4点中都分别有3点与此2点连了红线，于是其余4点中必有2点与v1，v2都连红线，不妨设v3，v4与v1，v2都连了红线，则v1，v3，v2，v4四点连出同色四边形．(图1)⑵设v1，v2，v3之间都连红线．由于v1，v2，v3的每一个都至少连出了3条红线，故它们每一个都要与v4，v5，v6中的至少一个连红线．①若v4，v5，v6中有某一点与此三点中的某两点都连红线，例如v4与v1，v2都连红线，则v1，v3，v2，v4这4点连出同色四边形．(图2)②若v4，v5，v6中的每个点都只与v1，v2，v3这三点中的某一点连红线，如图3，则在其余的线中只要有任一条线连红线，就有红色四边形出现．③若v4，v5，v6中的每一点与v1，v2，v3这三点中的某一点连红线，而所有其余的线都是蓝线，则出现蓝色四边形．(图4)例3．给定空间中的9个点，任意4点不共面，每两点间连一线段．求最小的n值，使当对其中任意n条线段用红、蓝两色之一任意染色时，都一定出现一个三边同色的三角形．图4v1v2v3v4v5v6图3v1v2v3v4v5v6图2v1v2v3v4v5v6v6v5v4v3v2v1图1ADCBE-2-解：设染色的线段至少有33条，则因9个点之间两两连线有C29＝36条，故不染色的线段至多有3条．设点A引出不染色的线段，则去掉点A及所引出的线段．在剩下的点及线段中，若还有点B引出不染色的线段，同样地再将B及引出的线段去掉，依次进行．因不染色的线段至多3条，所以至多去掉3个顶点，则还剩下6个顶点，其两两连线都染上了红色或蓝色．即得到k6（6阶完全图）图的2-染色．熟知，存在同色三角形．其次，存在一个9顶点32条边的图，把图的边2－染色，可使图中无同色三角形．如图所示，将9个点分成5组A＝{V1，V2}、B＝{V3，V4}、C＝{V5，V6}、D＝{V7，V8}、E＝{V9}，两组间连一条红线表示从这两组中任取一点都连有红线；两组间连一条蓝线表示从这两组中任取一点都连有蓝线；每一组内部的点之间不连线．该图构成有9个顶点，有C29－4＝32条边，且不存在2－染色的同色三角形．从而，欲求的最小n值为33．例4．在88棋盘的方格中分别填写1，2，…，82，每格一个数．证明：必有两个相邻方格(有公共边的方格)，方格中的两个数的差至少为5．⑴证：取每个方格的中心，凡是相邻的两个方格，就把相应的中心连一条线．这样得到了一个图G(图中红线组成的图即为图G)．图G的的直径=14，，故图G中任意两点的距离≤14．若相邻两个方格中填的数相差＜5，则差≤4，于是图G中所填两个数的差≤14×4＝56．但图中填了1与64，此二数必有一条链相连，此链的长≤14．即其差≤56，与64－1＝63矛盾．例5．⑴证明：有n个顶点且不含三角形的图G的最大边数为n24．证明：设v1是G中具有最大度数的顶点，d(v1)＝d．又设与v1相邻的d个顶点为vn，vn－1，…，vn－d＋1．由于G不含三角形，所以vn，vn－1，…，vn－d＋1均互不相邻．故G的边数e≤(n－d)d≤n24．由于G的边数为整数，故e≤n24．当n＝2m时，取二部图G＝Km，m．当n＝2m＋1时，取二部图G＝Km＋1，m．即满足e＝n24．⑵设Z为空间含有n(n≥4)个点的点集，其中任意四点不共面，这些点之间连有n24＋1条线段．证明：这些线段必可构成两个有公共边的三角形．(当n为偶数时的情况即是1987年国家集训队选拔考试题)证明：n＝4时，Z中共有4个点，共连有5条线段，由于4点间共可连6条线段，共组成4个三角形．每条线段与不在其上的两点各可组成一个三角形，故去掉任一条线段，则减少2个三角形．即4点连5条线段必连出两个有公共边的三角形．n＝5时，Z中5个点连524＋1＝7条线段，必有一点连线段数不超过2条(如果每点连线段数≥3，则统计每点的连线数的和≥35＝15条，由于每条被统计了2次，应是27＝14条)．去掉连线数不超过2条的点及其所连线段，则至多去掉2条线段，余下4点至少连了5条线段，如上证，必有两个有公共边的三角形．设n＝k(k≥4)时，命题成立．当n＝k＋1时，由于统计各点连出(2)(1)图4v1v2v3v4v1v2v3v2kADCBE123456789-3-线段数的和＝2(k＋1)24＋2．则连线数最少的点A，则点A的连线数≤1k＋12(k＋1)24＋2．当k＝2t时，(k＋1)24＝t(t＋1)．1k＋12(k＋1)24＋2＝12t＋1(2t2＋2t＋2)＝t＋t＋12t＋1．即该点连线段数≤t．此时，去掉点A及所连之线段，则余下k个点，且余下线段数≥t2+1＝k24+1．当k＝2t－1时，(k＋1)24＝t2．1k＋12(k＋1)24＋2＝12t(2t2＋2)＝t＋1t．即该点连线段数≤t．此时，去掉点A及所连之线段，则余下k个点，且余下线段数≥t2－t＋1＝(2t－1)24＋1＝k24＋1．于是，由归纳假设可知，余下点及线段中，必有两个有公共边的三角形．综上可知，命题成立．例6．S为m个无序正整数对(a，b)(即(a，b)与(b，a)是相同的)(1≤a，b≤n，a≠b)组成的集合．证明：至少有4m3n(m－n24)个三元数组(a，b，c)，适合：(a，b)，(b，c)，(c，a)都属于S．证明：作一个图G＝(V，E)，以点vi表示数i(i＝1，2，…，n)，当且仅当(i，j)∈S时，在点vi与vj间连1条线段．于是图G有n个顶点，m条边．问题转化为：图G中至少有4m3n(m－n24)个三角形．令顶点vi的度为di，取G的任一条边vivj，则vi与vj共向其余的顶点引出d1＋d2－2条边．从而共有di＋dj－n对分别由vi与vj引向同一顶点的线段，与vivj组成三角形．因此G中至少有di＋dj－n个以vivj为一边的三角形．但这个三角形在G三边上被计数了3次．从而G中三角形数k满足k≥13Σvivj∈E(di＋dj－n)．注意到di在上述和式中出现了di次，而G中共有m条边，故k≥13(Σi＝1ndi2－mn)．由于Σi＝1ndi＝2m，故nΣi＝1ndi2≥(Σi＝1ndi)2＝4m2Σvivj∈Edi2≥4m2n．∴k≥13(4m2n－mn)＝4m3n(m－n24)．例7．十个学生参加一次考试，试题共有十道，已知没有两个学生做对的题目完全相同，证明：这十道题中可以找到一道题，把这道题取消后，每两个学生所做对的题目仍不会全同．(假定每个题，都只有做对与做错这两种情况，没有部分对的情况发生)证明反设取消任何一题后，都有两个学生做对的题目完全相同．首先，取消某一题后，全同的人不会多于2人，否则，由于每道题的结果都只有全对或全错两种情况，在取消某题前，这题必有至少两人答的情况相同，于是，取消这题前，就有两人答对的情况全同．用10个点表示这10个学生，如果取消某题后有某两人的对错情况全同，则在表示这两人的两个点间连一条线，并在线旁注上该题的题号(如果有几对人全同，则只任取其中一对连线注题号)．这样，在10个点间就连了10条线，于是必出现圈．现取出现的一个圈，从该圈的任一顶点出发，沿圈走一圈回到起点，由于每经过一条边，到新一个顶点时，都与原顶点有一个题目的差异，且经过不同的边，对错的题目不同．这样回到原起点时，对错的情况不可能还原，这就引出矛盾．(例如v1与v2间连线上注的题号为1，则若v1第一题正确，则v2第一题错误，后面的边上都没有注题号1，故以后每个vi的第1题对错情况都不变，即，第1题都错．到沿此圈前进一圈回到v1，应得v1的第一题错，与初始状态的假定“第1题正确”矛盾．例8．n名儿童希望把m块形状为矩形的相同的巧克力分成重量相等的n份(n，m∈N*)．规定每块巧克力至多被分成两块．对怎样的n与m，上述要求能实现？解：如果m≥n，则每人分得的巧克力不少于1块，这总是可以按上述要求分成的．m＝n时，每人1块巧克力，不要分开，当m＞n时，设每块巧克力的长度为l，把这m块巧克力长边相连排成一排，其总长度为ml，再按长度分成n等分，每份长为mln，每名儿童取1份，由于mn＞1，故每块巧克力至多分成了两-4-块，满足题意．当m＜n时，mn＜1，于是每块巧克力都要被切开．如果mn＜12，显然不能按要求能分成；当mn＝12时，只要把每块巧克力二等分即可得到满足要求的分法；当12＜mn＜1时．用n个点表示这n名儿童，若某两人各取了同一块巧克力的两部分，就在表示相应的人的点间连一条线．这就得到了一个图．若此图有k个连通分支．每个分支分别有m1、m2、…、mk条边与n1、n2、…、nk个顶点，由于每个儿童分得的巧克力相等，故m1n1＝m2n2＝…＝mknk＝mn．因每个连通分支是顶点数多于边数的连通图，所以必有mi＝ni－1(i＝1，2，…，k)．于是，n1＝n2＝…＝nk＝nk，m1＝m2＝…＝mk＝mk，因此，可以分的一个必要条件是：存在m、n的一个公约数k，使mk＝nk－1，即m＝n－k．这个条件也是充分的．首先，当k＝1时，因为每个儿童分得一块巧克力的n－1n，可以把每块巧克力切成n－1n与1n的两块，前m－1名儿童每个人取n－1n，最后一名儿童取n－1个1n即可．对于k＞1，可以把每块巧克力切成n－kn与kn的两块，前m－k名儿童每个人取n－kn，后k名儿童取mk个kn，此时后k名儿童取mk×kn＝mn＝n－kn．于是每人分得的巧克力数相等．例9．亚瑟王(传说中的英国国王)在王宫中召见他的2n名骑士，其中某些骑士之间互相有仇，已知每个骑士的仇人不超过n－1个，证明：摩尔林(亚