tceic.com
简单学习网 让学习变简单
相关标签
当前位置:首页 >> 学科竞赛 >>

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


第 68 讲 图论问题(二)
本讲主要内容:本讲将继续研究用图来解决问题的方法. 偶图 取图 G=(V,E),如果 V=X∪ Y,X∩Y=?,其中 X={x1,x2,?,xn},Y={y1, y2,?,ym},且 xi 与 xj(1?i<j?n),ys 与 yt (1?s<t?m)均互不相邻,则称 G 为偶图. 色数:将图 G 的顶点涂上颜色,如果至少要 k 种颜色才能

使任意两个相邻的顶点颜色不 同,则称 G 的色数为 k.显然,偶图的色数?2.即偶图色数不超过 2.

A 类例题
例 1 在空间中给定 2n 个不同的点 A1,A2,?,A2n,n>1,其中任意三点不共线.设 M 是 n +1 条以给定的点为端点的线段的集合.⑴证明:存在一个三角形,其顶点为给定的点, 其边都属于 M.⑵证明:若集合 M 的元素不超过 n2 个,则这样的三角形可能不存在.(1973 年奥地利数学竞赛) 分析 可以从简单的情况开始试验,发现规律再证明.从 K4(4 阶完全图,见 67 讲)共有多 少条线及多少个三角形、擦去 1 条线去掉几个三角形入手得出结论,对于 K5、K6 也能用此法 得到结论,但对于 p>6,Kp 难用此法,如何过渡到一般情况?可以用数学归纳法. 证明:n=2 时,在 4 个点间连了 5 条线,由于 4 阶完全图在 4 个点间共可连出 6 条线, 这 6 条线连出了 4 个以此 4 点中的某 3 点为顶点的三角形.而每条线的两个端点与(除这条线 的两个端点外的)另两个顶点可以连出共 2 个三角形,故去掉任何一条边都使连出三角形数减 少 2,于是在 4 个点间连 5 条线必连出了 v4 v3 以此 4 点中的 3 点为顶点的三角形. v3 设 n=k 时,2k 个点间连有 k2+1 条 v 2k 线时, 必有三角形出现. 则当 n=k+1 时, 2(k+1)个点间连了(k+1)2+1 条线. 此时, v1 v2 v2 v1 任取两个相邻的顶点 v1,v2,如果在其余 (1) (2) 的顶点中有某个顶点与 v1,v2 都连了线, 图4 例如 v3 与 v1,v2 都连了线(图 4(1)),则出 现了三角形.如果其余所有的点与此二点都至多连出 1 条线(图 4(2)),则去掉点 v1,v2 及与这 两点相邻的边,此时,余下 2k 个点,至多去掉了 2k+1 条边,余下至少(k+1)2+1-(2k+1) =k2+1 条边,由归纳假设知,其中必有三角形. 综上可知,命题成立. 说明 若 2n 个点间连了 n2 条边,可以把这 2n 个点分成两组,每组 n 个点,规定同组的 点间都不连线,不同组的任何两点都连 1 条线,这样得到了一个完全偶图 Kn,n,此时共计连 了 n2 条线,但任取三点,必有两点在同一组,它们之间没有连线,于是不出现三角形.
2

例 2 一个舞会有 n(n?2)个男生与 n 个女生参加, 每个男生都与一些女生(不是全部)跳过 舞,而每个女生都至少与 1 名男生跳过舞,证明,存在男生 b1,b2 与女生 g1,g2,其中 b1 与 g1 跳过舞,b2 与 g2 跳过舞.但 b1 与 g2 没有跳过舞,b2 与 g1 没有跳过舞. 分析 就是要给出一种选择方法,按此方法操作,即可选出满足要求的两个男生与两个女 生.可以用极端原理来证明这样的存在性命题. 证明 取所有男生中与女生跳舞人数最多的一 个,设是 b1 . b1 b 2(3) (1) b 1 至少与 1 名女生没有跳过舞, 取没有与 b1 跳过舞的 一名女生为 g2 , g2 至少与 1 名男生跳过舞,设为 b2,显然 b1 不是 b2, 现在考虑所有
(4) g 1

g 2 (2)

没有与 b2 跳过舞的女生,她们不能都没有与 b1 跳过舞,(否则没有与 b1 跳舞的女生人数就比 没有与 b2 跳舞的人数多,b1 就不是与女生跳舞人数最多者).即至少有 1 个女生没有跟 b2 跳 过舞但跟 b1 跳过舞.这个女生即为 g1. 说明 这里就得到了一个偶图{b1,b2}∪{g1,g2}.(图中,括号内的数字表示证明中出现的 先后顺序).极端原理常用于证明存在性命题.

情景再现
1.求证:顶点多于 1 的树是偶图. 2.证明 偶图的色数?2,反之,色数?2 的图是偶图.

B 类例题
例 3 某镇有居民 1000 人,每人每天把昨天听到的消息告诉自己认识的人,已知任何消 息只要镇上有人知道,都会经过这样的方式逐渐地为全镇的人所知道.证明可以选出 90 名代 表,使得同时向他们报告一个消息,经过 10 天,这一消息就为全镇的人知道. 分析 就是要给出一个把 1000 个点的连通图分成 90 个子图的方法,使每个点都在其中 一个子图中,且每个子图的最长的链的长度不超过 10.这样,只要把每个子图的最长链的一 个端点选为“代表” ,就能完成这个任务. 证明 用 1000 个点代表 1000 个居民,两名居民相识,则在两点之间连一线,如此可得 一图,依条件,这个图是连通图.若图中有圈,则我们去掉圈中的一边使圈被破坏而不影响 图的连通性,经过有限次这种手续,可得树 T1000. 在 T1000 中取一条主干 v1v2?vn,取 v11 作为 1 个代表,把边 v11v12 去掉,则此图分成了 2 个连通分支, 在含有 v1 的一棵树中, 每点到 v11 的路的长度都不超过 10, 否则 v1v2?vn 在 T1000 中不是主干,故 v11 知道的消息在 10 天内可以传遍它所在分支的点集所代表的居民;余下另 一分支再取其主干,又按此法得出第二个代表 v22,依此类推,则 T1000 分割成若干棵树:同 样,在含 v22,v33,?的树中,v22,v33,?知道的消息在 10 天内都能传遍树的点集所代表的 居民;由于 1000=11×89+21,且每一个小分支树可能还有分支,从而其顶点数可能超过 11, 所以这样分法,至多分出 89 棵树并余下一个至多有 21 个点的树,该树的链长?20,取此链 的中心 v,则该链上每个点到 v 的距离都?10.现在取 v11,v22,v33,?为代表,最后一棵树 取其中心 v 为第 90 名代表,只要将消息告诉这些代表,则在 10 天之后,每个分支树的点集 所表示的居民全都知道这个消息,问题已获解决. 说明 注意每次在最长链上截去一段后,余下的链的主干不一定就是原来主干的截剩部 分,所以每次都要重新确定主干. 例 4 一个国家的国王打算建 n 个城市且修(n-1)条道路,使每条道路连接两个城市而不 1 2 经过其他城市.而每两个城市都可以互相到达,其间的最短距离恰是 1,2,?,Cn=2n(n- 1)这些数,问在下列情况下,国王的打算能否实现:(1)n=6;(2)n=1998. 分析 就是要画一个树,使任两个顶点的距离都不能相同.对于顶点数少的情况估计是可 能存在的,而要得到 n=6 图可以用构造法.对于 n=1998,估计不会存在,所以可以用反证 法证明. 为了得到 n=6 的情形,长度为 1 与 2 的线 段是要取的,否 则得不到 1,2,这两条线段连结可以得到长 度 3,为得到距 v2 5 v
1

2

1 v3

v1 2 v2 5 v4 1 v3

v64 v 4

8

v5

8

v5

离为 15、14、?的线段,可以取某两个城市间距离为 8(15 的一半),此时 8+7=15,8+6 =14,8+5=13 可以通过增加一条长度为 5 的线段如图得到,再增加一条长为 4 的线即可得 到全部的 15 个数. 解 (1) n=6 时,国王的打算可以实现,城市和道路的分布可依据图所示. ⑵ n=1998 时,国王的打算不能实现,因为符合要求的道路网存在的必要条件是:n 或 (n-2)是完全平方数,证明如下: 用点表示城市,用线表示连接城市的道路,得到一个图 G.由题设,知 G 是 n 阶连通图, 又其线的数目恰为(n-1),故 G 是 n 阶树,因而 G 的任两点之间只存在唯一的通道.把 G 的 顶点二染色:任取一个点 A,对于图中任一点,若它沿唯一的通道到 A 的距离是一个偶数, 则把此点染红(A 也应染红,因 A 到 A 的距离为 0,0 是偶数),否则染蓝. 设红点的数目为 x,则蓝点的数目为 y=n-x.考虑距离为奇数的点对,易知:两点之间 的距离为奇数,当且仅当这两个点一红一蓝.由一个红点和一个蓝点组成的点对有 xy 个.又 1 1 1 1 在 1,2,?,2n(n-1)中,当2n(n-1)为偶数时,其中的奇数有4n(n-1)个;当2n(n-1)为奇 1 数时,奇数有 [n(n-1)+2]个.于是,如果国王的打算可以实现,则必须满足 4 1 xy=4n(n-1) 1 ① 或 xy=4[n(n-1)+2] ②.

此时,对于① ,有 4x(n-x)=n(n-1),即 4x2-4nx+n2-n=0, 解得 n? n n± n x= ,相应的 y= . 2 2 n± n-2 n? n-2 同样,对于②: 有 x= ,y= . 2 2 故只有 n 或(n-2)是完全平方数时, 国王的愿望才可能实现. 但 1998 和 1998-2=1996 都不是完全平方数,故当 n=1998 时,国王的打算不可能实现. 说明 我们只证明了这个条件是必要条件,没有证明这个条件是充分的.对于 n=6,有 6 -2=4 是完全平方数,有可能存在满足要求的图,再通过构造出满足要求的图,才能确定解 存在. 例 5 证明:任意的 9 个人中,必有 3 个人互相认识或 4 个人互相不认识. 分析 即证明, 在任意的 K9 中, 把边涂成红或蓝两种颜色, 则必存在红色 K3 或蓝色的 K4. 或 在一个有 9 个顶点的图 G 中,必存在 K3,或在其补图中,存在 K4. 证明⑴ 如果存在一个顶点,从这点出发的 8 条线中,有至少 4 条为红色,设从 v1 引出的 4 条线为红色,引到 v2,v3,v4,v5.若此 4 点中的某 2 点间连了红色线,则存在红色 K3,若此 4 点间均连蓝线,则存在蓝色 K4. ⑵ 如果从任一点出发的 8 条线中,红色线都少于 4 条.于是从每点出发的蓝色线都至少 5 条.但由于任何图中的奇顶点个数为偶数,故不可能这 9 个顶点都引出 5 条蓝线.于是至少 有一个顶点引出的蓝线≥6 条,例如从 v1 到 v2,v3,…,v7 都引蓝线,则在 v2,v3,…,v7 这 6 个点的图中,必存在红色三角形或蓝色三角形,于是 G 中必有红色 K3,或蓝色 K4. 链接 拉姆赛(Ramsey)问题 - 本题实际上说的是:在有 n 个顶点的图 G 中,有一个 K3,或在其补图 G 中(在 K9 中去掉 G 的所有边后余下的图即 G 的补图)有一个 K4,二者必有一成立.n=9 是保证这一个结论成立 的 n 的最小值.一般的,在一个有 t 个顶点的图中存在 Km,或在其补图中存在 Kn,t 的最小值

是多少?这就是拉姆赛问题.记满足上述要求的 t 的最小值为 r(m,n). 则有 r(m,n)=r(n,m), r(1,n)=r(m,1)=1,r(2,n)=n,r(m,2)=m. 并可证: 定理一 在 m≥2,n≥2 时,r(m,n)≤r(m,n-1)+r(m-1,n). 现在已经求出的 r(m,n)有:r(3,3)=6,r(3,4)=9,r(3,5)=14,r(3,6)=18,r(3,7) =23;r(4,4)=18. 定理二 设完全图 KN 的边涂了 n 种颜色, 则在 N 充分大时, KN 中必有一个同色三角形. 设 rn 是使 KN 中有同色三角形存在在 N 的最小值,则 ⑴r1=3,r2=6,r3=17; ⑵rn≤n(rn-1-1)+2; n! n! ⑶rn≤1+1+n+n(n-1)+…+ + +n!. 2! 1! 上述两个定理都是拉姆赛定理的特例,更一般的结论请参阅单 墫 教授的有关图论的著 作.例如《趣味的图论问题》等

情景再现
3.平面 α 上有 n 条直线,把 α 分成若干区域,证明:可以用两种颜色就可使相邻的区域 都涂上不同的颜色. 4.在 8×8 的棋盘上填入 1~64 的所有整数,每格填一个数,每个数填一次.证明:总能 找到两个相邻的格子(有公共边的两个方格就是相邻的方格),这两个方格中填的数相差不小于 5. 5.证明:任意 14 人中,必有 3 人互相认识或有 5 人互相不认识.

C 类例题
例 6 1990 个人分成 n 组,满足 (a) 每个组中没有人认识同组的所有的人; (b) 每个组中,任意三人中至少有两人互不认识; (c) 每个组中两个互不认识的人,必可在同组中恰好找到一个他们都认识的人. 证明:在每一组中,各人在该组中认识的人数都相同.并求分组个数 n 的最大值.(1990 亚洲与太平洋地区数学竞赛) 分析 条件都是针对某一组的,所以证明应在某个组内进行,由于两点或连线,或未连线, 故可以分两点未连线及两点已连线的情况证明. 要求组数最多,应使每组的人数最少.故求应每组人数的最小值. 解 取其中一组 M,设|M|=m,用 m 个点表示组 M 中的人,若两人认识,则在相应点间 连一条线.于是题设条件可写为: (a) M 中任何一点,与 M 中其余的点没有都连线,即设 x∈M,用 d(x)表示 x 在 M 中的次 数.则 d(x)?m-1. (b) M 中没有连出三角形; (c) 设 x,y∈M.若 x,y 未连线,则存在唯一 z∈M,与 x,y 均连线. 原题即求证:M 中每个点向 M 中点连的线数均相等. 由于 M 中没有点与其余所有的点都连了线,故存在 x,y∈M,且 x,y 未连线.由(c)存 在惟一 z∈M,且 z 与 x,y 都连了线. z
x A y B

p

q

⑴ 记 M 中除 z 外与 x 连线的点集为 A, 与 y 连线的点集为 B, 由(c), A∩B=?, 且由(b), A、B 中任何两点均不相邻.对于 p∈A,由于 p 与 y 不相邻,则有唯一点与 p 及 y 都相邻, 此点必在 B 中,设为 q,同样,B 中任何一点 q?,也必 与 A 中唯一点 p?相邻.且若 p1、p2∈A,则在 B 中与它们相邻的点 q1、 x q2 互不相同, 否 y 则与(c)矛盾(p1、p2 若与 B 中的 q 都连线,则它们与两 个不同的点 x 及 q 都连了线).这说明 A 与 B 的元素有一一对应关系, |A|=|B| . 则 d(x)=d(y). v u ⑵ 若 x,y 连线,则由(a),存在 u∈M,u 与 x 未 连 线 , 则 d(x)=d(u) . 若 u 与 y 也 未 连 线 , 则 由 上 证 , d(u)=d(x)=d(y).若 u 与 y 连线,则存在 v∈M,v 与 y 未连线,d(v)=d(y),当 v 与 x 未连线时, d(x)=d(v)=d(y); 当 v 与 x 连线时, 由(c), v 与 u 必不连线, 于是 d(v)=d(u), 从而 d(x)=d(y). 故 每组中的人认识本组的人数相同. ⑶ 为了求分组个数的最大值, 应找出满足条件的 组中人数的最 z 小值,由(a),有 x,y∈M,x 与 y 不相邻.于是由(c), 存在 z∈M,与 x、y 都相邻.由(a),必还有 u,u 与 z 不相邻(否则 z 与同组的点都 y x 相邻);于是由(c),u 必与 x、y 之一相邻,设 u 与 x 相邻,于是 u 与 y 不相邻.故又存在 v 与 u、y 相邻.这样就有了 5 个点. 从而每组 v u 至少 5 个点.而图中 5 个点满足全部要求. 于是至多可分出 1990÷5=398 组. 例 7 给定平面上的点集 P={P1,P2,?,P1994}, P 中任三点均不共线,将 P 中的所有的 点任意分成 83 组,使得每组至少有 3 个点,且每点恰好属于一组,然后将在同一组的任两点 用一条线段相连,不在同一组的两点不连线段,这样得到一个图案 G,不同的分组方式得到 不同的图案,将图案 G 中所含的以 P 中的点为顶点的三角形个数记为 m(G). (1)求 m(G)的最小值 m0; (2)设 G*是使 m(G*)=m0 的一个图案,若 G*中的线段(指以 P 的点为端点的线段)用 4 种 颜色染色,每条线段恰好染一种颜色.证明存在一个染色方案,使 G*染色后不含以 P 的点为 顶点的三边颜色相同的三角形.(1994 年全国高中数学联赛) 分析 估计当各组点数尽可能接近时三角形个数最少. 因此只要证明当两组点数差?2 时, 不能达到最小值.可以用逐步调整法来证明.第⑵小问可以用构造法来解.注意 K5 的边 2 染 色时,可以找到不存在同色三角形的染色法,于是可以据此构造出满足要求的图来. 解:设 G 中分成的 83 个子集的元素个数分别为 ni(1?i?83), ∑ ni=1994.且 3?n1?
i=1 83

n2???n83. 则 m(G)=
3 ∑ Cn .即求此式的最小值.
i

83

i= 1

3 设 nk+1>nk+1. 即 nk+1-1?nk+1. 则 Cn +Cn3 k+1 k

+1

这 -1-(Cnk+Cnk+1)=Cnk-Cnk+1-1<0.

3

3

2

2

就是说, 当 nk+1 与 nk 的差大于 1 时, 可用 nk+1-1 及 nk+1 代替 nk+1 及 nk, 而其余的数不变. 此 时,m(G)的值变小. 于是可知,只有当各 ni 的值相差不超过 1 时,m(G)才能取得最大值. 1994=83×24+2.故当 81 个组中有 24 个点,2 个组中有 25 个点时,m(G)达到最小值.

m0=81C24+2C25=81×2024+2×2300=168544. ⑵ 取 5 个点为一小组,按图 1 染成 a、b 二色.这样的五个小组,如图 2,每个小圆表示 一个五点小组.同组间染色如图 1,不同组的点间 的连线按图 2 染成 c、d 两色.这 25 个点为一组, a c a c b d 共得 83 组.染色法相同.其中 81 组去掉 1 个点及 b d b d 与此点相连的所有线. 即得一种满 足要求的染色. a a b c b d d c
a c

3

3

例 8 有 n 人聚会, 已知每人至

图1

图2

n 少认识其中的?2?

? ?

n n 个人.而对任意的? ?个人,或者其中有两人认识,或者余下的 n-? ?人中有两人相识.证明: ?2? ?2? 当 n?6 时,这 n 个人中必有 3 人两两认识.(1996 年全国联赛) n 分析 本题与例 6 类似,要通过分析连线的情况找出三角形来.由于题中给出了? ?,故应 ?2? 分 n 为偶数或奇数的情况分别讨论. 证明 作一个图, 用 n 个点表示这 n 个人, 凡二人认识, 则在表示此二人的点间连一条线. 问 题即,在题设条件下,存在以这 n 点中的某三点 为 顶 点 的 三 角 B A 形.设点 a 连线条数最多,在与 a 连线的所有点 中点 b 连线最多, Φ k -1 k 1 与 a 连线的点除 b 外的集合为 A,与 b 连线的点 除 a 外的集合为 B. 1° 设 n=2k, 则每点至少连 k 条线, 集合 A、 B 中都至少有 k-1 2k 个点 个点. a b ⑴若存在一点 c,与 a、b 都连线,则 a、b、 c 满足要求; 图1 ⑵若没有任何两点与 a、 b 二点都连线(图 1), 则由 A∩B=?, |A ∪B|?2k-2,|A|?k-1,|B|?k-1, 故得 |A|=|B|=k-1,且图中每点都连 k 条线.若 A 中任何两点间均未连线,B 中任两点也未连线,则 A∪{b}中不存在两点连线,B∪{a}中也不存 在两点连线. 与已知矛盾. 故在 A(或 B)中必存在两点, 这两点间连了一条线, 则此二点与 a(b) 连出三角形, 2° 设 n=2k+1.则每点至少连 k 条线,A、B 中都至少有 k-1 个点. B A ⑴若存在一点 c,与 a、b 都连线,则 a、b、 c 满足要求; Φ k k-1 ⑵若没有任何两点与此二点都连线,且|A|? k ,则由 |B| ? k - 1(图 2),A∩B=?,|A∪B|?2k-1,可得|A∪B| =2k-1,|A|=k, 2k +1个点 |B|=k-1,若 A 中任何两点间均未连线,B 中任 两点也未连线, 则 b a A∪{b}中不存在两点连线, B∪{a}中也不存在两点 连 线 . 与 已 知矛 图2 盾. 故 A(或 B)中存在两点, 这两点间连了一条线, 则此二点与 a 连 出三角形, ⑶若没有任何两点与此二点都连线,且|A|=k-1,即每点都只连 k 条线.这时,必有一 点与 a、b 均未连线,设为 c (图 3).c 与 A 中 k1 个点连线,与 B 中 k2 个点连线,k1+k2=k, 且 1?k1, k2?k-1. 否则若 k2=0, 则 A∪{b}中各点均未连线, B∪{a, c}中各点也未连线. 矛 盾.故 k1,k2?1.且由于 n?6,则 k1+k2?3,故 k1,k2 中至少有一个不小于 2,不妨设 k1 ?2,现任取 B 中与 c 连线的一点 b1,由于 b1 与 B 中其余各点均未连线,若 b1 与 A 中的所有 与 c 连线的点均未连线,则 b1 连线数?2+k-1-k1?k-1,矛盾,故 b1 至少与此 k1 个点中 的一点连线.故证.

c A k2 B

k-1

k1

Φ

k-1

情景再现

a

2k +1个点 图3

b

6.在正整数 n 与 δ 满足什么条件时,可以 作出一个 n 阶 δ 正则图. 即是:已知 n 个点,其中某些点间连了一条线,且每个点都恰好与 δ 个点连了线.问 δ 可以取什么样的数值? 7. 某次体育比赛,每两名选手赛一场,每场一定决出胜负,通过比赛确定优秀选手, 选手 A 被确定为优秀选手的条件为:对任何其他选手 B,或 A 胜 B,或存在选手 C,有 A 胜 C 而 C 胜 B.如果按这个条件确定的优秀选手只有 1 名.求证:这名选手胜所有其余的选 手.(1988 年中国数学冬令营) 8.给定空间中的 9 个点,任意 4 点不共面,每两点间连一线段.求最小的 n 值,使当对 其中任意 n 条线段用红、蓝两色之一任意染色时,都一定出现一个三边同色的三角形.(1992 中国数学奥林匹克)

习题 13
1.⑴ 如果在偶图 G=(X,Y,E)中,|X|>|Y|,且 X 中每个顶点的次数都不小于 δ,求证: Y 中至少有一个顶点的次数>δ. ⑵ 若图 G 为偶图,且 G 有圈,则 G 的圈的长为偶数.反之,若图 G 有圈,且所有的圈 长为偶数,则 G 为偶图. 2.设 C 是 100 阶 3 正则图,现用红、白两色给这 100 个点着色,其中红点 40 个,白点 60 个,如果一条线的两个端点都是红色,则将这条线也染成红色;如果一条线的两个端点都 是白色,则将这条线也染成白色,现已知红色线有 38 条,问白色线有多少条? 3.若干人相聚,其中有些人彼此认识,若⑴如果某两个人认识的人数相等,则他们没有 共同的熟人;⑵有一个人至少有 100 个熟人.证明:可以找到一个参加聚会的人,他恰好有 100 个熟人. 4.有 2n 个学生,每天出去散步,每两人一组,如果每一对学生只在一起散步一次,这 样的散步至多可以持续多少天? 5.20 名选手参加 14 场单打比赛,每名选手都至少参加过 1 场.证明:必有某 6 场比赛 的参赛者是 12 名不同的选手.(1989 年美国数学竞赛) 6.在 n?n 棋盘的方格中分别填写 1,2,?,n2(n?2),每格一个数.证明:必有两个相 邻方格(有公共边的方格),方格中的两个数的差至少为 n.(1988 年捷克数学竞赛) 7.把 Kn 中的每条线段染上红色或蓝色.把某一点出发引出两条同色线段组成的角叫做 1 同色角.证明:同色角的总数不小于 n(n-1)(n-3). 4 8.用黑白两种颜色去涂正九边形的顶点,每个顶点只涂黑、白两色之一,证明:在以这 九点为顶点的所有三角形中,必有两个顶点同色的全等三角形. 9.⑴ 将完全图 K5 中的 10 条线段进行染色,使得有公共端点的线颜色不相同.至少要 用几种颜色? ⑵ 将完全图 K2n 中的所有线段染上颜色,使得有公共端点的线颜色不相同.至少要用几 种颜色? ⑶ 证明:将完全图 K2n-1 中的所有线段染上颜色,使得有公共端点的线颜色不相同.至 少要用 2n-1 种颜色.

10.某团体中任意两个认识的人都没有共同的熟人,而任意两个不认识的人都恰有两个 彼此共同的熟人.证明:该团体中每个人认识的人数都相同.(1975 南斯拉夫数学竞赛) 11.某次体育比赛,每两名选手各赛一场,无平局.通过比赛确定优秀选手.设 A 为选 手,如果对其他任意选手 B,要么 A 胜 B,要么存在选手 C,使得 A 胜 C,C 胜 B,则 A 即 是优秀选手.证明:如果按上述规则选出的优秀选手只有 1 名,则这名选手胜其他所有的选 手.(1987 年中国数学奥林匹克) 12.排球比赛中,每两队都各比赛一场.对两个球队 A 与 B,如果 A 胜 B,或者存在某 个球队 C,使得 A 胜 C,C 胜 B,则称 A 优于球队 B.比赛结束后,优于其他所有球队的球 队即被授予冠军称号.比赛结束后能否恰有两个冠军队?(1988 年前苏联数学竞赛) 本节“情景再现”解答: 1.证明 任取树 T 的一个悬挂点 v1,把 v1 涂红,所有与 v1 距离为奇数的顶点都涂蓝,所 有与 v1 距离为偶数的顶点都涂红,所有涂红的顶点组成集合 X,所有涂蓝的顶点组成集合 Y, 则得到一个二色图,即为偶图. 2.证明 设 G=(X,Y,E)是偶图,把 X 中的点全部涂成红色,把 Y 中的点全部涂成蓝 色,则所得的图中,相邻的顶点涂色都不同,即只用 2 色即可涂完 G 的所有顶点,使相邻的 顶点涂色不同.又如果 G 没有边,则只用 1 种颜色即可把 G 的所有顶点涂好,且没有任何相 邻的顶点同色(因没有顶点相邻),故偶图的色数?2. 反之若图 G 的色数?2,若色数=1,表示 G 中任何两顶点都不相邻,即 G 没有边,此 时,设 G 为 n 阶的,可把 G 中 k(1≤k≤n-1)个点涂成一种红色,另外 n-k 个点涂成蓝色,即 得一个二色图,涂红的点集为 X,涂蓝的点集为 Y,即为偶图.若色数=2,即用两种颜色可 以把所有顶点涂色,且同色点都不相邻,则取涂一种颜色的点的集合为 X,涂另一种颜色的点 的集合为 Y,则得到一个偶图.即色数?2 的图是偶图. 3.证明 n=1 时,1 条直线把平面分成 2 部分,可用两种颜色涂. 设 n=k 时,k 条直线把平面分成的区域有满足题意的涂色法,当 n=k+1 时,先画出其中 k 条直线,而暂把第 k+1 条直线擦去.这时 k 条直线把平面分成的区域可以涂色.涂好色后, 把第 k+1 条直线画出,凡在这条直线某一侧的部分,涂色不动,而在直线另一侧的部分,把 涂的色全部改为另一色,则所得涂色满足题意.即 n=k+1 时,命题成立. 综上可知,命题成立. 4.证明 取每个方格的中心,凡是相邻的两 个方格, 就把相应 的中心连一条线.这样得到了一个图 G(图中红 线 组 成 的 图 即为 图 G). 图 G 的的直径=14, ,故图 G 中任意两点的 距离≤14. 若相邻两个方格中填的数相差<5,则差≤4, 于是图 G 中所填 两个数的差≤14×4=56.但图中填了 1 与 64,此 二 数 必 有 一 条链 相连,此链的长≤14.即其差≤56,与 64-1=63 矛盾. 5.证明:以点表示人,红色线表示认识, 蓝 色 线 表 示 不认 识. ⑴ 若存在一个点,从这点引出了至少 5 条红线,例如从 v1 向 v2,v3,?,v6 引出了 5 条红线,若 v2,v3,?,v6 间有某两点间连了红线,则这两点与 v1 组成红色三角形,否则此 五点间全部连蓝色线,为一蓝色五边形. ⑵ 若从任一点引出的红线都少于 5 条,则每点引出的蓝色线都至少 9 条.由例如从 v1 到 v2,v3,?,v10 均连蓝色线,则由例 5 可知 v2,v3,?,v10 中或存在红色三角形或存在蓝 色四边形,于是原图中或有红色三角形,或此蓝色四边形与 v1 合成一蓝色五边形.故证.

1 1 6.证明:由于共计连了 nδ 条线.故 δ 应是不超过 n-1 且使 nδ 为整数的那些正整数 2 2 值. 1 反之若正整数 δ 不超过 n-1, 且使2nδ 为 种连法:取一圆分成 n 等分. n 任取一数 i,满足 1?i??2?,把圆上这 n
13 4 12 5 11 6 10 7 9 8 16 15 1 2 3

整数,可构造一

? ?

个点中,距离为 2 条线,当 n 为

n i 的点都连起来,这时当 i≠2时,每个点都连了 n 偶数,且 i= 时,每个点都连了 1 条线. 2

16阶5正则图

如果 n 为奇数,则 δ 必须为偶数:δ=2k,如果 n 为偶数,则 δ 可为奇数,也可为偶数. 若 δ=2k<n, 依次取 i=1, 2, ?, k, 按上法连线, 则得到每个点都连了 2k 条线; 若 δ=2k+1 n <n,则按上法连了 2k 条线,后再取 i= 连线,此时每个点又连了 1 条线,即每个点都连了 2 2k+1 条线.于是可知,可以连出满足要求的图. 如图示即是一个 16 阶 5 正则图,分别取 i=2,4,8 画出. 7.证明:取 A 为胜场最多者,若 A 胜所有选手,此时 A 为优秀选手. 若 A 未全胜,则 A 必负于某个选手 B,此时若找不到 C,使 A 胜 C 而 C 胜 B,即所有负 于 A 的选手都负于 B,则 B 比 A 胜场更多,矛盾.故必存在这样的 C 胜 B.故此时 A 为优秀 选手. 若只有 1 名优秀选手,即优秀选手只有 A,于是其余选手均不是优秀选手.若 A 负于 B, 由于 B 不是优秀选手,则存在 D,D 胜 A 与 B,若 D 不存在.即其余所有选手或负于 A,或 负于 B,则 B 也为优秀选手.故 D 必存在.现 D 胜 A、B,由于 D 不是优秀选手,同理,故 必能找到 E,胜 A、B、D,?,这样一直下去,最后必有一人胜所有其余的人,为优秀选手, 与只有 1 名优秀选手矛盾.故 A 全胜. 8.解:设染色的线段至少有 33 条,则因 9 个点之间两两连线有 C9=36 条,故不染色 的线段至多有 3 条. 设点 A 引出不染色的线段,则去掉点 A 及所引出的线段.在剩下的点及线段中,若还有 点 B 引出不染色的线段,同样地再将 B 及引出的线段去掉,依次进行. 因不染色的线段至多 3 条,所以至多去掉 3 个顶点,则还剩下 6 个顶点,其两两连线都 染上了红色或蓝色.即得到 K6(6 阶完全图)图的 2-染色.熟知,存在同色三角形. 其次,存在一个 9 顶点 32 条边的图,把图的边 2-染色,可使图中无同色三角形.如图所 示,将 9 个点分成 5 组{V1,V2}、{V3,V4}、{V5,V6}、{V7,V8}、{V9},两组间连一条实线表 示从这两组中任取一点都连有红线;两组间连一条虚线表示从这两组中任取一点都连有蓝线; 每一组内部的点之间不连线.该图构成有 9 个顶点,有 C9-4=32 条边,且不存在 2-染色的 同色三角形.从而,所求的最小 n 值为 33. “习题 68”解答: 1.⑴证明 X 中所有点连线的总数应等于 Y 中所有点连线的总数. 因 X 中的点共至少连出了|X|?条线.如果 Y 中点的次数都不大于?,则 Y 中点连出的线的
2 2

条数?|Y|?,由于|X|>|Y|,故|X|?>|Y|?.矛盾. ⑵证明,若 G 为偶图,即其顶点可以二染色,使相邻顶点染色不同,对于 G 的任一圈, 取圈上的任一顶点 v1,从 v1 出发,沿圈前进,最后回到 v1,经过的顶点染色为 x→y→x→? →y→x(最后回到起点,染色仍为 x),即经过了偶数个顶点,故圈长为偶数. 若 G 的所有圈长都为偶数,不妨设 G 为连通的,否则可以分别考虑其连通分支.现取 G 的任一顶点 v,规定从 v 到某个顶点 v?的一条链长为偶数时,把 v?染红,否则把 v?染蓝.设 v1 为圈上的任一顶点,则从 v 到 v1 存在两个不全同的链,由于圈长为偶数,故此两个链长奇偶 性相同,于是每个顶点都可涂成确定的颜色,且相邻的两顶点涂成颜色不同.即 G 为偶图. 2.解 因为红色线的两个端点都是红色的,所以红点的度的和 3× 40=120 中有 2× 38=76 是与红色线关联的,另外的 120 一 76=44 个度所关联的线的两个端点中一个是红点,另一个 是白点,所以白点的度的和 3× 60=180 中有 44 是与没有染上颜色的线关联的.也就是说,有 180 一 44=136 个度是与白色线关联的,所以白色线有 136÷ 2=68 条. 3.证明:在所有的人当中,设 A 认识的人最多(如果认识的人数最多的人有几个,则任 取其中一人为 A). 则 A 认识的人数?100,设 A 认识的人为 B1,B2,?,Bn (n?100),又 B1,B2,?, Bn 分别认识 b1,b2,?,bn 人.由于 Bi 与 Bj 有共同的熟人 A,故 Bi 与 Bj 认识的人数不同, 这说明所有 bi 都互不相等.但所有 bi?n,且由于 Bi 至少认识 A,故 bi>0. 所以 b1,b2,?,bn 恰等于 1,2,?,n.但 n?100,故必有某个 bi=100. 4.解 由于每人只能与其余 2n-1 人出去散步一次,故至多可能持续 2n-1 天. 为了保证这样的散步可以安排, 可以画一个圆, 把这个圆分成 2n-1 等分. 把圆心袤为 1, 圆上的分点依次记为 2,3,?,2n,先画出一批弦:把 1 与 2 连起来,再连 3 与 2n,4 与 2n-1,?,即把过 3,4,?,n-1,n,n+1 而与 1,2 连线垂直的弦连出,连线的两人第 2π 一天出去散步,把这些连线绕 1 旋转 ,连线的人(1 与 3,4 与 2,5 与 2n,?,)第二天 2n- 1 2π 散步,以后每天都是绕 1 旋转 ,?,这样经过 2n-1 天,每个人都与其余 2n-1 个人 2n-1 出去散步一次.即终止.(图中连的实线表示第一天,虚线表示第二天,??) 除 2n 外,第 i 天,若 k+m≡i(mod 2n-1),(1?k,m?2n-1),则 k 与 m 配对,而 2n 与余下 1 人配对. 这只要证明:对于每个 k(1?k?2n-1),与之配对的元素每天都不同,对于 2n,每天与 之配对的元素也不同. 5.解:用 20 个点表示这 20 个人,若某两人比赛过就在表示这两人的点间连 1 条线,题 意即:已连了 14 条线,每点至少连了 1 条线.求证:有 6 条线,连的 12 个点互不相同. 设此 20 个点的度分别为 d1,d2,?,d20,则 d1+d2+?+d20=28. 把度为 di 的顶点处连接的 di-1 条边删去. 则至多删去了(d1-1)+(d2-1)+?+(d20-1)=28 -20=8 条边, 于是还剩下 6 条边,但每个顶点的度?1.即此 6 条边连接 12 个顶点. 6.解:反设任何相邻方格中写的数都?n-1. 取 Ak={1,2,?,k}(1?k?n2-n),Bk=(k+n,k+n+1,?,n2},Ck={k+1,k+2,?, k+n-1},则 Ak,Bk 元素不能相邻.它们只能与 Ck 的元素相邻.由于|Ck|=n-1,故必有一行 及一列没有 Ck 中的元素.这一行及这一列中只能是 Ak 的元或只能是 Bk 中的元.由 Ak 与 Bk 中的元不能相邻,于是这一行及这一列必全为 Ak 中的元,或者全为 Bk 中的元. 对于 k=1,由于 A1 只有一个元,故相应行与列中的元应全是 B1 中的元,对于 k=2,?, n-1,均有相同的结论即存在一行及一列全是 Bk 的元.而对于 k=n2-2n+1,n2-2n+2,?

n2-n,则存在一行及一列,全是 Ak 的元.即存在 l,使 B1,B2,Bl 中的元能占满一行及一列, 而 Al+1 中的元则占了一行及一列.此两行与两列相交处的方格中的元即是 Bl 的元,又是 Al+1 的元.设为 a 则 a∈{1,2,?,k+1},且 a∈{k+n,k+n+1,?n2}.由于 n?2,这是不可能 的.故证.
2 7.证明:设从顶点 Vi 引出 xi 条红线,n-1-xi 条蓝线,则从 Vi 共引出 Cn- 1个角,其中

1 1 异色角有 xi(n-1-xi)个,但 xi(n-1-xi)?4(n-1)2,故每个顶点引出同色角数?2(n-1)(n- 1 1 2)-4(n-1)2=4(n-1)(n-3). 1 故同色角总数? n(n-1)(n-3). 4 8.证明:任意两个顶点连线的中垂线必经过另一个顶点,且除此 3 点外的另 6 点可分成 3 对,每对的两个点关于这条中垂线对称. 9 个点涂成两种颜色,必有一种颜色的点不超过 4 个,不妨设白 点不超过 4 个. 设白点只有 3 个,取任意 2 个白点,除这两个白 点、 这两个白点 的中垂线上的顶点及第 3 个白点与它关于这条中垂线 的对称点, 余下 2 对对称点中都是黑点,此 4 个黑点就可连出两个全 等三角形. 若白点有 4 个,这 4 个白点间可连 6 条线段,这 6 条连线的中 垂线上的顶点有 6 个.但红点只有 5 个,故或者某条 中垂线经过白 点,即化为上一情形;或有某两条中垂线过同一个红点,于是,相应的白点连线平行,故此 4 个白点可以连出两个全等三角形. 9⑴解:由于从一点出发了 4 条线,故至少要 4 色,下面说明 4 色不够:考虑从 V1、V2 连颜色 a,则 V3、V4、V5 只有两种 可能连法 ( 实质 V V 相同),如左图.此时 V3V4、V5V4 两条中必有一 V V c d 条无法染色,即需要至少 5 色,而 5 色可以染,只 V V d c 要作图即得(如右图). b b a ⑵证明:每点引出 2n-1 条 线,即至少 2n V V V V -1 色,即色数?2n-1. 又对于 2n 个点,可排出表:把点编号 0, 1, 2, ?, 2n-1. 把 1 2 2n-1 圆 2n-1 等分,0 放在圆心,其余各号排成一 圈,0 与 k 连线及 2n-2 3 所有与此连线垂直的弦用第 k 种颜色染, 这样 2n-1 种颜色即能 2n-3 4 染成.故证. 0 5 ⑶ 证明:⑴由于 K2n 可用 2n-1 种颜色 2n-4 染色,故去掉其中 一个顶点及其所连的边,得到 K2n-1,也可用 2n - 1 种 颜 色 染 成.即所需色数?2n-1.
4

4

5

3

5

3

1

2

1

2

1 若只用 2n-2 色,由于图中共有 (2n-1)(2n 2

- 2) 条线,于是必

1 有一种颜色染了[2(2n-1)(2n-2)÷2]+1=n 条线,这 n 条线若无公共顶点,则有 2n 个顶点, 而此图只有 2n-1 个顶点,故 2n-2 色不够.故所需色数>2n-2.从而必须用 2n-1 色.证 毕. 10.解:以 n 个点表示该团体中的人,两人认识,则在表示两人的点间连一条线,问题
A D B C
A B A1 Ak Bk B1

是:若两点连了线,则它们不能与同一第三点连线,即不出现三角形,若两点间未连线,则 它们恰与另两个点都连了线. 首先证明任意两个连线的点的次数相同.设 AB 连线,则它们除彼此外没有连向同一点, 设 A 与 A1,?,Ak 连了线,则 A1,?,Ak 间均不连线,B 与 A1,?,Ak 均不连线.此时 B 与 Ai 除 A 外必还有一点连线,设为 Bi,且 Bi 与 Bj 不同,否则 A、Bi 与 3 点都连了线.于是 与 Ai 对应的与 B 连线的点有 k 个.即|B|?|A|,同理,|A|?|B|.即|A|=|B|. 其次, 若 C、 D 未连线, 则 C、 D 都与 E、 F 连线, 则|C|=|E|, |D|=|E|, 于是|C|=|E|=|F|. 于 是得证. 11.证明:取 A 为胜场最多者,则或 A 胜所有选手,此时 A 为优秀选手. 若 A 未全胜,则 A 必负于某个选手 B,此时若找不到 C,使 A 胜 C 而 C 胜 B,即所有负 于 A 的选手都负于 B,则 B 比 A 胜场更多,矛盾.故必存在这样的 C 胜 B.故此时 A 为优秀 选手. 若只有 1 名优秀选手,即优秀选手只有 A,于是其余选手均不是优秀选手.若 A 负于 B, 由于 B 不是优秀选手,则存在 D,D 胜 A 与 B,若 D 不存在.即其余所有选手或负于 A,或 负于 B,则 B 也为优秀选手.故 D 必存在.现 D 胜 A、B,由于 D 不是优秀选手,同理,故 必能找到 E,胜 A、B、D,?,这样一直下去,最后必有一人胜所有其余的人,为优秀选手, 与只有 1 名优秀选手矛盾.故 A 全胜. 12.解:首先证明:按此规则,至少有 1 个冠军: 若 A 全胜,则 A 必 M 为冠军.若无人全胜,设 A 为胜场最多者,把余下的队 分成两个集合: A B M={胜 A 的队},N={负于 A 的队}.设 B∈M,则可在 N 中找到 C, 使 C 胜 B, C 反 N 中设找不到胜 B 的队,则 B 胜 N 中所有的队,于是 B 比 A 的胜场至少多 S 1.与 A 的假设矛盾.故 A 优于 M 中所有的队,又 A 又 优于 N 中所有的队, D 故 A 为冠军. T 设有两个球队都得了冠军.不妨设为 A 与 B,A 与 B 必比赛,设 A 胜 B, 由于 B 也优于 A,故存在 C 使 B 胜 C 而 C 胜 A.取胜 A 但负于 B 的队的集合 S,则由 C 的 存在,S??.及胜 A 又胜 B 的集合 T.再取所有负于 A 的队的集合 M,于是 S∪T∪M∪{A, B}即为全体参赛队. 若 T 非空,则由于 T 是每两队也要比赛 1 场,故也可找出 T 中的冠军队 D,D 优于 T 中 每个队. 由于 D 胜 B, 故 T 优于 B 及 S 中的每个队, T 胜 A, 故 T 优于 A 及 M 中所有的队. 于 是 T 也为全部队的冠军.与恰有两个冠军队的假设矛盾.故 T=?. 于是,用同样的方法可知:S 中也将产生冠军队,该冠军队也是全部队的冠军,矛盾.故 不可能恰有两个冠军队.


推荐相关:

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

2012江苏省数学竞赛《提优教程》教案:第68讲_图论问题(二)_学科竞赛_高中教育_教育专区。第 68 讲 图论问题(二) 本讲主要内容:本讲将继续研究用图来解决问题...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com