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

图论选讲








图 论 选 讲
基本概念:点、线、简单图、连通、圈、树、点的度、完全图、 Euler 圈、 Hamilton 圈、偶图、平面图、色数。 性质 1:一个图每个点度之和为偶数。 证明:

? deg(v) ? 2 E 。
v?G

性质 2:树 T

中至少有两个点的度为 1 ;树 T 有 n 个顶点,则 T 中恰好有 n ? 1 条边。 证明:取最长的链 v1v2 ...vk ,则 deg(v1 ) ? deg(vk ) ? 1 。

n ? 2 时, 只有 1 条边。 假设 n ? k 时成立, 对于 n ? k ? 1 , 去掉 G 的度为 1 的一个点 v , 则得到一个新的树,点数边数都减少了 1 ,由归纳假设结论成立。
性质 3:一个图 G 有 n 个点,边数不小于 n ,则 G 中有圈。 证明:设 G 有 k 个连通分支 G1 , G2 ,..., Gk ,则必有一个连通分支(不妨设为 G1 )边数 不少于点数。由性质 2 可知 G1 不是树,因此 G1 有圈。

性质 4:红、蓝两种颜色对 K 6 的连线进行涂色,则至少有 1 个同色三角形。 证明:任取一点 v1 ,由抽屉原理 v1 连出的五条边中至少三条同色,不妨设 v1 与 v2 , v3 , v4 连红色边,若图中无红色三角形,则 v2 , v3 , v4 之间只能两两连蓝边,因此 ?v2 v3v4 为蓝色三 角形。

性质 5: 用红、 蓝两种颜色对 K5 的所有连线进行涂色, 如果其中没有同色三角形, 则 K5 中有长度为 5 的红、蓝色圈各一个。 证明:由性质 4 的证明过程可知, K5 的每个点只能连出两条红边、两条蓝边。考虑红 边构成的子图,每个点的度都是 2 ,因此是由若干个圈组成,由于不存在长为 1, 2 的圈(简 单图) ,因此只能是一个长为 5 的圈。 同理,蓝边组成的子图也是一个长为 5 的圈。















例 1:用红、蓝两种颜色对 K10 的所有连线进行涂色,则其中必有两个没有公共点的长度为 奇数的同色圈,两个圈也同色。 (1990IMO 预选) 证明:任取六个点,由性质 4 其中有一个同色三角形; 剩下的点中取六个点, 由性质 4 其中有一个同色三角形, 若两个三角形同色,则结论成立。 不妨设两个三角形不同色, 这两个三角形的顶点之 间有 9 条边,其中必有 5 条边同色,不妨设为蓝色,则 红三角形的三个顶点中必有一个点向蓝色三角形连出 两条蓝边,因此有五个点中有红色和蓝色两个三角形。 由性质 5,剩下的五个点中要么有同色三角形,要 么有两个长度为 5 的红圈和蓝。 综上所述,结论成立。

例 2:求最小的正整数 n ,使得任选 K9 的 n 条边进行红、蓝染色,必有一个同色三角形。 (1992IMO)
A1

证明:我们在左图 K5 的基础上构造我们的例 子,很明显此 K5 中没有同色三角形。

A8,A9

A2,A3

将 9 个 点 A1 , A2 ,..., A9 分 为 5 个 组 :

? A1? , ? A2 , A3? , ? A4 , A5 ? , ? A6 , A7 ? , ? A8 , A9 ?



同组的不相连,将相邻组的点用红边相连,不 相邻的组用蓝边相连。
A6,A7 A4,A5
2 图中连有 C9 ? 4 ? 32 条边。在其中任选

三个点,如果有两点同组,则不构成三角形;若属于三个不同的组,则由于 K5 中没有同色 三角形,因此这三个点不构成同色三角形,因此 n ? 33 。 若对 33 条边进行了染色,则只有 3 条边没有染色。取三条没染色边各一个顶点 A, B, C (可能有相同的) ,则连接此三点之外的任意两点的边都被染了色,因此其余的点构成一个 红、蓝染色的完全图,其中必含有一个完整的红、蓝染色的 K 6 ,因此存在同色三角形。 综上所述, n ? 33 为所求最小值。










同色四边形。 (国家队选拔赛)





例 3:求最小的正整数 n ,使得任选 K10 的 n 条边进行红、蓝染色,必有一个同色三角形或 证明:左图共有 30 条边被红、蓝染色,此图由大小两个

K5 ,以及相互之间连接的 10 条边组成。图中没有同色
三角形或同色四边形,因此 n ? 31 。 若有 31 条边被染色,则必有 16 条边同色,以下我 们来证明:在 10 个点中,任意连接 16 条边,必有三角 形或四边形。

10 个点 16 条边 32 个端点, 必有一点 A 的度 k ? 4 ,
假设与 A 相连的点为 B1 , B2 ,..., Bk ,若另外的 9 ? k 个点 中有点 C 连接两个 Bi , B j ,则 A, Bi , B j , C 构成四边形;若 9 ? k 个点中每个点最多连接一个

Bi ,则这 9 ? k ? 5 个点的子图至少有 16 ? k ? (9 ? k ) ? 7 条边,必有一个圈,若圈长为 3, 4
则形成三角形和四边形,若圈长为 5 ,另外连接一边必然产生三角形,证毕。 综上所述, n ? 31 为所求最小值。

例 4:有 10 个不同的实数 x1 , x2 ,..., x10 ,对于其中任意两个数 xi , x j , xi ? x j 与 xi x j 中至少
2 2 有一个是有理数。证明: x12 , x2 都是有理数。 (2005 俄罗斯) ,..., x10

证明:将如果 xi ? x j 是有理数,则用红线连接 xi x j ,否则用蓝线连接 xi x j 。由图论知识易 知 x1 , x2 ,..., x6 这六个点中必有三个点构成一个同色三角形,不失一般性设 x1 x2 x3 是同色的。 ㈠ 若 ?x1 x2 x3 是 红 色 三 角 形 , 则 x1 ? x2 , x1 ? x3 , x3 ? x2 都 是 有 理 数 , 因 此

x1 ? x2 ? x3 ?

( x1 ? x2 ) ? ( x1 ? x3 ) ? ( x3 ? x2 ) 是有理数,因此 x1 ? ( x1 ? x2 ? x3 ) ? ( x2 ? x3 ) 2

也是有理数,同理 x2 , x3 也都是有理数,不妨设 x1 ? 0 。 对于任意 i ? 1 ,若 x1 ? xi 是有理数,则 xi ? ( x1 ? xi ) ? x1 是有理数;若 x1 xi 是有理数, 则 xi ?

x1 xi 也是有理数。因此,所有的数都是有理数,命题成立。 x1










2 2




2

㈡若 ?x1 x2 x3 是蓝色三角形,则 x1 x2 , x1 x3 , x3 x2 都是有理数,因此它们的乘积 ? x1 x2 x3 ? 是有

?xx x ? ?xx x ? ?xx x ? 2 2 理数,故 x ? ? 1 2 3 ? , x2 ? ? 1 2 3 ? , x3 ? ? 1 2 3 ? 都是有理数。 ? x2 x1 ? ? x2 x3 ? ? x1 x3 ?
2 1

2

? xi x j 对于任意 i ? 3 ,若 xi x j ,1 ? j ? 3 是有理数,则 xi2 ? ? ? x ? j

? 也是有理数;不妨设 ? ? ?

2

2 xi ? x1 , xi ? x2 , xi ? x3 都是有理数,则 x2 ? x1 也是有理数,由于 x2 ? x12 是有理数,因此

x2 ? x1 ?

2 ? x12 x2 也是有理数。但是 x1 x2 是蓝线,矛盾。 x2 ? x1

2 2 都是有理数。 综上所述, x12 , x2 ,..., x10

例 5:V 是图 G 的所有顶点,对于任意 D ? V ,如果每个 x ?V \ D 都至少与 D 中一个点相 邻,我们称 D 是一个 G 的中心,证明: G 恰好有奇数个中心。 证明:若 x, y 两点相邻我们记作 x ? y ,若 x, y 不相邻我们记作 x ? ? y ,特别的我们也记

x ? x。 对于 V 的任意子集 S , 如果一个 t ?V 与 S 中每个数都不相邻, 则称 t 是 S 的敌人,
记 E ( S ) 为 S 的全部敌人。显然,当且仅当 E ( S ) ? ? 时, S 是一个中心。 令 F ? ( A, B ) A, B ? V , ?x ? A, ?y ? B, x ? ? y ,由于 ( A, B ) ? F ? ( B, A) ? F , 并且 ( A, A) ? F ? A ? ? ,所以 F 为奇数。 另一方面我们只考虑二元组的第一项,对于任意 A ? V , ( A, B ) ? F ? B ? E ( A) , 因此恰好有 2
E ( A)

?

?

个 B ? V ,使得 ( A, B ) ? F ,故 F ?
E ( A)

A?V

?2

E ( A)



当且仅当 A 是一个好集时, E ( A) ? ? , 2

? 1 是一个奇数,假设有 g 个中心,则

F ? g (mod 2) ,因此 g 是奇数。

例 6: T 由若干个大于 1 的整数组成, S 是 T 的一个子集,并且对于任意 t ? T 都存在一个

s ? S 使得 ( s, t ) ? 1 ,称 S 是一个好集。证明:共有奇数个好集。 (2010 美国选拔赛)
证明:若 ( s, t ) ? 1 ,则连接 s, t ,得到一个图 G ,好集也即上题的中心。















例 7:有一次聚会的任意 4 人中,都可以找出 3 人,两两都是朋友(朋友关系是相互的) ;或 者可以找出 3 人,两两都不是朋友。证明:可以将这些人分为两组,使得第一组的人两两都 是朋友,第二组的两两都不是朋友。 (克罗地亚 2011) 证明:将每人看成一个点,若相互是朋友则用红线连接两点,否则用蓝线连接两点,得到一 个图 G 。由已知每四个点中都有一个红色三角形,或一个蓝色三角形。 我们取图中最大的红色完全图 R , 如果 R ? 2 , 则 G 本身是蓝色完全图, 以下设 R ? 2 如果 G \ R 恰好是蓝色完全图,则命题已经成立。不妨设存在 v1 , v2 ? G \ R ,使得 v1v2 是红 线,由 R 的最大性, v1 必与一个 u1 ? R 相互连蓝线。

u1 v1 u1 v1

u v2

若 u1v2 也是蓝线,任取 R 中一个 u ? u1 , v1 , v2 , u1 , u 中的同色三角形 只能是红色三角形 uv1v2 。也即 uv1 , uv2 都是红线,此时 R ? ?v1 , v2 ? \ ?u1? 构成更大的红色完全图,矛盾。

u v2

若 u1v2 也是红线,任取 R 中一个 u ? u1 , v1 , v2 , u1 , u 中的同色三角形 只能是红色三角形 uv1v2 或者 u1uv2 。无论哪种情况 v2u 都是红线,因此

R ? ?v2 ? 构成更大的红色完全图,矛盾。

所以 G \ R 恰好是蓝色完全图,因此结论成立。

例 8:一个连通图 G 中有一个点 v0 的度为 2010 ,其余的每个点的度都小于 2010 ,并且如 果有两个点的度相同, 则这两个点的度都是偶数。 求最大的 k , 使得总能去掉与 v0 的 k 条边, 使得剩下的图仍然是连通图。 (土耳其 2010) 解:由于小于 2010 的奇数有 1005 个,而奇点个数是偶数,因此 G 中最多有 1004 个奇点。 假设去掉 v0 以后, G 有 m 个连通分支 G1 , G2 ,..., Gm 。对于每个 1 ? i ? m ,假设 v0 与 Gi 中 的 deg Gi (v0 ) 个点相连,则

? deg
i ?1

m

Gi

(v0 ) ? 2010 (*),对于每个 Gi ,可以去掉 v0 与它们相连

的 deg Gi (v0 ) ? 1 条边,使得连通性仍然得以保持,因此 kmax ? 2010 ? m 。 假设 m 个分支中有 a 个使得 deg Gi (v0 ) 为偶数, b 个使得 deg Gi (v0 ) 为奇数。由于

deg Gi (v0 ) 为奇数时, Gi 中至少还有一个点在 G 中是奇点,而 G 中最多有 1004 个奇点,因










此 b ? 1004 。由(*) 2010 ?




2010 ? b ? 1507 ,所 2

? deg
i ?1

m

Gi

(v0 ) ? 2a ? b ,因此 m ? a ? b ?

以 kmax ? 2010 ? m ? 503 ,因此总能去掉 v0 的 503 条边使得连通性得以保持。 去 掉 504 条 边 有 时 是 不 可 以 的 , 可 以 构 造 反 例 如 下 : 先 构 造 1004 个 完 全 图

K1 , K 3 ,..., K 2007 ,和 503 个 K 2 ;第二步将 v0 和 K1 , K 3 ,..., K 2007 的各一个点相连,再将 v0 和

503 个 K 2 的每个点相连。这样的图 1004 个奇点的度都不相同,并且 m ? 1507 。
因此, k ? 503 为所求最大值。

例 9:一个简单图 G 是连通的,已知去掉 G 中任意一个长度为奇数的圈的所有边, G 将不 再是连通图。证明: G 的色数 ? 4 。 (俄罗斯 2010) 证明:设 T 是 G 的一个生成树,则可以用 0,1 对 T 的每个顶点染色,使得相邻点不同色。 以 G 的点为顶点,G 中所有不属于 T 的边为边得到图 S 。由于从 G 中去掉所有 S 的边 以后图仍然连通,由已知 S 不含长为奇数的圈,也即 S 的圈都是偶圈,因此 S 是一个偶图 (二部图) ,所以可以用 0,1 两种颜色对 S 的每个顶点染色,使得相邻点不同色。 设 G 的点 v 在 T 的颜色是 x ,在 S 的颜色是 y ,则我们最终将 v 染成第 xy 色。对于
2

? ?

G 中任意相邻两点 u , v ,无论边 uv 是属于 T 或 S ,则 u , v 两点的颜色二进制至少有一位数
字不同,所以 u , v 不同色。所以, G 的色数 ? 4 。

例 10:一个图开始有 2000 个互不相连的点,甲乙两人轮流操作如下,由甲先开始,每人每 次可以连接两个还没有相连的点。如果去掉图中任何一个点后,剩下的图仍然是连通图,则 称此图为好图。 最先使得这个图变成好图的一方为输家, 谁有必胜策略? (2000 圣彼得堡) 解:我们来考虑这样一个“必败”的状态:任意添加一条边都会使得图变成好图。 此时假设去掉点 A ,图被分为两个互不相连的连通图 G1 , G2 ,由于任意添加一条边都 会变成好图,因此 G1 , G2 的点都和 A 相连,并且 G1 和 G2 都是完全图,设 G1 ? k ,则 W 共 有

k (k ? 1) (1999 ? k )(1998 ? k ) ? ? 1999 ? k (k ? 1999) ? 1999000 ? 0(mod 2) 条边。 2 2

而每次甲操作以后,图都有奇数条边,因此乙不可能面对必败的状态,所以无论如何操 作,乙都会获得胜利。















例 11:用黑、白两种颜色对有限图 G 顶点进行染色,开始时将全部点染黑,其后允许操作 如下:任意选定一点,将此点以及所有与它相邻的点变色。是否可以通过适当的操作将所有 点变白?(加拿大 2010) 我们来证明对于任意有 n 个点的图 G ,都可以将所有点变白。 证明: n ? 1 时,我们直接对这个点操作一次即可;假设对于某个 n ? 1结论成立,则当

G 有 n ? 1 个点时,假设这些点为 v1 , v2 ,..., vn ?1 ,由归纳假设对于任意 1 ? i ? n ? 1 ,可对
Gi ? G \ ?vi ? 进行一系列操作 Ti ,使得 Gi 的 n 个点全部变色,若此时 vi 也变色,则结论已
经成立,不妨设每个 Ti 都使得 vi 不变色,而 vi 以外的点都变色。 注意到对于任意 1 ? i ? j ? n ? 1 ,我们进行 Ti , T j 这组操作,可以使得 vi , v j 变色,其它 点都不变色。 因此当 n 是奇数,我们将 n ? 1 个点两两分组,然后将每组点变色即可;若 n ? 2k 是偶 数, 则 G 有奇数个点, 由于所有点的度之和为偶数, 所以必有一个点的度为偶数, 不妨设 vn ?1 的度是偶数,它与 A ? ?v1 , v2 ,..., v2t ? 相邻,与 B ? ?v2t ?1 , v2t ? 2 ,..., v2 k ? 不相邻。我们对 B 两 两分组,然后将每组点变色,然后对 vn ?1 操作一次,将 A ? ?vn ?1? 变色即可。 综上所述,对于所有的图 G ,我们都可以将所有的点变成白色。 例 12:开始时 1 到 2012 的每个数都被染成黑色,允许以下操作:任选一个数 n ,将与 n 不 互素的所有数(包括 n )变色。是否可以有限次操作后,将所有数变成白色?(俄罗斯) 例 13: V 是简单图 G (V , E ) 的顶点集合,每个点的度都是奇数。开始我们用红、蓝两种颜 色对所有 V 进行染色。 其后每一步操作如下: 如果第 k 步结束时, 与 v 相邻的点中红点更多, 则在第 k ? 1 步将 v 染成红色,否则将 v 染成蓝色(每一步所有的顶点同时操作) 。求证:在 2 有限步以后,操作会发生循环,并且循环节的长度不大于 。 证 明 : 可 以 将 第 k 步 染 色 看 成 f k : V ? ??1,1? , 其 中 1 代 表 红 色 , ?1 代 表 蓝 色 。 令

Sk ?

uv?E

??f

k

? ? ? ? (u ) f k ?1 (v) ? f k ?1 (u ) f k (v) ? ? ? ? ? f k (u ) ? f k ?1 (v) ? ? ? ? f k ?1 (u ) ? f k (v) , v?V ? u?N ( v ) v?V ? u?N ( v ) ? ?

则 ?S k ? S k ?1 ? S k ?

?? ?
v?V

?

? u?N ( v )

? f k (u ) ? ? f k ?1 (v) ? f k ?1 (v)? ? ?

由我们的染法规则,对于任意一个点 v ,都有 ?

? u?N ( v )

?

? f (u ) ? ? f k ?1 (v) ? f k ?1 (v)? ? 0 ,因 ?

此 S k 为不减的整数数列,由于 Sk ? 2 E 有界,因此在有限步以后, S k 会变成常数,此后 都有 f k ?1 (v) ? f k ?1 (v) ,因此操作会发生循环,并且循环节的长度不大于 2 。















定义:n, k ? 2 为正整数, 将 n 个点尽量等分为 k 组, 然后将不同组的每两个点相连得到的 k 部图记作 Tk , n 。 由于任意 k ? 1 个点中至少有两个点同组, 故 k 部图中均不含 K k ?1 , 以下我们用 e ? G ? 代 表 G 的边数。 定理( Turan ) :简单图 G 有 n 个点,若 G 中不含 K k ,则 e ? G ? ? e Tk ?1, n ,等号仅 当 G ? Tk ?1, n 时成立。

?

?

k ? 2 时, 命题显然成立; 假设对于所有小于 k 的正整数命题都成立, 设 G 中不含 K k , 证明:
假设在 G 中点 x 的度 ? 最大,记 X 为所有与 x 相连的点, Y 是其余的点。则有

e ? G ? ? e ? X ? ? e ?Y ? ? e ? X , Y ?
由于 G 中不含 K k ,故 X 中不含 K k ?1 ,由归纳假设 e ? X ? ? e Tk ? 2, ? 。由于 Y 中每个 点的度均 ? ? ,故 e ?Y ? ? e ? X , Y ? ? ? n ? ? ? ? ,当且仅当 Y 中每个点的度均为 ? 时成立。 在 Tk ? 2, ? 之外加上 ( n ? ? ) 个点,然后将这 ( n ? ? ) 个点与 Tk ? 2, ? 的点两两相连得到一个

?

?

k ? 1 部图 H ,故 e ? G ? ? e ? X ? ? e ?Y ? ? e ? X , Y ? ? e ?Tk ? 2,? ? ? ? n ? ? ? ? ? e ? H ? 。
若一个 n 个顶点 k ? 1 部图中,有两部点数为 a , b ,且 a ? b ? 2 ,我们重新分配点数为

a ? 1, b ? 1 ,由于 ( a ? 1)(b ? 1) ? ab ? a ? b ? 1 ? 1 ,故有 n 个顶点 k ? 1 部图中,点分布越平
均边数越多,因此 e ? G ? ? e ? H ? ? e Tk ?1, n ,故结论成立。

?

?

推论 1:简单图 G 有 n 个点,若 G 中不含三角形,则 e ? G ? ? ?

? n2 ? ?。 ?4?

? n2 ? e G 推论 2:简单图 G 有 n 个点,若 G 中不含 K 4 ,则 ? ? ? ? ? 。 ?3?















例 14: 平面上有 7 个点, 每 3 个点中至少存在两个点有线段相连, 问最少连了几条线段? (上海) 解:我们设此图为 G ,补图为 G ,则我们的问题等价于 G 中不存在三角形,并且 G 的边数 尽量的多。 由 Turan 定理,此时 G ? T2, n ,故 G 的边数最少是 C?n /2? ? C?n /2? , G 可以构造如下:
2 2 ? ? ? ?

将 n 个点分成两部分点数分别是 ? ? , ? ? ,这样任取三个点必有两个点属于同一部分。 2 2 例 15: n 是一个正整数,平面上有 5n 个点,其中任意三点都不在一条直线上,现在用

?n? ?n? ? ? ? ?

10n 2 ? 1 条线段连接这些点,然后对这些线段进行黑白染色。求证:必有同色三角形。
证明:由于 e T5,5 n ?

?

?

4 n ? 5n ? 10n 2 ,由 Turan 定理,图中必有 K 6 ,而对 K 6 的边黑白染 2

色,必有同色三角形。 例 16:有 30 个人参加一次聚会,每人都在聚会时送了一件礼物给另外一个人(一个人 可以收到多件礼物) ,求证:可以在其中找出 10 个人,这些人相互之间都没有送过礼物。 (Baltic 2010) 证明:以 30 个人为顶点,若两人之间有一人给另一人礼物则连接相应的两个点,这样得到
2 图 G 最多有 30 条边,因此它的补图 G 至少有 C30 ? 30 ? 405 条边。

本题等价于要证明 G 中存在 K10 ,由 Turan 定理,若 30 个点的图没有 K10 ,边数最多 的是 T9,30 ,也即 30 个点分为 9 组,有 3 组每组 4 个点,有 6 组每组 3 个点,因此最多有

3 ? 4 ? 26 ? 6 ? 3 ? 27 ? 399 边。因此至少有 405 条边的 G 中肯定有 K10 。 2 证明 2:设 S 为这 30 个人,如果 S 的子集 A 中的人相互之间都没有送礼物,则称 A 是一个
好集,由已知每个一元子集都是好集。

U 是所有收到过 T 中人的礼物的全体人员, 设 T 是其中人数最多的好集, 显然 U ? T ,
故 T ?U ? 2 T 。 对于任意 x ? T ? U ,由 U 的定义可知 x 没有收到过 T 中人的礼物,又因为 T ? ? x? 不 是好集,因此 x 送了礼物给 T 中的一人,所以 T ? U 也是一个好集。 因此 T ? 10 。 所以可以在 由 T 的最大性可得 T ? T ? U ? 30 ? T ? U ? 30 ? 2 T , 其中找出 10 个人,这些人相互之间都没有送过礼物。














n2 条线段的 3

例 17:在单位圆上有 n 个点,用线段将这 n 个点相连,证明:其中最多有

(波兰 1998) 距离大于 2 。 证明:我们构造一个 n 个点的图 G ,如果在单位圆上两点的距离大于 2 ,则在 G 中将这 两个点相连。 我们先来证明 G 中不存在 K 4 ,若不然则有圆上 4 个点相互之间的距离都大于 2 ,假 设这 4 个点顺时针依次为 ABCD ,由于 AB, BC , CD ? 大于

2 ,故 ?AOB, ?BOC , ?COD 均

?
2

,因此 ?DOA ?

?
2

,但此时 AD ?

2 ,矛盾。

由 Turan 定理, G 最多有

n2 条边。 3

例 18:求满足以下条件的最小正整数 n :在圆周上任取 n 个点 A1 , A2 ,..., An ,则所有 (上海高中数学竞赛) ?Ai OA j 中至少有 2011 个不大于 120? 。 解:如果 ?Ai OA j ? 120? ,我们都连接 Ai A j ,这样就得到一个由 n 个点组成的图 G ,由于

? n2 ? n2 n2 1 2 2 ,所以至少有 Cn ? ? ? n ? 1? ? 1 个角不大 图中没有三角形,因此 e ? G ? ? ? ? ? 4 4 ?4? 4
于 120? 。 因此当 n ? 91 时,至少有 2024 ? 2009 个角 ?Ai OA j 不大于 120? 。

而当 n ? 90 时, T2, n 中没有三角形,我们将一个圆 6 等分,将 n 个点分为 ? ? , ? ? 两 2 2 部分放在相对的两段弧上,这样在同一段弧的两个点构成的圆心角都小于 60? ,而不在同一 段弧的两个点构成的圆心角都大于 120? ,所以有 C?n / 2? ? C?n / 2? ? 2C45 ? 1980 个角不大于
2 2 2 ? ? ? ?

?n? ?n? ? ? ? ?

120? 。
因此, n 最小为 91 。










相关文章:
图论问题选讲答案
图论问题选讲答案_学科竞赛_高中教育_教育专区。数学竞赛辅导讲义,有答案图论问题讲义答案 例 1.空间 6 点,无 3 点共线,每两点连 1 条线,染红或蓝. ⑴ 求...
图论问题选讲
图论问题选讲_数学_自然科学_专业资料。图重要的概念与定理 论 大连市第二十四...2 例题选讲例 1 某天晚上 21 个人之间通了电话,有人发现这 21 人共通话 ...
图论例题
图论问题选讲 冯惠愚 2009.07.15. 四点连出同色四边形.(图 1) ⑵设 v1,v2,v3 之间都连红线.由于 v1,v2,v3 的每一个都至少连出了 3 条红线,故它们...
图论模型简介
图论模型选讲 35页 免费 图论模型的构建 41页 免费 图论常见模型 72页 2财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进...
m08图论模型简介
43页 2财富值 图论模型选讲 35页 免费 图论模型的构建 41页 免费 图论常见模型 72页 2财富值 图论模型及其算法 85页 2财富值喜欢此文档的还喜欢 ...
图论模型讲义
图论模型选讲 35页 免费 图论模型的构建 41页 免费 图论常见模型 72页 2财富...51 第 8 章 图论模型图论(Graph Theory)18 世纪起源于欧洲。瑞士著名数学家...
图论模型
图论模型选讲 35页 免费 图论模型的构建 41页 免费 图论模型及其算法 85页 1...? ? ? 2 = [ ( N ? 1)!] 2 ; n ≥ 3 图论模型: 假设该公园共有...
数学建模选讲
数学建模选讲_数学_自然科学_专业资料。数学建模选讲姚一、授课内容与方法数学建模...。 具体求解可以用图论方法, 将本系统的 10 个可取状态用 l0 个点表示, ...
图论模型
图论模型一 43页 2财富值 图论模型选讲 35页 免费 图论模型的构建 41页 免费 图论模型及其算法 85页 2财富值 图论常见模型 72页 2财富值 图论模型专题 98页...
图论模型简介
图论模型 98页 免费 图论模型一 43页 2财富值 图论模型选讲 35页 免费 图论模型的构建 41页 免费 图论常见模型 72页 2财富值喜欢...
更多相关标签:
道教符咒选讲 | 几何证明选讲 | 数学分析选讲 | 不等式选讲 | 选修4 5不等式选讲 | 数学史选讲 | 中华文化选讲 | 智慧树中华文化选讲 |