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

图论选讲








图 论 选 讲
基本概念:点、线、简单图、连通、圈、树、点的度、完全图、 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 。










相关文章:
数学建模选讲
数学建模选讲_数学_自然科学_专业资料。数学建模选讲姚一、授课内容与方法数学建模...。 具体求解可以用图论方法, 将本系统的 10 个可取状态用 l0 个点表示, ...
高中竞赛数学讲义第68讲图论问题(二)
高中竞赛数学讲义第68讲图论问题(二)_学科竞赛_高中教育_教育专区。第 68 讲 ...即可选出满足要求的两个男生与两个女 生.可以用极端原理来证明这样的存在性...
图论例讲
图论例讲 图论例讲(陶平生) 1 、设有 2n 阶简单图 G ,若其每个顶点的度数皆不小于 n ,证明:从 G 中必可选出 n 条边,其端点互不相同. 2 、某地网球...
图论第一讲
图论第一讲 隐藏>> 第七章 图论与网络优化模型 图论与网络优化是数学建模的一个重要方面, 经 济管理、工业工程、通讯与网络技术等诸多领域中的 问题都可以化为...
图论-Dijkstra算法原理详细讲解
图论-Dijkstra算法原理详细讲解_计算机硬件及网络_IT/计算机_专业资料。Dijkstra 算法...Dijkstra经典算法详细讲... 7页 免费 用图论理论正确掌握破圈... 3页 免费...
图论例讲问题解答
图论例讲( 图论例讲(问题解答) 例讲 陶平生 1 、设有 2n 阶简单图 G ,若其每个顶点的度数皆不小于 n ,证明:从 G 中必可选出 n 条边,其端点互不相同...
图论 第四讲 经典算法
图论 第四讲 经典算法_数学_自然科学_专业资料。图论的经典算法图的经典算法是必须掌握的,背也要背过。联赛中考图论也是在经典 算法的基础上,考的是灵活应用。所...
图论的应用
数学与统计学院 图论论文 课程名称 题姓学专目名号业 图论及其应用 图论中的应用...会讲英语; b 会讲英语和汉 语; c 会讲英语、意大 利语和俄语; d 会讲...
5经典图论问题
经典图论问题 7页 免费 经典图论算法 25页 1财富值 图论 第四讲 经典算法 14...其二是由于对原型中要素的选 取有差异:模型一对要素的选取不充分,模型二则保留...
图论大作业
图论及其应用》大作业 指导老师 郝荣霞 知行 1503 徐鹏宇 15291200 第一题(讲过) 2.1.9 证明:若 G 是森林且恰有 2k 个奇点,则在 G 中有 k 条边不重...
更多相关标签: