高中数学竞赛中的解题方法与策略-高中卷-14-第二版

章节摘录

版权页：   插图：   图论是以图为研究对象，研究顶点和边组成的图形的数学理论和方法，起源于著名的哥尼斯堡七桥问题。图论中的图是指由若干个不同的顶点及连接其中某些顶点的边所构成的图形，通常用G表示，或者更确切地记作G（V，E），其中V是所有顶点的集合，E是所有边的集合。图G中，顶点的位置以及边的曲直长短都是无关紧要的，我们所关心的是图G中顶点和边的组成状况。 图论有一套庞大的概念系统，下面列举的是其中最基本的概念以及一些本节中会涉及到的概念： 如果图G的两个顶点ν1，ν2之间有边相连，则称ν1，ν2相邻，否则称ν1，ν2不相邻。 如果一条边的两端是同一顶点，这样的边称为环。 如果两个顶点之间有k（k≥2）条边相连，那么这些边称为重边。 若一个图既没有环也没有重边，这样的图称为简单图。 每两个顶点均相邻的简单图称为完全图。 有n个顶点的图称为 n阶图。其中n阶完全图记为Kn。 顶点数和边数都有限的图称为有限图，否则称为无限图。 图G中，与顶点ν相邻的边数（环作两条边计算）称为顶点ν的度（或者次数），记做d（ν）。若顶点的度是奇数，则称为奇顶点，否则称为偶顶点。 若图中的边不考虑起点和终点，则称为无向图，否则称为有向图（有向图有出度和入度的概念）。如无特别说明，一般的图都指无向的简单图。 在图G中，一个由不同的边组成的序列：e1，e2，…，em（其中ei=（νi－1，νi），i=1，2，…，m）称为从ν0到νm的链，其中ν0和νm称为这条链的端点，数m称为这条链的长。如果一条链的两个端点重合，则称这条链为圈。 如果对图的任何两个顶点u，ν，都存在一条链以u，ν为端点，这样的图称为连通图。 关于图G的顶点和边数之间的关系，有如下定理。 定理 图G中边数的两倍等于顶点度数之和。 设G中n个顶点为ν1，ν2，…，νn，边数为e，则 d（ν1）+d（ν2）+…+d（νn）=2e。 证明 所有顶点的度的和d（ν1）+d（ν2）+…+d（νn）表示以顶点ν1，ν2，…，νn中某个顶点为端点的边的总数。由于一条边有两个顶点，所以图G中每条边在和d（ν1）+d（ν2）+…+d（νn）中被计数了两次。即证。 这个定理通常称为握手引理：如果许多人在一起握手，那么握手次数为偶数次，从而握过奇数次手的人有偶数个。即得推论 推论 图G中奇顶点的个数一定是偶数个。 一笔画，就是纸上给定一个图G，能否从图G的一个顶点出发，笔不离开纸，而且连续地沿着每条边恰好一次，然后回到原来顶点，从而画出整个图G。如果图是欧拉图，则可以一笔画出整个图G，否则不能。欧拉给出过一个图是否是欧拉图的判别方法。 一笔画定理 一个连通图为欧拉图的充要条件是每个顶点的度都是偶数。 由此可以推出，一个图可以一笔画的充要条件是没有奇顶点或者两个奇顶点。如果有两个奇顶点，那么这两个奇顶点是一笔画的起始点和结束点。 本节所选的大多数例题和习题本身并非图论问题，但我们采用图论方法求解，旨在反映图论应用的广泛性与灵活性。 例1 n名选手进行网球对抗赛，每名选手至多赛一场，每场比赛两名选手参加，已赛完n+1场。证明：至少有一名选手赛过三次。 证明 把 n名选手用n个点ν1，ν2，…，νn表示，当且仅当νi，νj，所代表的两名选手比赛过时，令νi，νj相邻，于是得到一个含n个顶点的简单图。由于总共赛过n+1场，所以图G的边数是，n+1。由定理知 d（ν1）+d（ν2）+…+d（νn）=2（n+1）， 如果图G中所有顶点的度都不超过2，则由上式得到 2（n+1）=d（ν1）+d（ν2）+…+d（νn）≤2n， 这不可能。因此图G中至少有一个顶点x，它的度至少是3。于是，顶点x所表示的选手至少赛过三次。 例2设S={x1，x2，…，xn}是平面上的点集，其中n≥3。若任意两点之间的距离不小于1，证明：距离恰好等于1的点对不超过3n对。 证明取这n个点为顶点，两顶点相邻当且仅当它们之间距离为1，得图G。

内容概要

熊斌第46届、49届、51届、52届和53届国际数学奥林匹克中国队领队、主教练，华东师范大学数学系教授，博士生导师，华东师范大学国际数学奥林匹克研究中心主任。多次参与中国数学奥林匹克、全国高中数学联赛、全国初中数学竞赛、西部数学奥林匹克、女子数学奥林匹克、国际城市青少年数学邀请赛等竞赛的命题工作。在国内外发表了100余篇论文，主编和编著的著作150多本。

何忆捷上海市延安中学教师、数学奥林匹克教练员，复旦大学理学硕士，第18届中国数学奥林匹克金牌获得者。长期从事数学奥林匹克研究，高中毕业后出版著作《高中奥数命题研究与训练题集》，并参与全国高中数学联赛、国家集训队等命题及培训工作。

书籍目录

1 化归
2 反证法
3 数学归纳法
4 抽屉原理
5 容斥原理
6 极端原理
7 奇偶性
8 面积法
9 从整体考虑问题
10 选择合适的记号
11 数形结合
12 对应与配对
13 递推方法
14 染色法
15 赋值法
16 算两次
17 逐步调整法
18 构造法
19 不变量与恒增(减)量
20 图论方法
习题解答

编辑推荐

《数学奥林匹克小丛书•高中卷:高中数学竞赛中的解题方法与策略(第2版)》可作为中学生的课外辅导材料，也可以作为师范院校本科生、研究生的数学解题和数学竞赛课程的教材或参考书。

作者简介

奥数小丛书 高中卷14（第二版 高中数学竞赛中的解题方法与策略），ISBN：9787561792025，作者：熊斌，何忆捷 编著

图书封面

---

 高中数学竞赛中的解题方法与策略-高中卷-14-第二版下载

---