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

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江苏省数学竞赛《提优教程》教案:第66讲_覆盖
2012江苏省数学竞赛提优教程》教案:第66讲_覆盖_学科竞赛_高中教育_教育专区。第 66 讲 覆盖本节主要内容是图形覆盖与嵌入. 一、图形覆盖的定义: 平面闭图形...
2012江苏省数学竞赛《提优教程》教案:第68讲_图论问题(二)
2012江苏省数学竞赛提优教程》教案:第68讲_图论问题(二)_学科竞赛_高中教育_教育专区。第 68 讲 图论问题(二) 本讲主要内容:本讲将继续研究用图来解决问题...
2012江苏省数学竞赛《提优教程》教案:第62讲__多项式
2012江苏省数学竞赛提优教程》教案:第62讲__多项式_学科竞赛_高中教育_教育专区...68份文档 新市场营销法则 助推企业成长 999感冒灵市场营销方案 汽车品牌的足球...
2012江苏省数学竞赛《提优教程》教案:第05讲 子集
2012江苏省数学竞赛提优教程》教案:第05讲 子集_学科竞赛_高中教育_教育专区。第 5 讲 子集本讲内容有子集、子集的个数、集合的划分及子集的应用。 设 ...
2012江苏省数学竞赛《提优教程》教案:第60讲 概率2
2012江苏省数学竞赛提优教程》教案:第60讲 概率2_学科竞赛_高中教育_教育专区...0.68 (2)随机变量 ? 、 ? 的分别列是 P 乙 0.75? 0.8 ? 0.6. ? ...
2012江苏省数学竞赛《提优教程》教案:第63讲_极限
2012江苏省数学竞赛提优教程》教案:第63讲_极限_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 2012江苏省数学竞赛提优教程》教案:第63讲...
2012江苏省数学竞赛《提优教程》教案:第57讲 排列与组合
2012江苏省数学竞赛提优教程》教案:第57讲 排列与组合_学科竞赛_高中教育_教育...126 个五位 “渐升数” ,若把这些数按从小到大的顺序排列,则第 100 个数...
2012江苏省数学竞赛《提优教程》教案:第49讲四面体与球题目
2012江苏省数学竞赛提优教程》教案:第49讲四面体与球题目_学科竞赛_高中教育_...68份文档 新市场营销法则 助推企业成长 999感冒灵市场营销方案 汽车品牌的足球...
2012江苏省数学竞赛《提优教程》教案:第36讲--同-余
2012江苏省数学竞赛提优教程》教案:第36讲--同-余_学科竞赛_高中教育_教育专区。第 17 讲 同 余 同余是数论中的重要概念,同余理论是研究整数问题的重要工具...
2012江苏省数学竞赛《提优教程》教案:第75讲_几何不等式
2012江苏省数学竞赛提优教程》教案:第75讲_几何不等式_学科竞赛_高中教育_教育专区。第 75 讲 几何不等式本讲只要内容是几何不等式: A 类例题 例 1 已知 ...
更多相关标签: