当前位置:首页 >> 学科竞赛 >>

图论问题选讲答案


图论问题讲义答案 例 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.于是异色三 36 角形数≤ =18. 2 由于共有 C2=20 个三角形.故至少有 2 个同色三角形. 6 ⑶ 空间 5 点,无 3 点共线,每两点连 1 条线,染红或蓝,是否一定存在 1 个以其中三 A 点为顶点的三角形.三边同色? E B 解:不一定,如图,五边形 ABCDE 中,染了 5 条红边 5 条蓝边,其中没有同色三角形. ⑷ 把数 1,2,3,4,5 任意分成两组,试证明:在这两组数中,总有一组数中存在两 C D 个数,它们的差(的绝对值)也在这一组中. 解:任取 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 条线, 其中必有一 v1 v2 v1 v2 v1 v2 v1 v2 种颜色线≥3 条, 即或红线≥3 条 或蓝线≥3 条. 把连出红线≥3 条 v3 v6 v3 v3 v3 v6 v6 v6 的点称为 A 类点,连出蓝线≥3 v4 v5 v4 v4 v5 v5 图3 v4 图1 v5 条的点称为 B 类点,则 A 类点或 图2 图4 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 条线段用红、蓝两色之一任意染色时,都一定出现一个三边同色的三角形.

-1-

解:设染色的线段至少有 33 条,则因 9 个点之间两两连线有 C9=36 条,故不染色的线段至多有 3 条. 设点 A 引出不染色的线段,则去掉点 A 及所引出的线段.在剩下的点及线段中,若还有点 B 引出不染 色的线段,同样地再将 B 及引出的线段去掉,依次进行. 因不染色的线段至多 3 条,所以至多去掉 3 个顶点,则还剩下 6 个顶点,其两两连线都染上了红色或 蓝色.即得到 k6(6 阶完全图)图的 2-染色. 熟知,存在同色三角形. 其次,存在一个 9 顶点 32 条边的图,把图的边 2-染色, 9 可使图中无同色三角形. 如图所示, 9 个点分成 5 组 A={V1, 将 1 8 A V2}、B={V3,V4}、C={V5,V6}、D={V7,V8}、E={V9}, 两组间连一条红线表示从这两组中任取一点都连有红线; 两组 E 2 B 间连一条蓝线表示从这两组中任取一点都连有蓝线; 每一组内 7 部的点之间不连线. 该图构成有 9 个顶点, C9-4=32 条边, 有
2
D C
6 4 且不存在 2-染色的同色三角形. 5 从而,欲求的最小 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 矛盾.

2

3

n2 例 5.⑴ 证明:有 n 个顶点且不含三角形的图 G 的最大边数为? ?. ?4? 证明: v1 是 G 中具有最大度数的顶点, 1)=d. 设 d(v 又设与 v1 相邻的 d 个顶点为 vn, n-1, vn-d+1. v ?, 由 n2 于 G 不含三角形,所以 vn,vn-1,?,vn-d+1 均互不相邻.故 G 的边数 e≤(n-d)d≤ . 4 n2 由于 G 的边数为整数,故 e≤? ?. ?4? n 当 n=2m 时,取二部图 G=Km,m.当 n=2m+1 时,取二部图 G=Km+1,m.即满足 e=? ?. ?4? n2 ⑵ 设 Z 为空间含有 n(n≥4)个点的点集, 其中任意四点不共面,这些点之间连有? ?+1 条线段.证明: ?4? 这些线段必可构成两个有公共边的三角形.(当 n 为偶数时的情况即是 1987 年国家集训队选拔考试题) 证明: n=4 时, 中共有 4 个点, Z 共连有 5 条线段, 由于 4 点间共可连 6 条线段, 共组成 4 个三角形. 每 条线段与不在其上的两点各可组成一个三角形,故去掉任一条线段,则减少 2 个三角形.即 4 点连 5 条线 段必连出两个有公共边的三角形. 52 n=5 时,Z 中 5 个点连? ?+1=7 条线段,必有一点连线段数不 ?4? 超过 2 条(如果每点连线段数≥3, 则统计每点的连线数的和≥3?5=15 条,由于每条被统计了 2 次,应是 2?7=14 条).去掉连线数不超过 2 条的点及其所连线段,则至多去掉 2 条线段,余下 4 点至少连了 5 条 线段,如上证,必有两个有公共边的三角形. 设 n=k(k≥4)时,命题成立.当 n=k+1 时,由于统计各点连出
-22

v3 v3

v4 v 2k

v1
(1)

v2
图4

v1

v2
(2)

(k+1) ? 1 ? ?(k+1) ? ? 线段数的和=2? ? 4 ?+2.则连线数最少的点 A,则点 A 的连线数≤k+1?2? 4 ?+2?. 当 k=2t 时,?
2 (k+1)2? t+1 1 ? ?(k+1) ? ? 1 =t(t+1). 2 +2 = (2t2+2t+2)=t+ .即该点连线段数≤ ? 4 ? k+1? ? 4 ? ? 2t+1 2t+1

2

2

k2 t.此时,去掉点 A 及所连之线段,则余下 k 个点,且余下线段数≥t2+1=? ?+1. ?4? 当 k=2t-1 时,?
2 (k+1)2? 2 1 ? ?(k+1) ? ? 1 2 1 =t . 2 ? 4 ? ? ? 4 ?+2?=2t(2t +2)=t+ t .即该点连线段数≤t.此时,去 k+1

掉点 A 及所连之线段,则余下 k 个点,且余下线段数≥t2-t+1=?

(2t-1)2? k2 +1=? ?+1. ?4? ? 4 ?

于是,由归纳假设可知,余下点及线段中,必有两个有公共边的三角形. 综上可知,命题成立. 例 6.S 为 m 个无序正整数对(a,b)(即(a,b)与(b,a)是相同的)(1≤a,b≤n,a≠b)组成的集合.证明: 4m n2 至少有 (m- )个三元数组(a,b,c),适合:(a,b),(b,c),(c,a)都属于 S. 3n 4 证明:作一个图 G=(V,E),以点 vi 表示数 i(i=1,2,?,n),当且仅当(i,j)∈S 时,在点 vi 与 vj 间 4m n2 连 1 条线段.于是图 G 有 n 个顶点,m 条边.问题转化为:图 G 中至少有 (m- )个三角形. 3n 4 令顶点 vi 的度为 di,取 G 的任一条边 vivj,则 vi 与 vj 共向其余的顶点引出 d1+d2-2 条边.从而共有 di +dj-n 对分别由 vi 与 vj 引向同一顶点的线段,与 vivj 组成三角形.因此 G 中至少有 di+dj-n 个以 vivj 为一 1 边的三角形.但这个三角形在 G 三边上被计数了 3 次.从而 G 中三角形数 k 满足 k≥ (d +dj-n). 3v v ∈E i

Σ

i j

1 n 注意到 di 在上述和式中出现了 di 次,而 G 中共有 m 条边,故 k≥ ( d2-mn). 3 i=1 i

Σ

由于

i=1

Σ

n

di=2m,故 n

i=1

Σ

n

d2≥( i

i=1

Σ

n

di)2=4m2?

4m2 d2≥ . i n v v ∈E

Σ

1 4m2 4m n2 ∴ k≥ ( -mn)= (m- ). 3 n 3n 4

i j

例 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 等分,每份长为 ml m ,每名儿童取 1 份,由于 >1,故每块巧克力至多分成了两 n n
-3-

块,满足题意. m m 1 m 1 当 m<n 时, <1,于是每块巧克力都要被切开.如果 < ,显然不能按要求能分成; 当 = 时, n n 2 n 2 只要把每块巧克力二等分即可得到满足要求的分法;当 1 m < <1 时.用 n 个点表示这 n 名儿童,若某两 2 n

人各取了同一块巧克力的两部分,就在表示相应的人的点间连一条线.这就得到了一个图.若此图有 k 个 连通分支.每个分支分别有 m1、m2、?、mk 条边与 n1、n2、?、nk 个顶点,由于每个儿童分得的巧克力相 等, 故 m1 m2 mk m = =?= = . 因每个连通分支是顶点数多于边数的连通图, 所以必有 mi=ni-1(i=1, ?, 2, n1 n2 nk n n m ,m1=m2=?=mk= , k k m n = -1,即 m=n-k. k k

k).于是,n1=n2=?=nk=

因此,可以分的一个必要条件是:存在 m、n 的一个公约数 k,使

n-1 这个条件也是充分的.首先,当 k=1 时,因为每个儿童分得一块巧克力的 ,可以把每块巧克力切 n 成 n-1 1 n-1 1 与 的两块,前 m-1 名儿童每个人取 ,最后一名儿童取 n-1 个 即可. n n n n n-k k n-k m 对于 k>1,可以把每块巧克力切成 与 的两块,前 m-k 名儿童每个人取 ,后 k 名儿童取 个 n n n k k m k m n-k ,此时后 k 名儿童取 × = = .于是每人分得的巧克力数相等. n k n n n 例 9.亚瑟王(传说中的英国国王)在王宫中召见他的 2n 名骑士,其中某些骑士之间互相有仇,已知每 个骑士的仇人不超过 n-1 个,证明:摩尔林(亚瑟王的谋士)能够让这些骑士围着圆桌坐下,使每个骑士都 不与他的仇人相邻. A 证明:如果两人不是仇人,就称这两人为朋友.把这 2n 个人任意排列成一圈, B 如果相邻两人是朋友, 就把他们连一条线. 这时这个圈就断成若干段.从某一人出发, 顺时针检查,遇到第一个断开的地方,例如相邻的 A1 与 B1 间断开.现从 B1 下面的人 开始检查每个 A1 的朋友:必能找到相邻两人 A2、B2,其中 A1 与 A2 是朋友,B1 与 B2 也是朋友. B A 若每个与 A1 是朋友的人后面的人都是 B1 的仇人,由于 A1 的朋友至少有 n 个,而 B1 的仇人不超过 n-1 个, 从而每个 A1 的朋友后面的人不可能都是 B1 的仇人. 即这样 的两个人是能找到的.现在把此圆周上从 B2 顺时针向后直到 A1 的一段不动,而把从 B1 到 A2 的一段保持相 邻关系翻转,使 A2 转到 A1 后面而 B1 转到 B2 前面.这样,除 A1、A2 及 B1、B2 由原来不相邻变为相邻外其 余的人的相邻关系没有改变,而此时原来 A1B1 断开之处已被 A1A2 连接替代.即断开处至少减少了 1 处. 由于圆圈上断开处只有有限处,而每经过这样一次调整可以使断开处减少 1 处.故经过有限次调整, 就能得到满足要求的坐法.
1 1 2 2

n n 例 10.有 n 人聚会,已知每人至少认识其中的[ ]个人.而对任意的[ ]个人,或者其中有两人认识,或 2 2 n 者余下的 n-[ ]人中有两人相识.证明:当 n≥6 时,这 n 个人中必有 3 人两两认识. 2 证明:作一个图,用 n 个点表示这 n 个人,凡二人认识,则在表示此二人的点间 连一条线.问题即,在题设条件下,存在以这 n 点中的某三点为顶点的三角形.设点 a 连线条数最多,在与 a 连线的所有点中点 b 连线最多,与 a 连线的点除 b 外的集合 为 A,与 b 连线的点除 a 外的集合为 B. 1° 设 n=2k,则每点至少连 k 条线,A、B 中都至少有 k-1 个点. ⑴若存在一点 c,与 a、b 都连线,则 a、b、c 满足要求;
-4A B

k -1 Φ k -1
2k个点

a

图1

b

⑵若没有任何两点与 a、b 二点都连线(图 1),则由 A∩B=?,|A∪B|≤2k-2,|A|≥k-1,|B|≥k-1, 故 得 |A|=|B|=k-1,且图中每点都连 k 条线.若 A 中任何两点间均未连线,B 中任两点也未连线,则 A∪{b} n 中不存在两点连线,B∪{a}中也不存在两点连线.与已知矛盾(与“对任意的[ ]个 2 n 人,或者其中有两人认识,或者余下的 n-[ ]人中有两人相识”矛盾).故在 A(或 2
A B

k

Φ

k-1

2k+1个点 B)中必存在两点,这两点间连了一条线,则此二点与 a(b)连出三角形, b a 2° 设 n=2k+1.则每点至少连 k 条线,A、B 中都至少有 k-1 个点. 图2 ⑴若存在一点 c,与 a、b 都连线,则 a、b、c 满足要求; ⑵若没有任何两点与此二点都连线, 且|A|≥k,则由|B|≥k-1 时(图 2), 则由 A ∩B=?,|A∪B|≤2k-1,|A|≥k,|B|≥k-1, 故得|A∪B|=2k-1,|A|=k,|B|=k-1,若 A 中任何两点间均未 连线,B 中任两点也未连线,则 A∪{b}中不存在两点连线,B∪{a}中也不存在 c 两点连线.与已知矛盾.故 A(或 B)中存在两点,这两点间连了一条线,则此二 A B 点与 a 连出三角形, k k-1 k 1 Φ 2 k-1 ⑶若没有任何两点与此二点都连线,且|A|=k-1,即每点都只连 k 条线.这 时,必有一点与 a、b 均未连线,设为 c.c 与 A 中 k1 个点连线,与 B 中 k2 个点 2k+1个点 连线,k1+k2=k,且 1≤k1,k2≤k-1.否则若 k2=0,则 A∪{b}中各点均未连线, a b B∪{a,c}中各点也未连线.矛盾.故 k1,k2≥1.且由于 n>6,即 k1,k2 中至少 图3 有一个≥2,不妨设 k1≥2,现任取 B 中与 c 连线的一点 b1,由于 b1 与 B 中其余 各点均未连线,若 b1 与 A 中的所有与 c 连线的点均未连线,则 b1 连线数≤2+k-1-k1≤k-1,矛盾,故 b1 至少与此 k1 个点中的一点连线.故证. 例 11.若任意 133 个正整数中,至少有 799 对数互素,证明:其中必存在 4 个正整数 a、b、c、d,使 得 a 与 b,b 与 c,c 与 d,d 与 a 互素. 证明:用 133 个点表示这 133 个数,若某两个数互素,就在表示这两个数的点间连一条线段.设从点

Ai 出发的线段有 di 条,则

i=1

∑ di≥2?799.
133

133

若两个点 A、B 都与点 C 连了线,就称 A、B 是属于 C 的点对.于是分别属于 Ai(i=1,2,?,133)的 ( ∑ d )2 133 133 133 1 133 1 133 2 1 i=1 i 1 133 2 点对的总和为 M= ∑ Cdi= ∑ di(di-1)= ∑ (d i -di)≥ [ - ∑ di]= ( ∑ di)( ∑ di-133) 2i=1 2i=1 2 133 2?133 i=1 i=1 i=1 i=1 ≥ 1 1 12?11?133 2 ?2?799?(2?799-133)> ?2?6?133(2?6?133-133)= =C133. 2 2?133 2?133

2 2 但这 133 个点间每两点都连线时,点对数为 C133.而 M>C133,说明上面的计数中有重复计数.即存在

点 A、C,它们既是属于 B 的点对,又是属于 D 的点对,即 A,B;B,C;C,D;D,A 都连了线.故证. 又解:画一个 133×133 表格,把这 133 个数记为 A1,A2,?,An,若 Ai 与 Aj 互素,则将表格中第 i 行 j 列的方格中心涂红.于是当 d(Ai)=m 时,则表格中的 i 行及 i 列各有 m 个红点.且表格的主对角线上的 方格中心都没有涂红,所以,表中共有 2×799 个红点. 若存在满足题中条件的四个数,则表格中存在一个边平行于格线的矩形,其四个顶点都为红点.同行
2 的两个红点组成一个红点对,于是表中红点对数为 ∑ Cdi.若有不同两行的各一个红点对处于同一位置,则 i=1 133

表格中存在四个顶点都为红点且边平行于格线的矩形.
2 反设表格中任何四个红点其中心都不是一个边平行于格线的矩形顶点.则表格中红点对数≤C133.但由 2 2 上证知 ∑ Cdi>C133.故证. i=1 133

-5-

练习题答案
1.平面上给定 7 个点,用一些线段连接它们,每三个点中至少有两点相连,问至少要有多少条线段?试给出一个图. 解:7 个点中共有三点组 C7=35 个.每条线段共与其余 5 点组成 5 个三角形.故线段条数≥ 如果有一个点没有连线,则其余 6 点两两都必须连线,要 C6=15 条. 如果有一点只连了一条线,其余 5 点必须两两连线,连线数>C5+1=11 条. 设某点只连了 2 条线,如 AB、AC 连了 2 条线,则其余 4 点均未与 A 连线,于是它们必须两两互连, 应连 C4=6 条.此时,取 B、C 两点及其余 4 点中的任一点,尚不满足条件,故 BC 应连线,此时连了 9 条线满足题目要求. 若每点都至少连出 3 条线,则总度数≥21,即至少连了[ ∴ 至少连 9 条线. 2.20 名选手参加 14 场单打比赛,每名选手都至少参加过 1 场.证明:必有某 6 场比赛的参赛者是 12 名不同的选手. 解:用 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 个顶点. 3. 3n+1 人, 有 每两人之间下象棋、 围棋、 跳棋中的一种. 已知每个人都与 n 个人下象棋, 个人下围棋, 个人下跳棋. n n 证 明:其中必有 3 人,两人下象棋,两人下围棋,两人下跳棋. 解:即一个三色的 K3n+1,每点都连出 n 条红线,n 条蓝线及 n 条黄线.其中一定有一个三角形,三边不同色. 由一个顶点出发的两条线组成的角如果边的颜色不同,则称为异色角.一个三角形如果三边不同色,则其三个角都是异 色角,称为异色三角形. 每个顶点处的异色角都有 3n2 个,从而这个 K3n+1 中的异色角共有 3n2(3n+1)个. 1 1 3 由这些线段组成的三角形共有 C3n+1= (3n+1)?3n(3n-1)= n(3n+1)(3n-1)个. 6 2 ∴ 由抽屉原理知,[ 3n ]+1=3,即至少存在一个三角形,有 3 个异色角,即为异色三角形. 1 (3n-1) 2 21 ]+1=11 条线. 2
2 2 2 3

35 =7 条. 5
B

A

C

4.九名数学家出席一次国际会议,其中任意 3 人中至少有 2 人能讲同一种语言.如果每位数学家至多能讲 3 种语言.证 明:至少有 3 位数学家能用同一种语言交谈. 证明: 9 个点表示这 9 个人, 用 任二人如能用第 r 种语言交谈, 则在表示此二人的点间连一条线并涂上第 r 种颜色, 于是, 本题即是证明,存在一个同色的三角形. 首先,若 v1 与 v2 间连了第 k 种颜色线,v1 与 v3 间也连了第 k 种颜色线,则 v2 与 v3 间也要连第 k 种颜色线.此时即出现同 色的三角形.所以只要证明从其中某一点出发的线中必有两条线的颜色相同. 反设从任一点出发的线中没有同色的线,由于每个人至多会用三种语言.即 degvi≤3,于是 v1 至少与 5 个点不邻接,设 为 v2、?、v6,同样,v2 至少与 5 个点不相邻接,于是 v3、?、v6 中至少有一点与 v2 不相邻.设为 v3,于是 v1、v2、v3 不相 邻接.与已知矛盾.故证. 又证:若每点的度均≤3,于是,必有两点未连线,设 v1、v2 未连线,则其余各点均必须与这 2 点之一连线,否则若 v3 与 v1、v2 均未连线,则 v1、v2、v3 两两均未连线,矛盾,于是 v1、v2 与其余 7 点至少连了 7 条线,与 degv1+degv2≤6 矛盾. 所以,必存在某点的度≥4.由于这一点出发的线只有 3 种颜色,故必有 2 线同色,可证. 5.证明:任意的 9 个人中,必有 3 个人互相认识或 4 个人互相不认识. 证明:⑴ 如果存在一个顶点,从这点出发的 8 条线中,有至少 4 条为红色,设从 v1 引出的 4 条线为红色,引到 v2,v3, v4,v5.若此 4 点中的某 2 点间连了红色线,则存在红色 K3,若此 4 点间均连蓝线,则存在蓝色 K4. -6-

⑵ 如果从任一点出发的 8 条线中,红色线都少于 4 条.于是从每点出发的蓝色线都多于 4 条,即至少 5 条.但由于任何 图中的奇顶点个数为偶数,故不可能这 9 个顶点都引出 5 条蓝线.于是至少有一个顶点引出的蓝线≥6 条,例如从 v1 到 v2, v3,?,v7 都引蓝线,则在 v2,v3,?,v7 这 6 个点的图中,必存在红色三角形或蓝色三角形,于是 G 中必有红色 K3,或蓝 色 K4. 6.⑴ 在一所房子里有 10 个人,其中任意 3 人中至少有 2 人互相认识,证明:其中有 4 人,他们任意 2 人都互相认识. ⑵ 如果把⑴中的数 10 改为 9,结论仍成立否? 解:用 10 个点表示这 10 个人,如果某 2 人互相认识,则在表示这两人的点间连 1 条线. 即任 3 点都至少连了 1 条线,要求证明存在一个 K4. 设不存在 K4,即任意 4 点中总有 2 点没有连线, ① 设某一点 A 与 4 点都没有连线,则由假设此 4 点中有 2 点未连线,则此 2 点与 A 共 3 点 均未连线,与题设矛盾.故 A 至多与 3 点未连线,即至少与 6 点连了线. ② 设 A 与 A1、A2、?,A6 连线,则 A1,?,A6 中任意 3 点必有 2 点未连线,否则存在 K4, ③ 设 A1 与 Bi、Bj、Bk 都未连线,则 Bi、Bj、Bk 间若有两点未连线,则出现 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 的点. 7.⑴ 试说明,存在无 3 点共线的 6 个点,它们之间连了 12 条线段,但其中没有 K4. ⑵ 试证明:无 3 点共线的 6 个点之间连了 13 条线段,其中必有 4 个 K4. 解:把 6 个点平均分成 3 组,每组 2 个点,规定同组的点不连线,不同组的点都连线,则共连 C6-3=12 条线段,但任 取其中 4 点,必有 2 点同组,这 2 点间没有连线段,故不存在 K4. ⑵ K6 共有 15 条边,现去掉 2 条边后即有 13 条边,分两种情 形: ① 去掉的两边有一个公共端点,如图设 v1v2,v2v3 没有连线, 则去掉其公共端点 v2, 在其余 5 点中任取 4 点均为 K4, 即有 4 个 K4; ② 去掉的两边没有公共端点, 如图 v1v2, 3v4 没有连线, v1、 v 在 v2 中任取 1 点,v3、v4 中任取 1 点,再取 v5、v6 这两点,则所得 4 点 即为 K4,共有 4 种取法,即共有 4 个 K4. 8.某镇有居民 1000 人,每人每天把昨天听到的消息告诉自己认识的人,已知任何消息只要镇上有人知道,都会经过这 样的方式逐渐地为全镇的人所知道.证明可以选出 90 名代表,使得同时向他们报告一个消息,经过 10 天,这一消息就为全 镇的人知道. 证明 用 1000 个点代表 1000 个居民, 两名居民相识, 则在两点之间连一线, 如此可得一图, 依条件, 这个图是连通图. 若 图中有圈,则我们去掉圈中的一边使圈被破坏而不影响图的连通性,经过有限次这种手续,可得树 T1000. 在 T1000 中取一条主干 v1v2…vn,取 v11 作为 1 个代表,并把边 v11v12 去掉,则此图分成了 2 个连通分支,在含有 v1 的一棵 树中,每点到 v11 的道路的长度都不超过 10,否则 v1v2…vn 在 T1000 中不是主干,这是不可能的,故 v11 知道的消息在 10 天后 整个树的点集所代表的居民全都知道;余下另一分支再取其主干,又按此法得出第二个代表 v22,依此类推,则 T1000 分割成若 干棵树: 同样, 在含 v22,33, v …的树中,22,33, v v …知道的消息在 10 天后整个树的点集代表的居民全都知道; 由于 1000=11× 90+10, 故这样分法,至多分出 89 棵树,余下至多 21 个点的链长≤20,取此链的中心,则此中心的离径≤10.现在取 v11,v22,v33,… 为代表,只要将消息告诉这些代表,则在 10 天之后,这些树的点集所表示的居民全都知道这个消息;最后一棵树取其中心为 代表,该中心到树中其他各点的距离不超过 10,取这个中心所表示的居民作为第 90 名代表,则问题已获解决. 9.求满足下列条件的最小正整数 n:在圆周上任取 n 个点 A1、A2、?、An,则在 Cn个角∠AiOAj(1≤i<j≤n)中,至少有 2007 个不超过 120° . 解:对于这 n 个点,设使∠AiOAj>120° (1≤i<j≤n)的角共有 Sn 个,则有 Cn-Sn 个角不超过 120° .现求 Sn 的最大值. -72 2 2

A6 A A5 A4 A1 A3 A2

1

6

1

6

2

5

2

5

3

4

3

4

规定:当且仅当∠AiOAj>120° 时,在 Ai 与 Aj 间连一线段.于是共连出了 Sn 条线段. 对于这 n 个点中的任意 3 点 Ai、Aj、Ak(1≤i<j<k≤n),如果已在这三点间连了 2 条线段,例如 AiAj、AjAk 连了线段,则 Ai 与 Ak 必不连线.这是因为∠AiOAj>120° ,∠AjOAk>120° ,则必有∠AiOAk<120° .这说明这 Sn 条连出的线段中没有连出三 角形. 由于在 n 个点中,至多可以连[ n2 n2 ]条线段而没有连出三角形.于是,Sn≤[ 4 ]. 4 于是,解 Cn-[
2

n2 ]≥2007. 4

若 n=2m,则得 m(2m-1)-m2≥2007?m≥46?n≥92; 若 n=2m+1,则得(2m+1)(m+1)-m(m+1)≥2007?m≥45?n≥91. 经验证 91 满足要求:把圆周 6 等分,在相对的两个等分中放入 91 个点,其中一个等分放入 45 个点,另一个等分中放 入 46 个点,在同一等分中的两个点所对应的角<120° ,不同等分中的两个点所对应的角>120° ,即有 C45+C46=2025 个角不 超过 120° .而 90 个点中至多有 2C45=1980 个角不超过 120° . 故所求 n 的最小值为 91. 10.某次体育比赛,每两名选手赛一场,无平局.通过比赛确定优秀选手.设 A 为选手,如果对其他任意选手 B,要么 A 胜 B,要么存在选手 C,使得 A 胜 C,C 胜 B,则 A 即是优秀选手.证明:如果按上述规则选出的优秀选手只有 1 名,则这 名选手胜其他所有的选手. 证明:取 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 全胜. 11.凸 n 边形及其 n-3 条在形内不相交的对角线组成的图形称为一个剖分图.证明:当且仅当 n 是 3 的倍数时,存在一 个剖分图是一个可以一笔画的圈. 解:显然 n=6 时存在满足要求的剖分图,设凸 3k 边形存在满足要求的剖分图,对于凸 3k+3 边形,可先擦去相邻 3 点 A2、A3、A4,把余下 3k 点组成凸 3k 边形的剖分图画出(从点 A1 出发 并回到 A1),再把去掉三点补回,并连 A1A3,A3A5,即得到 3k+3 边形的剖分图.满足要求.即当 n 是 3 的倍数时存在满足要求的剖分图. 再证明:当存在剖分时,3|n.由于是一笔画的圈,故每个顶点都是偶数度.于是从每个顶 点引出的对角线都有偶数条.这样就可以把每个分成的三角形染色,使相邻的三角形不同色.这 时,由于每个顶点处分成的三角形都有奇数个从而位于两边的三角形同色,设同红.即只要有原 来的凸 n 边形边的三角形都是红色.而每条对角线两边都是异色. 统计红色三角形的边,若红色三角形共有 k 个,红边共有 3k 条,其中凸 n 边形的边有 n 条,对角线有 n-3 条,则 n+n -3=3k. ∴ 3|n.
A5 A3 A4 A3 +3
k

2

2

2

A1 A2

12.已知 n(n≥6 的偶数)人中任何 3 人之间至少有两人互通电话,且每人至多与?

?

n-2? 个人互通了电话,证明:这 n 个 2 ?

人总可以分成不相交的两组,使同一组内任何两人互通了电话. 解:用 n 个点表示这 n 个人,若两人通电话,则在表示这两人的点间连 1 条线.题目就是:任意 3 点中至少连了 1 条线, 每个点至多连?

?

n-1? 条线.则可以把这些点分成两个不相交的子集,同集中任意两点都连了线. 2 ?

任取没有连线的两点 A1 与 B1,则与 A1 没有连线点的至少有 n-1-?

?

n-1? n = 个.设 A1 与 B1,B2,?,B 没有连线, 2 ? 2 []

[]

n 2

同时可设 B1 与 A1,A2,?,A 没有连线.令 S1={A1,A2,?,A },S2={B1,B2,?,B }.
[]
n 2

[]

n 2

[]

n 2

1? 若 S1∩S2≠?,取 C∈S1∩S2,则(A1,B1,C)都没有连线,与“已知任何 3 人中至少有两人通了电话”矛盾,故 S1 ∩S2=?. -8-

2? 取三点组(A1,Bi,Bj)(1≤i<j≤

[n]),则只能 B 与 B 连线,即 S 中任何两点都连了线.同样,S 中任何两点都连了线. 2
i j 2 1

当 n=2k(k∈N*)时,S1∪S2=S,结论成立. 13.给定平面上无三点共线的 n 个点,以这 n 个点为两个端点连出了 m 条线段,已知对于其中任意的两点 A、B,都有 一个点 C,使 C 与 A、B 都连有线段.求 m 的最小值. 解:若某点只连了 1 条线段,例如点 A1 只连了 1 条线段 A1A2,取 A1,A2 两点时,没有第三点与它们都连线段.故每点 至少连了 2 条线段. 如果某点恰连了 2 条线段,如 A1 只与 A2、A3 连线,对于 A1、A2,则必须连 A2A3,成一个三角形.对于点 Ai(4≤i≤n), 考虑点对 A1、Ai,必有一点与此两点都连了线,于是 Ai 必与 A2、A3 之一连了线.但 Ai 至少连 2 条线,故从 A4,A5,?,An 出发的线至少有 2(n-3)条,且其中至少有 n-3 条向 A2、A3 引出.当 n 为奇数时,除与 A2、A3 连的线外,其余 n-3 条线至 1 1 1 多重复 2 次(在 Ai 与 Aj 之间连的线 4≤i<j≤n),故连的线的条数 m≥3+(n-3)+ (n-3)= (3n-3)=[ (3n-2)];当 n 为偶数 2 2 2 1 时,其余 n-4 条线至多重复 2 次.故连的线的条数 m≥3+(n-3)+ (n 2
A2
k

1 1 -4)+1= (3n-2)=[ (3n-2)]. 2 2 3 如果每个点连线数都不少于 3 条,则连线数≥ n. 2 1 总之,连线数 m≥[ (3n-2)]. 2 又, n=2k+1(k∈N*)时, A2h-1A2h(h=1, ?, 及连 AiA2k 当 连 2, k),
+1

A2 -1
k

A2 -1 A2
k

k

-2

A2 +1
k

A2

k

A4 A1 A2 A3 A1 A2 A3
n=2k

A4

n=2k+1

1 (i=1,2,?,n),共连了 3k= (3n-3)条线,满足题意;当 n=2k(k 2

1 ∈N*)时,连 A2h-1A2h(h=1,2,?,k-1),及 A2An-1,AiAn(i=1,2,?,n-1),共 (3n-2)条线满足题意. 2 14. 平面内是否存在一个含 n(n≥8)个点的图, 在这 n 个点间连有一些线段, 使得从 n 个点出发的线段数分别为 4, 6, 5, ?, n-5,n-4,n-3,n-2,n-2,n-2,n-1,n-1,n-1? 解:n=8 时,如图可画出八边形,其中 V1 连 4 条线,V2 连 5 条线,V3、V4、V5 连出 6 条边, V6、V7、V8 连出 7 条边. n=9 时在上图的基础上增加一个顶点 V9,它与 V3,V4、V5、V6、V7、V8、V9 各连 1 条边,则 得到连线数分别为 4,5,6,7,7,7,8,8,8 的九边形. 当 n>9 时,设存在这样的 n 边形 V1V2V3?Vn,从其各顶点出发的线段数分别为 4,5,6,?, n-5,n-4,n-3,n-2,n-2,n-2,n-1,n-1,n-1,去掉 Vn、Vn-1、Vn-2 三点及所连线段, 则余下 n-3 个点,分别连了 1,2,3,?,n-6,n-5,n-5,n-5 条线段.取 M1={V1,V2, V3};M2={V4,?,Vn-6};M3={Vn-5,Vn-4,Vn-3}.由 n>9,故 M2≠?. 由于 M3 中的点连线数为 n-5,故它们每点仅与 1 点未连线,若 M3 中点都没有与 V1 连线, 则它们都要与 V2 连线,与 V2 连 2 条线矛盾.故 V1 与 M3 中某 1 点连线,设 V1 与 Vn-3 连线,则 V2 与 Vn-4、Vn-5 连线(因此二点只与一点未连线).V3 与 Vn-5、Vn-4、Vn-3 均连线,于是 V3 与 M2 中的 点均未连线,此时 Vn-6 至多连了 n-3-1-3=n-7 条线,与 Vn-6 连 n-6 条线矛盾.故 n>9 时这 样的图不存在. 15.某团体中任意两个认识的人都没有共同的熟人,而任意两个不认识的人都恰有两个彼 此共同的熟人.证明:该团体中每个人认识的人数都相同. 解:以 n 个点表示该团体中的人,两人认识,则在表示两人的点间连一条线,问题是:若 两点连了线,则它们不能与同一第三点连线,即不出现三角形,若两点间未连线,则它们恰与 另两个点都连了线. 首先证明任意两个连线的点的次数相同.设 AB 连线,则它们除彼此外没有连向同一点,设 -9A B Ak A1 B1 Bk

V3

V2 V1 V8

V4 V5 V7

V6

V3 V4 V5 V6

V2

V1 V9 V8 V7

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|.于是得证. 又证:用 n 个点表示这 n 个人,如果其中某两个人互相认识,则在表示这两个人的点间连一条线, ,这样就得到了一个图 G. 设其中一人 v1 有 k 个熟人,v2,v3,?,vk+1 为其熟人,而与 vk+2,vk+3,?,vn 这 n-k-1 个人不认识. 由已知,v2,v3,?,vk+1 这 k 个点两两不相邻.此时可知: ⑴ G 中没有三角形(因如有三角形时,则两个相邻的点都与第三点相邻,与题设矛盾) ⑵ 若两点不相邻,则它们都与某两个点相邻,即出现一个四边形且无对角线的圈. 现 v1 与 vk+2 不相邻, 则存在一个以 v1 及 vk+2 为相对顶点的四边形圈. 此四边形的另两个顶点与 v1 都相邻, 故必在 v2,3, v …, vk+1 中.不妨设为 v2 与 v3.(因 v1 与 vk+2,vk+3,…,vn 这 n-k-1 个点不相邻) 再考虑 v1 与 vk+3,也存在一个以 v1 及 vk+3 为相对顶点的四边形圈,同理,此四边形的另两个顶点也必在 v2,v3,…,vk+1 中.但不能是 v2 与 v3.否则 v2,v3 有至少 3 个共同的熟人 v1,vk+2,vk+3. 这说明与 v1 不相邻的顶点至多有 Ck个,即 n-k-1≤Ck=
2 2

k(k-1) . 2

⑶ 又因 v2,v3 不相邻,他们有一个共同的熟人 v1,另一个共同的熟人不能在 v2,v3,?,vk+1 中,只能在 vk+2,vk+3,?, vn 这 n-k-1 个人中.而 v2,v3,?,vk+1 中的不同的二人组,除 v1 外的另外一个熟人也不同.即二人组数应不超过 n-k-1, 即 n-k-1≥Ck=
2

k(k-1) k(k-1) 2 .于是 n-k-1=Ck= . 2 2

∴ k2+k-2(n-1)=0. 此方程至多只有一个正整数根.而对每个顶点此方程均成立. 即:每个参加者都有同样多的熟人. ⑷△=1+8(n-1)=8n-7 为完全平方数时本题才有解.

- 10 -


相关文章:
图论问题选讲答案
图论问题选讲答案_学科竞赛_高中教育_教育专区。数学竞赛辅导讲义,有答案图论问题讲义答案 例 1.空间 6 点,无 3 点共线,每两点连 1 条线,染红或蓝. ⑴ 求...
图论问题选讲
图论问题选讲_数学_自然科学_专业资料。图重要的概念与定理 论 大连市第二十四...或者是两位同胞编号之和. 6 练习题答案 1.证:用 6 个点表示 6 个人,再用...
离散数学及其应用图论部分课后习题答案
离散数学及其应用图论部分课后习题答案_理学_高等教育_教育专区。离散数学及其应用图论部分课后习题答案作业答案:图论部分 P165:习题九 1、 给定下面 4 个图(前两个...
图论习题及答案
图论习题及答案_高等教育_教育专区。作业解答练习题 ...(w,capacity) %一维装箱问题的FFD(降序首次适应)...(next,current)=inf; %表示这条边已经选掉了 ...
张清华 图论课后题答案
张清华 图论课后题答案_理学_高等教育_教育专区。很完整的课后图论答案 ...(32+36+8)/2=38,3n-6=45-6=39 没做出来感觉题有问题 6.15 v2 v1 v3...
图论及其应用1-3章习题答案(电子科大)
图论及其应用1-3章习题答案(电子科大)_计算机软件及应用_IT/计算机_专业资料。...橱柜行业多“猫腻” 选品牌重沟通 儿童房卧室门窗选择 大有讲究20080份文档 权威...
组合数学与图论复习题及参考答案
组合数学与图论复习题及参考答案_工学_高等教育_教育专区。西南交大 研究生 组合...从 10 人中随意选一个人 p,F 表示与 p 相识的人,S 表示与 p 不相识的...
电子科技大学研究生试题《图论及其应用》(参考答案)
电子科技大学研究生试题《图论及其应用》(参考答案) 考试时间:120 分钟 一.填空题(每题 3 分,共 18 分) 1.4 个顶点的不同构的简单图共有__11___个; 2...
图论及其应用1-3章习题答案(电子科大) (1)
图论及其应用1-3章习题答案(电子科大) (1)_理学_高等教育_教育专区。学号:201321010808...2014年统计法基础知识精讲88份文档 2014全国高考状元联手分享状元笔记 ...
图论A有答案
xxxx 2014 - 2015 学年度第一学期试卷学四 A (闭卷 ) ( ) 课程题号 得分 得分 阅卷人 图论一 院系二 三 专业 年级、班级 11(1、2、3、4) 总分 ...
更多相关标签:
数学分析选讲答案 | 中华文化选讲答案 | 中华文化选讲幕课答案 | 数学分析选讲课后答案 | 高代选讲试卷及答案 | 中国文化选讲答案 | 图论与网络流理论答案 | 图论与代数结构答案 |