nbhkdz.com冰点文库

2012江苏省数学竞赛《提优教程》教案:第67讲


第 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 条线.题
2 3

目的条件即是:任三点间至少连 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), 证明 w1+w2+?+wn=e1+e2+?+en. 分析 根据竞赛图的特点可知:⑴ 每点的出次与入次的和都等于 n-1,⑵ 所有点的出次 1 的和与入次的和相等.由此可以推出:所有点的出次和与入次和都等于 n(n-1).这是两个基 2 本的性质.在要证的式子中把 ek 用 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) 1 2 2 2 =w1+w2+?+wn+n(n-1)2-2?2(n-1)(n-1) = w1+w2+?+wn. 说明 本题的证明方法与《奇偶分析》中的例 6 相似. 例 4 平面上给定 7 个点,用一些线段连接它们,每三个点中至少有两点相连,问至少要 有多少条线段?试给出一个图.(1989 蒙古数学竞赛) 分析 首先找到连线条数的下界(即至少要连出多少条线),再寻找是否可能达到这个下界,
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

可以分别枚举可能的连线方法,讨论每种方法的连线条数,得到最小的结果. 解 7 个点中共有三点组 C7=35 个.每条线段共与其余 5 点组成 5 个三角形.故线段条数 35 ≥ 5 =7 条.
A

3

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

线, 要 C6=15 条. 连 线 数 > C 5 = 10
2

2

如果有一点只连了一条线, 其余 5 点必须两两连线,

条. 设某点只连了 2 条线,如点 A 只连了 AB、AC 这 2 条线,则其余 4 点均未与 A 连线,于 是它们必须两两互连,应连 C4==6 条.此时,取 B、C 两点及其余 4 点中的任一点,尚不满 足条件,故 BC 应连线,此时连了 9 条线,所得图形满足题目要求. 21 若每点都至少连出 3 条线,则总度数≥21,即至少连了[ ]+1=11 条线. 2 所以,至少连 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

连一条边,证法 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∪B?S.故 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.

情景再现
C 段)组成, 3. ⑴右面的有向图由 4 个顶点及一些弧(有向线 D 指出各点 的出次(引出的弧的条数)与入次(引入的弧的条数). ⑵求出上题中所有各点的出次的和与入次的和, B 它们与弧的条数有 A 什么关系? ⑶证明:任一有向图中,出次的和与入次的和相等. 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 城乙队已赛过几场?证明你的结论. 分析 注意分析“各队赛过场次各不相同”的含义,即能推知比赛场次的取值情况.再从 比赛场次最多的队开始讨论,与之比赛的队是 哪些队? A城 证明 用 32 个点表示这 32 个队,如果某 两队比赛了一场, 30 甲队 0 1 29 2 则在表示这两个队的点间连一条线.否则就不 28 连线. 3 由于,这些队比赛场次最多 30 场,最少 0 场,共有 31 种情 况,现除 A 城甲队外还有 31 个队,这 31 个队 比赛场次互不相 同,故这 31 个队比赛的场次恰好从 0 到 30 都 有.就在表示每个 队的点旁注上这队的比赛场次. 考虑比赛场次为 30 的队, 这个队除自己与 同城的队外,与不 14 16 15 同城的队都进行了比赛,于是,它只可能与比 赛 0 场的队同城; A城 再考虑比赛 29 场的队, 这个队除与同城队及比 赛 0 场、 1 场(只赛 乙队 1 场的队已经与比赛 30 场的队赛过 1 场, 故不 再与其它队比赛 ) 的队不比赛外,与其余各队都比赛,故它与比赛 1 场的队同城;依次类推,知比赛 k 场的队 与比赛 30-k 场的队同城, 这样, 把各城都配对后, 只有比赛 15 场的队没有与其余的队同城, 故比赛 15 场的队就是 A 城乙队.即 A 城乙队比赛了 15 场. 说明 有些题的已知条件讨论起来头绪纷繁,如果利用图来讨论则可以化繁为简.利用点 与线的相邻与否来研究这一类题目需要一定的技巧,也需要相当的抽象概括能力与逻辑推理 能力.请大家多做些练习. 例 8 n(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)表示 ? (B) ? (D) A、B 已赛过的对手集合.显然,若 A ∈ α(B) , 则 B ∈ A=E ? (C) C α(A). ? (E)=? (A) 设 A 是对手集中元素最多的的选 手. D B 若命题不成立,则存在两个选手 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 条边.但 T?G,故 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 的充分 必要条件是
2 2 2 (n-1)n(2n-1) w1+w2+?+wn< . 6

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.解 不一定,例如右面的一个图中,就没有两 个点的出次相 B A 同.A、B、C、D 四点的出次依次为 3,2,1,0. 一般的 n 个点的竞赛图中, 可以出现 n 个点的出 次分别为 n-1,n C D -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 的点只到达 1 个点,故出次为 1 的点只到达出次为 0 的点,把出次为 1 的点排在倒数第 二位;再考虑出次为 2 的点,由于此点只到达 2 个点,故它只到达已排的两个点而不能到达

其余的点,把出次为 2 的点排在倒数第 3 位;??,依此类推,把出次为 k 的点排在倒数第 k+1 位,直到出次为 n-1 的点排在第 1 位.这就得到满足题目要求的排法. ⑵ 反设图中所有各点的出次均互不相等,则由上题,可把这些点排成一列,使前面的点 到达后面的点.而后面的点不能到达前面的点,于是该图中没有回路,与已知此图有回路矛 盾.故必有两点出次相等. 7.解 先证明:任意 4 人中都有 1 人与其余 n-1 人认识. 用 n 个点表示这 n 个人,若两个 人认识,则在表示 V1 ' 这两个人的点间连一条实线, 否则连一 条虚线. V4' V2 ' V1 V 1 V V 设任取 4 人 v1、v2、v3、v4,其中 v1 与 v2、v3、v4 都认 2 3 V4 V2 识,但此四人中无人与 n - 1 人都认 识.即每个点都有 V3 V 与之不相邻的点.设与 v1、v2、v3、v4 不相邻的点分别为 1' V3 ' ?2 ? ? 1? v1?、v2?、v3?、v4?,显然 v1?≠v2,v2?≠v1, 若 v1?≠v2? ,则四点 图6 v1、 v2、 v1?、 v2?不满足题意. 于是 v1?=v2?, 同理 v1?=v3? ,于是 得 v1?=v2?=v3?,此时 v1、v2、v3、v1?这四点仍不满足已知条件.故证. 又证 设图 G 中度数小于 n-1 的点为 v1、v2、…、vk,记 F={v1、v2、…、vk},用实线表 示相邻(认识),用虚线表示不相邻. 若 k<4, 则命题正确(因为图中找不到 4 个人, 他们中任 1 人都没有与其余 n-1 人认识). 若 k≥4 , 由 于 vk+1、vk+2、…、vn V1 V1 V2 V V V 1 2 2 的度数都=n-1, 故与 v1 不相邻的点都 在 F 中,设为 v2,此 时若还能找到 v3、 V4 V4 V3 V4 V3 V3 ?2? ?3? ?1? v4∈F,且 v3 与 v4 不 相邻.则此四人 图7 不 满足题 目要 求 ( 图 7⑴). 若在 F 中除 v1、v2 外无不相邻的人,则 v3、…、vk 均至少与 v1、v2 中某一人不相邻.则如图⑵、⑶,亦与 已知矛盾.故 k≥4 不可能.故证. 再考虑本题: 把 1982 个人中的任意 4 人组成一组, 该组中必有 1 人认识其余所有的人. 去 掉这个人,在余下的人中再任取 4 人,又成一组,又可找出一个认识其余所有人的人;…, 这样一直做下去.直到余下 3 人为止,此 3 人可能与其余的人不全认识. 故至少有 1979 人认识其余所有的人. 8.解 ⑴用 10 个点表示这 10 个人,如果某 2 人互相认识,则在表示这两人的点间连 1 条线. 即任 3 点都至少连了 1 条线,要求证明存在一个 K4. 设不存在 K4, 即任意 4 点中总有 2 点没有连线, A6 ① 设某一点 A 与 4 点都没有连线,则由假设 此 4 点中有 2 A A5 点未连线,则此 2 点与 A 共 3 点均未连线,与题设 矛盾.故 A 至 多与 3 点未连线,即至少与 6 点连了线. A4 ② 设 A 与 A1、A2、?,A6 连线,则 A1,?, A6 中任意 3 点 A1 必有 2 点未连线,否则存在 K4, A3 ③ 设 A1 与 Bi、Bj、Bk 都未连线,则 Bi、Bj、 Bk 间若有两点 A2 未连线,则出现 3 点,都未连线,与已知矛盾.故 此三点间都连 了线,于是此三点与 A 成为 K4. ④ 由③知 A1,?,A6 中任一点至多与其余 5 点中的 2 点未连线.即与其余 5 点中至少 3 点连了线.设 A1 与 A2、A3、A4 连了线.此时 A2、A3、A4 间至少连了 1 条线,设 A2A3 连了 线,则 A、A1、A2、A3 成为 K4. 由上证可知,不存在 K4 的假设不成立.

⑵ 若有某点连出 6 条线,则如上证. 若每点连线数<6,当每点连线数都=5 时.此时 9 个点连线统计为 45,为奇数.不可能. 若有某点连线数<5,即该点至少与 4 点未连线,则如上①,矛盾.从而必有点连线数= 6 的点. “习题 67”解答: 1.解 一个点经过两条弧就能到达的点至多有 4 个.经过一条弧或两条弧就能到达的点至 A 多有 6 个.如图,每个点的出次都是 2,点 A 经过 1 条弧能到达 B、 C,点 B、C 分别经过 1 条弧可以到达 D、E、F、G, 故点 A 经过 1 条 C B 或 2 条弧可以到达至多 6 个点. 其中如果有些点重合, 则点 A 可以到达 的点就少于 6 个. G D E F 1 2.证明 取出次最多的点为 A,则 A 的出次≥ (n - 1) .他可以经 2 1 一条线到达的点为 B1,B2,?,Bm,m≥ (n-1).对于 A 不能到达的点 C,若 B1,B2,?, 2 Bm 中没有点到达 C,则不能到达 C 的点至少有 m+1 个,即 C 的出次比 A 多,与 A 为出次最 多的点矛盾.故所有 A 不能到达的点,都可经 2 条线到达.故证. 3.证明 k=1 时,若 w1≠n-1,则 w1<n-1. 设 w1=n-1,即 w1 到达所有其余的点.把出次为 w1 的点去掉,这对余下的点的出次都 不受影响.此时就得到一个只有 n-1 个点的竞赛图.若 w2≠n-2,则 w2<n-2. 设 w1=n-1,w2=n-2,同上两次去掉出次为 w1,w2 的点,则得到一个有 n-2 个点的 竞赛图.其中每个点的出次≤n-3.于是若 w3≠n-3,就有 w3<n-3. 依此类推,若各点的出次为 w1≥w2≥?≥wn.如果 w1=n-1,w2=n-2,?,wk-1=n -(k-1),但 wk≠n-k(1≤k≤n),则依次去掉 k-1 个点,而不影响余下点的出次,此时余下 点的出次≤n-(k-1)-1=n-k.若 wk≠n-k,则必有 wk<n-k.证毕. 4.⑴证明 设 A 与 B 出次相等,由于 A、B 必连有线,不妨设 A 胜 B,于是 A、B 的出 次不为 0.取所有负于 B 的点集 M,设此集中有 k 个点,其中 k 必大于 0.于是负于 A 的点 集中也有 k 个点,若 M 中没有点胜 A,则 M 中的点均负于 A,于是 A 胜 M 中所有点且胜 B, 即 A 的出次至少比 B 多 1,与 A、B 出次相等矛盾.故 M 中必有点 C,C 胜 A,于是 A 胜 B, B 胜 C,C 胜 A.证毕. 1 ⑵证明:不论何种比赛结果,所有参赛者出次的和都等于 1+2+?+(n-1)= n(n-1). 2 若每个参赛者的出次都互不相同,则出次分别为 0,1,2,?,n-1.此时不存在满足 “A 胜 B,B 胜 C,C 又胜 A”的三个参赛者. (n-1)n(2n-1) 2 2 2 此时 w1+w2+?+wn=02+12+?+(n-1)2= . 6 当有两个参赛者的出次相同时,就存在三角形回路.设出次为 wk 的点为 Ak. 设 w1≥w2≥?≥w1.且设 w1=n-1,?,wk-1=n-(k-1),但 wk≠n-k,则 wk<n- k,逐个把 A1,A2,?,Ak-1 去掉,这样做不会影响剩下点的出次.这样去掉点后,余下点中 必有引向 Ak 的线, 设从 Aj(j>k)有引向 Ak 的线, 把这条线的方向改变, 则 Ak 的出次变为 wk+1, 而 Aj 的出次变为 wj-1.此时(wk+1)2+(wj-1)2=wk+w j +2(wk-wj)+2>wk+w j ,即这样 操作可使和 w1+w2+?+wn增加,继续这样做,直到使 wk=n-k,这时去掉 wk,再做下去,
2 2 2 2 2 2 2

直到每个 wi 都等于 n-(i-1)(i=1,2,?,n)为止.此时和式 w1+w2+?+wn已严格递增至 (n-1)n(2n-1) 2 2 2 (n-1)n(2n-1) .这说明 w1+w2+?+wn< 成立. 6 6 5.解 共计比赛 6 场,最多共可得 18 分.若有三个队都是二胜一负得 6 分(如图中 A、B、 C 队),则不能保证一定出线(因要抽签才能决定是否出线). 若一个队得 7 分, 则保证一定出线, 因不可能有三个队至少得 7 分, 否则 7×3=21>18. 故 得分不少于 7 分的至多有 2 个队.故得到 7 分一定能出线. 6.解 若三个队都互相打成平局,都输给另一队(图中 B、C、D 三队),则此三个队都得 2 分,其中有一个队出线. B A 若某队只得 1 分,则该队 1 平 2 负,赢该 队的两个队都至少 得了 3 分, 于是名次都在该队之前, 该队不可能 出线. D 即某个队出线了,则该队至少得了 2 分. C 7. 解 把相邻的两格中心用一条边相连, 于 是就有一个 8 行, 每行 8 个点的图,从 8?8 棋盘的左上角一格到右下角一格需要经过 14 条边,如果所有相邻方 格中填入数的差小于 5,则由于连填“1”的格与填“64”的格之间的路至多经过 14 条边.于是这 两格中数的差不会超过 14?4=56.但 64-1=63.矛盾.故结论成立. 8.证明 当 n=1 时,1 条直线把平面分成两部分,用两色可以区分这两部分,如果增加 1 条直线,可以把这条直线某一旁的区域中原来涂的颜色变成另一种颜色.则所有相邻的区域 涂色都不同.以后每多画出 1 条线都把线一旁的部分的每个区域中颜色重涂成与原来不同的 颜色,就可使相邻区域涂色不同. 9.解 设共有 n 个城市,每两个城市之间连一条线,每条线染三种颜色之一.例如:汽 车用红色,火车用蓝色,飞机用黄色.已知没有任何一点引出 3 种颜色的线.且不存在同色 三角形. A E 首先证明:任一点不能连出 3 条同色线,否则, 设 AB、AC、AD 连红线, 则 B、 C、 D 间都不能连红线. 设 BC 连蓝线, 由于 B 只能连出 D B 两种颜色,故 BD 只能是蓝色线,此时,C、D 都连了 红蓝两色线,它 C 们之间无论连红线还是蓝线均出现同色三角形. 于是每点引出的同色线不超过 2 条,线的颜色不超过 2 种,即不能超过 4 条线.即城市 数≤5. 若城市数=5.由于每点都引出某色线 2 条,另一色线 2 条,设 AB、AC 红色,AD、AE 蓝色,由于 B 应引出 2 条红色,现 BA 红,故还要引出 1 条红线,BC 不能红色(出现同色三 角形),故 BE 红.由于 EA、EB 一红一蓝,故 E 应引出 2 红 2 蓝,由于 ED 不能蓝,故 ED 红.EC 蓝,此时 C、D 都用了 2 色,从而它们也只能用红蓝两色,于是 B 也只能用红蓝两色, 与要用 3 色矛盾. 若城市数=4.可以构成满足条件的图. 10.解法 1 按顶点颜色分类,三角形共有 10 类:三红,两红一蓝,两红一黑,一红两 蓝,一红两黑,红蓝黑,三蓝,两蓝一黑,一蓝两黑,三黑.按线段两端颜色分类,线段共 有 6 类:红红,红蓝,红黑,蓝蓝,蓝黑,黑黑. 现在统计两端分别为红、蓝的边,在两红一蓝或两蓝一红这两类三角形中,每个三角形 都有 2 条红蓝边,每个红蓝黑三角形都有 1 条红蓝边,设前两类三角形共有 p 个,后一类三 角形共有 q 个.则两端红蓝的边共有 2p+q 条. 而每条两端红蓝的边,在大三角形内的红蓝边设有 k 条,每条都被计算了 2 次,大三角形 的红蓝边有 1 条,计算了 1 次.故

2

2

2

2p+q=2k+1,于是 q≠0,即红蓝黑三角形至少有 1 个. 解法 2 在每个划出的小三角形内取一个点,在三角形形外也取一个点.如果两个三角形 有一条红蓝的公共边,则在相应点间连一条线.于是得到了图 G,此时,两红一蓝或两蓝一 红的三角形都是图 G 的偶顶点,而红蓝黑三角形则对应着图 G 的奇顶点,大三角形外的那个 顶点也是奇顶点,由奇顶点的成对性,知图 G 中至少还有一个奇顶点,于是,至少还有一个 红蓝黑三角形. 11.证明:每个异色 K3 的三个角中必有两个角的两边异色,即每个异色三角形对应 2 个 异色角.反之每个异色角都在一个异色三角形内.设第 i 个顶点引出了 xi(0≤xi≤5,i=1,2, 3,4,5,6)条红边,5-xi 条蓝边.则该顶点为顶点的异色角共有 xi(5-xi)个.当 xi=2 或 3 时 xi(5-xi)=6 取得最大值.故异色三角形数≤6×6÷2=18 个. 但 K6 中共可连出 C3 6=20 个三角形,即至少有 20-18=2 个同色三角形. 存在只有 2 个同色三角形的二染色 K6,把 6 点分成两组,每组 3 点,同组连红线,不同 组连蓝线.由于任取三点,必有两点同组,于是必有红线,但如有不同组的点,则必有蓝线. 12.解 共有 C21=210 条航线,而每个航空公司有 C5=10 条航线,故至少要 21 家航空公 司. 画一个 21 边形, 用顶点表示城市, 依次 个五边形它可以由连 1,3,8,9,12 这五 对角线分别对着分圆为 1,2,3,4,5,6, 弧.这个五边形的边长互不重复,且含有了 对角线的所有长度.让这个五边形每次旋转 在的五个点即为第 k 家公司所在的城市.每 会在某次旋转中出现.于是相应城市间的航
2 2

20

21

1

2

3 4 5 6

19
18 17

16 15

O 9

7

14

8

13

12 11 10

编为 1~21 号. 取一 个点而成.其边及 7,8,9,11 等分的 该正 21 边形的边及 1 等分, 旋转 k 次所 个长度的对角线总 线存在.


2012江苏省数学竞赛《提优教程》教案:第67讲_图论问题(一)

2012江苏省数学竞赛《提优教程》教案:第67讲_图论问题(一)_学科竞赛_高中教育_教育专区。第 67 讲 图论问题(一) 本节主要内容是:把一个具体问题用图形表示出来...

2012江苏省数学竞赛《提优教程》教案:第67讲_图论问题(一)

2012江苏省数学竞赛《提优教程》教案:第67讲_图论问题(一) 隐藏>> 第67 讲 图论问题(一) 本节主要内容是:把一个具体问题用图形表示出来,利用图形的直观性可能...

2012江苏省数学竞赛《提优教程》教案:第66讲_覆盖

2012江苏省数学竞赛《提优教程》教案:第66讲_覆盖_学科竞赛_高中教育_教育专区。第 66 讲 覆盖本节主要内容是图形覆盖与嵌入. 一、图形覆盖的定义: 平面闭图形...

2012江苏省数学竞赛《提优教程》教案:第05讲 子集

2012江苏省数学竞赛《提优教程》教案:第05讲 子集_学科竞赛_高中教育_教育专区。第 5 讲 子集本讲内容有子集、子集的个数、集合的划分及子集的应用。 设 ...

2012江苏省数学竞赛《提优教程》教案:第57讲 排列与组合

2012江苏省数学竞赛《提优教程》教案:第57讲 排列与组合_学科竞赛_高中教育_教育...126 个五位 “渐升数” ,若把这些数按从小到大的顺序排列,则第 100 个数...

2012江苏省数学竞赛《提优教程》教案:第63讲_极限

2012江苏省数学竞赛《提优教程》教案:第63讲_极限_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 2012江苏省数学竞赛《提优教程》教案:第63讲...

2012江苏省数学竞赛《提优教程》教案:第47讲角度与距离题目

2012江苏省数学竞赛《提优教程》教案:第47讲角度与距离题目_学科竞赛_高中教育_...67份文档 九妖笑话 2014年笑话大全之让你笑个够 儿童笑话大全爆笑 爆笑笑话精...

2012江苏省数学竞赛《提优教程》教案:第62讲__多项式

2012江苏省数学竞赛《提优教程》教案:第62讲__多项式_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 2012江苏省数学竞赛《提优教程》教案:第...

2012江苏省数学竞赛《提优教程》教案:第60讲 概率2

2012江苏省数学竞赛《提优教程》教案:第60讲 概率2_学科竞赛_高中教育_教育专区。第 20 讲 概率(二) 本节主要内容有:几何概型,期望.各种概率问题选讲 概率的...

2012江苏省数学竞赛《提优教程》教案:第41讲 解不等式

2012江苏省数学竞赛《提优教程》教案:第41讲 解不等式_数学_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 2012江苏省数学竞赛《提优教程》教案:第41...