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

数学竞赛中的图论问题


2-6 数学竞赛中的图论问题(P.221)
一、基本思想 引例欧拉 7 桥问题

把所考察的对象作为顶点(v) ,把对象之间是否具有我们 所关心的某种关系作为了连线的的条件(e) ,这样,就可以 把一个具体问题抽象为图的研究. 在解数学竞赛题中的好处: (1)把抽象的问题转化为直观的问题; (2)把复杂的逻辑关系转化为简明的数量关系.

r />二、基本内容 有图、顶点、边、简单图、完全图、连通图、树、二分 图、竞赛图等 14 个定义,12 条定理: 定义1 设集合 V (G) ? ?v1 , v2 ,?, v p ? ? ? , E (G ) ? ?e1 , e2 ,? , eq ? 是 V ? G ?

中某些元素对的无序集合,则称 G ? V? G, ?E ? ?G 为图,又称 V ? G ? ? 为图 G 的顶点集合,其元素叫做顶点;称 E ? G ? 图 G 的边集合, 其元素叫做边.若 u,
v? V ?G ? ,边 e 是无序顶点对 ? u , v ? ,则记

e ? uv ? vu ,且称 u 与 v 是边 e 的端点, e 与顶点 u, v 关联,也说顶

点 u 与 v 邻接(或相邻) .有公共端点的边 e1 , e2 称为邻边,也说
e1 , e2 邻接.

例如 顶点: V (G) ={小王,小李,小张,小赵,小陈,小刘} ,
边:e1 = {小王, 小李} e2 ={小李, , 小赵} e3 = , {小陈, 小刘}



e1 , e2 相邻.

定义 2

图 G 中所含顶点的数目称为图的阶数, 记为 V(也
G

用 G 来表示) ;又用 E 表示图 G 的边数(也用

来表示) .通

常用 G ? p, q ? 表示 p 个顶点,q 条边的图 G ;若 p, q 都是有限数的 图 称 为 有 限 图 , 否 则 称 为 无 限 图 . 如 果 对 于 图 G ?V , E ? 与
G ' ?V ' , E ' ? ,有 V ' ? V , E ' ? E ,则称 G ' 是 G 的子图.

定义 3

两顶点间至多连一条边且每边的两个端点相异

的图称为简单图;图中任何两个顶点都邻接的简单图称为完 全图, p 阶完全图记为 K p . 定理 1 定义4
K p 的边数为 E ?

p ? p ? 1? 2



图 G 中与顶点 u 关联的边数称为顶点 u 的度,记

为 d ? u ? .如果 u 的度数是奇数,则称 u 为奇顶点;如果 u 的度 数是偶数,则称 u 为偶顶点. 定理2 任何一个图的总度数等于边数的 2 倍,

? d ?u ? ? 2 E .
u?V

推论 定义5

任何图中奇顶点的个数是偶数. 图 G 中点边交错的非空有限序列 u0 e1 u1 e2?3 k ? u
uk
1k

e u

叫做以 u0 , uk 为端点的途径.若途径中所有的 ei 都不相同,则 叫做 u0 ? uk 链; 若链中所有的 ui 都不相同则叫做 u0 ? uk 通路, 称 k 为通路的长;若 u0 , uk 重合,则叫做回路或圈. k 为奇(偶) 数的回路称为奇(偶)回路. 定义6 经过图 G 中每条边的链称为欧拉链, 两端重合的

欧拉链称为欧拉环游图(欧拉回路) ,有欧拉环游的图称为 欧拉图(简称 E 图) 直观的说, 欧拉图就是从一个顶点出发而每边通过一次又 能回到出发顶点的图(一笔画) . 定理 3 连通图 G 为欧拉图的充要条件是 G 中没有奇顶点. 推论 画成. 定义7 包含图 G 每一个顶点的通路称为哈密尔顿通路, 如果连通图 G 有 2 k 个奇顶点,那么图 G 可以用 k 笔

有哈密尔顿通路的图称为哈密尔顿图. 定理 4 设 G 是一个 p 阶简单图 ? p ? 3? ,若 G 中任意两个顶

点 u, v 的度数满足 d ? u? ? d ? v ,则 G 是哈密尔顿图. ? ? p 定义8 连通而无回路的图称为树, 树上度数为 1 的顶点

称为叶(悬挂点) . 定理 5 如果树 T 的顶点数不小于 2, 那么树 T 上至少有两

个叶. 定理 6 设图 G 有 p 个顶点, 条边, 则下列说法彼此等价: q

(1) G 是树; (2) G 的任意两个顶点间有且仅有一条通路; (3) G 连通,且 q ? p ? 1 ; (4) G 无回路,且 q ? p ? 1 ; (5)G 无回路, 但连接任何两个非邻接顶点 u, v 所得新图, 有且仅有一个回路; (6) G 连通,但舍弃任何一条边后便不连通. 定义 9 图 G ?V , E ? 的顶点集 V 若能分成两个非空子集 V1 ,V2 ,

使得任何边 e 的一个端点属于 V1 ,另一个端点属于 V2 ,则 G 为 二分图. 定理 7 图 G 为二分图的充要条件是 G 不含奇回路. 定义 10 设图 G ?V , E ? 为简单图, M 是 E 的一个非空子集,

若 M 中任何两边都不相邻,则称 M 为图 G 的一个匹配(又称 对集) .若 M 边之端点包括 G 中一切顶点,则称 M 为 G 的一个 完备匹配. M 中每一边的两个端点称为相配. 定义 11 在图的边上用箭头标注出方向就得到一个有向 图,称为定向.完全图的一个定向称为竞赛图. 定理 8 定义 12 每个竞赛图都有单向哈密尔顿通路. 若一个图 G 可以画在平面上,使得任何两条边

都不在非顶点处相交,则称图 G 为平面图.图的边所包围的

一个区域,其内部既不包含图的顶点,也不包含图的边,这 样的区域为图 G 的一个面.为了方便,把平面图 G 的外部无 限区域也作为一个面,称为外部面,其他面则称为图 G 的内 部面. 定理 9 设 G 是一个简单连通平面图, V ? G? ?
q? f ? . 2
,p ?E ? G ? q ,

面数为 f (包括外部面) ,则 p ? 定理 10

一个连通的平面简单图 G ,若有 v 个顶点 ? v ? 3? , e

条边,则 e ? 3v ? 6 . 定义 13 用红蓝两种颜色对完全图 K p 的边任意染色, 使每 条边都染上某一种颜色,若总会出现红色边 K m 或蓝色边 K n 时, 则记 p 的最小值为 r ? m, n ? , r ? m, n ? 为关于 m, n 的拉姆赛数. 称 定理 11
r ? 3 , ?3? 6? , r , ?3 ? 4 ?r 9? , ? 3 , ?5 r ? ?14, ? r ,? 6 ? 1 8 , 3 3, 7 23,

r ? 3,9 ? ? 36, r ? 4, 4 ? ? 18.

定义 14

用 n 种颜色对完全图 K p 的边任意染色, 使每条边

都染上某一种颜色,若总会出现同色三角时,则记 p 的最小 值为 r ? 3,3,?,3? ,简记为 rn ,称 rn 为拉塞姆数. ? ?? ? ?
n个

定理 12 设 S1 , S2 ,?, Sn 是集合 ?1, 2,?, rn ? 的任意分划, 则存在一 个 i,1 ? i ? rn ,使 S i 中有方程 x ? y ? z 的根.

三、主要方法 不是图论知识的直接套用,而是图论基本思想的常识应 用.

构造法、 反证法 数学归纳法 抽屉原理 染色方法 极端原理 四、例题选讲 例 1-1 有 5 个课外活动小组,每 2 个小组里有一个相

同的同学,每个同学恰好在两个小组里出现,问这 5 个小组 里共有多少个同学? 解 把小组对应为点, “每 2 个小组里

有一个相同的同学”就连一条线,每两点 都有连线;又由于“每个同学恰好在两个 小组里出现” ,故每两点都连且只连一条 线,得 5 阶完全图,图中变的条数就是同学个数,得 10 个 同学. 例 1-2 有 n 个药箱,每两个药箱里有一种相同的药,

每种药恰好在两个药箱里出现,问共有多少种药? 解 把药箱对应为点, “两个药箱里有 1 种相同的药”就 连一条线,每两点都有连线;又由于“每种药恰好在两个药 箱里出现” ,故每两点都连且只连一条线,得(n 阶完全图)
2 N ? Cn .

例2

证明: 在任何一群人中, 与奇数个人互相握手 (互

相认识)的人有偶数个. 证明 记这群人为 n 个点, “互相握手”就在对应的两

点连一条线,共有 e 条,每个人认识的人数为点的“度数” , 记为 d1 , d2 ,?, dn ,则
d1 ? d 2 ? ? ? d n ? 2e ,

?d ? ?d
i 奇 偶

i

? 2e ,

?d


i

? 2e ? ? d i 为偶数


? d 是偶数个奇数之和.
i 奇

例 3-1

(1947, 匈牙, 2-4-1) 例 证明: 在任意 6 个人中,

总可以找到 3 个人互相认识,或互相不认识,并且这种情况 至少出现 2 个.

例 3-2 (1976,波兰)平面上有 6 个点,任何 3 点都是 一个不等边三角形的顶点,则这些三角形有一个的最短边又

是另一个三角形的最长边. 提要:把每个三角形的最短边染成红色, 存在红色三角形, 红色三角形的最长边为所求. 例4 在边二染色的 K5 中没有单色三角形的充要条件是

它可分解为一红一蓝两个圈,每个圈恰由 5 条边组成. 证明 充分性是显然的.

考虑必要性,在 K5 中每点恰引出 4 条线段,如果从其中某点 A1 能引出三 条同色线段 A1A1,A1A3,A1A4,记为 同红,则考虑△A2A3A4,若当中有红边
Ai A j ( 2 ? i ? j ? 4 ) ,则存在红色三角形 A1 Ai Aj 是同蓝色三角形,

均无与单色三角形矛盾.所以,从每点引出的四条线段中恰 有两条红色两条蓝色,整个图中恰有 5 条红边、5 条蓝边. 现只看红边, 它们组成一个每点度数都是 2 的偶图, 可以 构成一个或几个圈,但是每个圈至少有 3 条边,故 5 条红边 只能构成一个圈,同理 5 条蓝边也构成一个圈. 例 5 求最小正整数 n ,使在任何 n 个无理数中,总有 3

个数,其中每两数之和都仍为无理数. 解
n ? 5.

取 4 个无理数 ?

2, 3, ? 2, ? 3

? ,显然不满足要求,故

设 a, b, c, d , e 是 5 个无理数,视它们为 5 个点,若两数之和

为有理数, 则在相应两点间连一条红边, 否则连一条蓝边. 这 就得到一个二染色 k5 .只须证图中有蓝色三角形,分两步: (1)无红色三角形.若不然,顶点所对应的 3 个数中, 两两之和均为有理数,不妨设 a ? b, b ? c, c ? a 都是有理数,有
1 a ? [(a ? b) ? (b ? c) ? (c ? a)] 2

但无理数≠有理数,故 k5 中无红色三角形. (2)有同色三角形,若不然,由上例知, k5 中有一个红 圈,顶点所对应的 5 个数中,两两之和均为有理数,设
a ? b, b ? c, c ? d , d ? e, e ? a 为有理数,则

1 a ? [(a ? b) ? (b ? c) ? (c ? d ) ? (d ? e) ? (e ? a)] 2

但无理数≠有理数,故 k5 中无 5 条边组成的红圈,从而有 同色三角形. 这时,同色三角形必为蓝色三角形,其顶点所对应的 3 个无理数,两两之和仍为无理数. 综上所述,最小的正整数 n ? 5 . 例 6-1 某足球邀请赛有 A, B, C, D 4 个城市参加,每市派出 红黄两支球队,根据比赛规则,每两之间球队至多赛一场, 并且同一城市的两支球队之间不进行比赛.比赛若干天后进 行统计,发现除 A 市红队外,其他各队比赛过的场次各不相 同.问 A 市黄队赛过多少场. (找黄队,求 c 场次) 解 因为“同一城市的两支球队之间不进行比赛” ,所以

每一个球队最多赛 6 场;有因为“除 A 市红队外,其他各队 比赛过的场次各不相同” ,所以,其他各队赛过的场次分别 为 0,1,2,3,4,5,6 共 7 种情况. 用 A1 , A2 , A3 , A4 , A5 , A6 , A7 , A8 表示 8 支球 队,两队之间进行了比赛就连 1 条边, 其中 A1 , A2 , A3 , A4 , A5 , A6 , A7 分别赛了 6,5,4, 3,2,2,1,0 场. 由于 A1 赛了 6 场, 应有 6 条引线, 记为 A1 A2 , A1 A3 , A1 A4 , A1 A5 , A1 A6 , A1 A7 , 由于 A1 与
A8 没有引线,故 A1 , A8 属于同一城市.

同理,

A2 , A7 属于同一城市, A3 , A6 属于同一城市, A4 , A5

属于同一城市.
A4 , A5 属于同一城市且都赛过

3

场,由于“除 A 市红队外,其他各 队比赛过的场次各不相同” ,所以
A4 , A5 就是 A 市的两支球队, A 市黄 得

队赛过 3 场. 例 6-2 李明夫妇最近参加了一次集会, 同时出席的还有

三对夫妻.一见面,大家互相握手,当然夫妻之间不握手, 也没有人与同一个人握两次从手.握手完毕后,李明统计了 包括妻子在内的 7 个人握手的次数,发现恰好数字发互不相 同.请问.李明的妻子握了几次手?

例 6-3 (P.225 例 2-115)

作业:1

习题 2-6 第 1

2. 习题 2-6 第 11 题(P.235)


相关文章:
数学竞赛中的图论问题
数学竞赛中的图论问题_数学_自然科学_专业资料。这是一篇数学与应用数学专业的大学毕业论文,其中涉及到的是图论的基本问题以及图论问题在数学竞赛中的应用分类...
高中竞赛数学讲义第68讲图论问题(二)
高中竞赛数学讲义第68讲图论问题(二)_学科竞赛_高中教育_教育专区。第 68 讲 ...,也必 与 A 中唯一点 p?相邻.且若 p1、p2∈A,则在 B 中与它们相邻的...
浅谈图论在数学竞赛中的应用
浅谈图论数学竞赛中的应用 论作为应用数学的一部份,是数学的一个分支。它以...利用图论的基本原理及如何应用图 论方法解决实际问题,包括图的基本概念、图的...
图论在数学竞赛中的应用
如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 图论数学竞赛中的应用 隐藏>> 08 数学 080301048 李雅芳 图论 图论在...
数学竞赛中的数论问题
14 岁的波萨就发表了图论中“波萨定理” . ●重视数学能力的数学竞赛,已经广泛采用数论题目,是数学竞赛四大支柱之一,四大 1 支柱是:代数,几何,初等数论,组合初步...
对图论中一问题的探讨
图论中一问题的探讨 刘爱兰 (西北师范大学数学与统计学院 10 级数学与应用数学 2 班) 摘要: Schur 于 1916 年用图论中的结论证明了关于高维 Ramsey 数的 ...
数学竞赛:图论讲义
图论及其应用 58页 2财富值 数学竞赛中的图论问题 29页 20财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
图论问题选讲答案
图论问题选讲答案_学科竞赛_高中教育_教育专区。数学竞赛辅导讲义,有答案图论...E B 解:不一定,如图,五边形 ABCDE 中,染了 5 条红边 5 条蓝边,其中没...
六年级奥数:图论中的匹配与逻辑推理问题2013
六年级奥数:图论中的匹配与逻辑推理问题2013_学科竞赛_小学教育_教育专区。小学数学竞赛习题六年级奥数:图论中的匹配与逻辑推理问题 ...
2012江苏省数学竞赛提优教案:第67讲_图论问题(一)
2012江苏省数学竞赛提优教案:第67讲_图论问题(一)_学科竞赛_高中教育_教育专区...图中的点的集合称为图的点集,记为 V:V={v1,v2,?,vn,?};图中的线的...
更多相关标签:
图论 竞赛图 | 图论竞赛题 | 图论 信息学竞赛 | 数学竞赛中的数论问题 | 数学竞赛中的组合问题 | 离散数学 图论 | 组合数学与图论 | 离散数学图论ppt |