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

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 的元素不超过 n 个,则这样的三角形可能不存在.(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 条线必连出了 以此 4 点中的 3 点为顶点的三角形. 设 n=k 时,2k 个点间连有 k +1 条线时,必有三角形出现.则当 n=k+1 时,2(k+1) 个点间连了(k+1) +1 条线.此时,任取两个相邻的顶点 v1,v2,如果在其余的顶点中有某 个顶点与 v1,v2 都连了线,例如 v3 与 v1,v2 都连了线(图 4(1)),则出现了三角形.如果其 余所有的点与此二点都至多连出 1 条线(图 4(2)),则去掉点 v1,v2 及与这两点相邻的边, 此时,余下 2k 个点,至多去掉了 2k+1 条边,余下至少(k+1) +1-(2k+1)=k +1 条边, 由归纳假设知,其中必有三角形. 2 2 2 2 2 2 v3 v3 v4 v 2k v1 (1) v2 图4 v1 (2) v2 综上可知,命题成立. 说明 若 2n 个点间连了 n 条边,可以把这 2n 个点分成两组,每组 n 个点,规定同组的 点间都不连线,不同组的任何两点都连 1 条线,这样得到了一个完全偶图 Kn,n,此时共计连 了 n 条线,但任取三点,必有两点在同一组,它们之间没有连线,于是不出现三角形. 2 2 例 2 一个舞会有 n(n?2)个男生与 n 个女生参加,每个男生都与一些女生(不是全部) 跳过舞,而每个女生都至少与 1 名男生跳过舞,证明,存在男生 b1,b2 与女生 g1,g2,其中 b1 与 g1 跳过舞,b2 与 g2 跳过舞.但 b1 与 g2 没有跳过舞,b2 与 g1 没有跳过舞. 分析 就是要给出一种选择方法,按此方法操作,即可选 出满足要求的两个男生与两个女生.可以用极端原理来证明这 样的存在性命题. 证明 取所有男生中与女生跳舞人数最多的一个,设是 (1) b 1 b 2(3) b1.b1 至少与 1 名女生没有跳过舞,取没有与 b1 跳

相关文章:
2012江苏省数学竞赛提优教案:第68讲_图论问题(二)
2012江苏省数学竞赛提优教案:第68讲_图论问题(二)_学科竞赛_高中教育_教育专区。第 68 讲 图论问题(二) 本讲主要内容:本讲将继续研究用图来解决问题的方法. ...
2012江苏省数学竞赛《提优教程》教案:第6讲__函数问题...
2012江苏省数学竞赛提优教程》教案:第6讲__函数问题选讲 隐藏>> 第6讲 函数问题选讲 本节主要内容有运用函数的有关知识解决函数自身的问题和与函数有关的方...
2012江苏省数学竞赛《提优教程》教案:第60讲 概率2
2012江苏省数学竞赛提优教程》教案:第60讲 概率2_学科竞赛_高中教育_教育专区...P 5 0.68 2.5 0.32 ? P 2.5 0.6 1.5 0.4 E? ? 5 ? 0.68 ? ...
2012江苏省数学竞赛《提优教程》教案:第63讲_极限
2012江苏省数学竞赛提优教程》教案:第63讲_极限_学科竞赛_高中教育_教育专区...a 无限趋近于 0) ,那么就说数列 {a n } 以 a 为极限,或者说 a 是数列...
2012江苏省数学竞赛《提优教程》教案:第67讲_图论问题(一)
2012江苏省数学竞赛提优教程》教案:第67讲_图论问题(一)_学科竞赛_高中教育_教育专区。第 67 讲 图论问题(一) 本节主要内容是:把一个具体问题用图形表示...
2012江苏省数学竞赛《提优教程》教案:第35讲_整数性质
2012江苏省数学竞赛提优教程》教案:第35讲_整数性质_学科竞赛_高中教育_教育专区。第 16 讲 整数的性质 初等数论的基本研究对象是整数.两个整数的和、差、积...
2012江苏省数学竞赛《提优教程》教案:第59讲 概率1
2012江苏省数学竞赛提优教程》教案:第59讲 概率1_学科竞赛_高中教育_教育专区。第 19 讲 概率(一) 概率的一些术语及基本知识. 1.基本事件:一次试验(例如掷...
2012江苏省数学竞赛《提优教程》教案:第10讲_覆盖_免费...
2012江苏省数学竞赛提优教程》教案:第10讲_覆盖 隐藏>> 第10 讲 覆盖本节主要内容是图形覆盖与嵌入. 一、图形覆盖的定义: 平面闭图形指的是由平面上一条简...
2012江苏省数学竞赛《提优教程》教案:第55讲 轨迹
2012江苏省数学竞赛提优教程》教案:第55讲 轨迹_学科竞赛_高中教育_教育专区...68份文档 新市场营销法则 助推企业成长 999感冒灵市场营销方案 汽车品牌的足球...
2012江苏省数学竞赛《提优教程》教案:第15讲_存在性问题
2012江苏省数学竞赛提优教程》教案:第15讲_存在性问题_学科竞赛_高中教育_教育专区。第 15 讲 存在性问题 本节主要内容是存在性问题. 存在性问题有三种: 第...
更多相关标签: