数学归纳法的逻辑原理及其在图论中的应用(1).pdf

数学归纳法的逻辑原理及其在图论中的应用 王天成 毒海溪范大学民族溪莲擎貔青海委审8 1 0 0 0 8 搐要 本文系统地介绍了数学归纳法的逻辑原理 圈论证明中逡甩数学归纳浓的类型问题 使读者对数学归纳法及教学归纳法 农瓣论孛的应用嗣题有一十套藩的认识 关键词 审越觳擎舞蝻法 一 数学嬲纳法的逻毫艮原理 数学归纳法是一种证疆与自然数n 有关的数学命题的 黧要方法 我们首先看 个简单的 人们熟悉的归纳集合 鄂自然数集N 0 1 l 要确定N 可先绘出一个特殊的 嚣索0 称为秘始元 它是产生N 的基再l l 然后霉绘密 个 f l I 自然数产生自然数的运算 即一元后继遮算n 蝴 1 这个运算作用在韧始元 上褥弼I 再作用在I 上 褥弱2 把这个过程一壹继续下去 莸蜀黻依次把所有自然 数产生出来 这个后继运算n 有 个性质 即当n N 时 贝H n E N 令P 是自然数的一个公共性质 并令P n 是一 个命题 表承爨然数n 鸯後震P 瑗在缎设命题 1 以0 2 所有n 如果P n 则P n 成立 那么可得 3 则所有 n P n 这就是通常所说的数学归纳法原理 用公式可表 蕊为 P O A n n E N 杰 p n H 纛 n n N 焱p n 或者表永为 V n n N p m m 如 叶P n 一 V n n E N p n 它是数学归纳法 简称归纳证明 的 基礁 摄据该朦理 我靛霹在有限鳇步骤是 证醒自然数集 巾无限的元素都有某性质 邸只要证明上述命题 1 和 2 我们就归纳地证明了命题 3 或者说 只要断定上述 公式的翦 孛 裁甑定了后锫 二 图论巾常用的归纳证明形式 因为图论中与自然数有关的命题当n o l 或n o 2 时容 易验证 并虽蠢n l 酵如暴结论P n 援确 曼萼不难推导出 n k 1 时结论p n 也正确 所以在窝论中利蘑数学麴纳法 诫明某 命题 我们往往采用第 数学归纳法 第一数攀归纳法 首先 证明当n 驭第一个值 例如 n o 1 爵结论p n 正确 然詹 缓设当n k k E N R k l l o 时结论P n 藏确 证明当n k 1 时结论p n 也正确 完成 这两个步骤 就可以断定命题P n 对予从研始的所有自 然耋 都歪礁 例l 对任意图G 有x G l 其中 为G 中顶点 的最大度 x G 为色数 即使图G 为n 一着色的n 的最小值 本文所提本港均觅文靛2 证瞬 对顶点p 归纳证赘 显然 当p l 时 A O x G 1 命题成娆 假设命题对硬点个数兰p l 时成藏 设v 是G 的任一褒底 由瑟缩法俄浚 x C v l 其中 为囊子图G v 中顶点的最大度 显然 故 有x G v A l 用A 1 种颜P 对O v 着色 设与 部接的 颚点是毪 v 矗 焉e l 晚 魄表承疆点v i 毪 v l 掰着 的颜色 因为k 兰A 敞从A 1 种颜色中必然可以找到一 种颜色c 黾 j l 2 k 对v 著颜色c h 予是命题得 诞 三 圈论中归纳法证明的类型 图论中的许多命题的证明 都广泛地运用了数学归纳 法 数学懿纳法在委论率琴失势一静衍之有效麓方法 下 面举例说明之 l 对顶点数P 归纳证明 壤2 若p 酚萋G 是一攥树 赠G 蹩有矿l 条边鳇连逶 匿 证明 对顶点P 归纳证明 当p l 或2 时 命题楚显然成 发的 缓设命题对少予p 个顶点的所有树均成立 由予树G 中两顶点阉道路的唯一链 移去G 巾的任何一条迭 均使 其变成有聪个分支G 1 和G 2 的分离图 设G l 与G 2 的边数和 硬点数分别是q P t 秘缘 投由归纳法的假设 有镶印广l 搿2 p r l 又p l 炉p 故得 薹 q l q l p l 1 挈b 1 l 蛩l 爹吁一堇 尹卜 1 0 点评 辫论孛的许多命趣与褒淼有关 其牵一些命蘧 的证明我们针对顶点数p 进行归纳证明往往比较有效 2 对边数q 归纳证明 筏3 数控公式 黯予基意的连逶乎鬻凿G 有 p q r 2 其中赫平筒图G 的面数 证明 对边数q 归纳证明 当q 时 由于G 怒连通图 收稿日期 2 0 0 7 0 6 2 7 作者简介 王炙成 1 9 7 1 一 男 汉族 青海贵南人 膏海师范大学民族师范学院副教授 膏海师范大学数学与信息科学系 武教疆合与蜜璃擎方向在职谚究生 万方数据 王天成 数学归纳法的逻辑原理及其在图论中的应用 所以G 只能是平凡图 结论显然成立 假设q k k 苫1 时成 立 当q k 1 时 对e 进行如下讨论 i 若G 是树 则G 是非平凡的 因而G 中至少有两片数 叶 设v 为数叶 令G G 吖 则G 仍然是连通图 且G 的边 数m m 1 k 由归纳假设可知 n m r 2 r l m r t 分别为G 7 的顶点数 边数和面 数 而n 1 1 1 r t i f 于是有 n m I n 1 一m 1 r n m r 2 i i 若G 不是树 则G 中含圈 设边e 在G 中某个圈上 令 G G e 则G 仍是连通且m m 一1 k 由归纳假设有n m 2 而n 功 r r 1 于是 n m r n 一 m 1 r t 1 n m r 2 点评 图有两个基本要素既图的顶点和边 图论中也有 许多命题与图的边有关 其中一些命题的证明我们针对边 数q 进行归纳证明就能达到目的 例3 中的命题是要证明等 式p q r 2 其中有三个自然数 我们对边数q 归纳证明就 达到了目的 3 对顶点集 或边集 的子集中元素个数归纳证明 例4 设T 为任意的一棵完全 y 树 q 为边数 t 为树 叶数 试证明q 2 t 一2 这里t 2 这个题的证明方法很多 下面就树叶数t 和分枝结点i 用数学归纳法进行证明 证明 方法一 对树叶数进行归纳证明 当t 2 时 结点数为3 边数q 2 故q 2 t 2 成立 假设t k k 苫2 时 结论成立 下面证明t k l 时结论 也成立 由于T 是完全二叉树 因此T 中一定存在都是树叶的 两兄弟结点v v 2 设v 是v v 的父亲 在T 中删除v v 2 得到 T T 仍为完全二叉树 这时结点v 成为树叶 树叶数t 卜2 1 k l l k 边数q 铷一2 由归纳假设知 q 2 t 2 所以q 一2 2 t 2 1 2 故q 2 t 2 方法 对分支点数i 用归纳法证明 磐 l 时 边数q 2 树叶数t 2 故q 2 t 2 成立 假设i k k 苫1 时 结论成 立 下面证明i k l 时结论也成立 由于T 是完全二叉树 因此T 中一定存在两个儿子都 是树叶的分支点 设v 就是这样一个分支点 设它的两个 儿子为v i 在T 中删除V i V 1 2 得树T T 仍为完全二叉 树 这时结点v 成为树叶 分支点数i 一 1 一l k l l k 树叶 数t t 2 1 边数q q 一2 由归纳假设知 q 2 t 2 所以 q 2 2 t 一 1 2 故q 2 t 2 点评 图的顶点 或边 根据它们具有的不同性质可以 分类 每一类都是顶点集 或边集 的一个子集 图论中有 些命题是针对不同分类的 证明这些命题时我们对子集中 元素个数归纳证明就能解决 例4 中 T 为任意的一棵完全 二叉树 它的顶点分为三类既树根 数叶和分枝结点 我们 针对树叶数戚分支点数i 进行归纳就能证明 4 其他与自然数有关命题的归纳证明 在图论中 应用数学归纳法证明命题除上述3 种常见 的类型外 还有其它与自然数n 有关的命题也可以用归纳 法证明 例5 设A 是图G 的邻接矩阵 则A K 的 i j 元素a k 垮 q 于G 中联结v 与v i 的长为k 的路的数目 证明 对k 用归纳法 当k o 时A 0 I 为P 阶单位矩阵 从任一顶点v i 到自身有 一条长为0 的路 任何两个不同的顶点间没有长为0 的路 故当k O 时定理成立 设定理对k 成立 现证明对k l 也成立 由于A h A A k 故a k l l 窆咿 又因a 提联结v 与v 2 l Jl l 的长为1 的路的数目 a o 羔瞧联结v 与v 2 长为v 的路的数目 l J 所以a 鹕蹬 嚷示由v 经过一条到v l 再经过一条长为k 的路到 l J v j 的总长为k 1 的路的数目 对所有的球和 即得 喔所 有联结v 与v i 的长为k l 的路的数目 四 结束语 数学归纳法是一种常用的不可缺少的推理论证方法 没有它 在图论中很多与自然数有关的命题难以证明 同 时对于与自然数有关的命题 把n 所取的无穷多个值一一 加以验证是不可能的 用不完全归纳法验证其中一部分又 很不可靠 数学归纳法则是一种用有限步骤证明与自然数 有关的命题的可靠方法 其思维方式对于开发学生的智力 有重要价值 在图论学习中 掌握并应用好这一方法有十 分重要的意义 参考文献 1 张克民 林国宁 张忠辅 图论及其应用一习题解答 M 北京 清华大学出版社 1 9 9 8 圜王朝瑞 图论咖 北京 北京理工大学出版社 2 0 0 1 1 4 2 1 4 3 3 耿素云 离散数学 M 北京 高等教育出版社 1 9 9 8 6 4 卢开澄 卢华明 图论及其应用 M 北京 清华大学 出版社 1 9 9 5 5 刘世泽 反证法的逻辑依据 高等函授学报 1 9 9 7 4 6 华罗庚 数学归纳法 M 上海 上海教育出版社 1 9 6 3 责任编辑 马建萍 6 7 万方数据 数学归纳法的逻辑原理及其在图论中的应用数学归纳法的逻辑原理及其在图论中的应用 作者 王天成 作者单位 青海师范大学民族师范学院 青海西宁 810008 刊名 青海师范大学民族师范学院学报 英文刊名 JOURNAL OF MINORITIES TEACHERS COLLEGE OF QINGHAI TEACHERS UNIVERSITY 年 卷 期 2008 19 1 被引用次数 1次 参考文献 6条 参考文献 6条 1 张克民 林国宁 张忠辅 图论及其应用 习题解答 1998 2 王朝瑞 图论 2001 3 耿素云 离散数学 1998 4 卢开澄 卢华明 图论及其应用 1995 5 刘世泽 反证法的逻辑依据 1997 04 6 华罗庚 数学归纳法 1963 本文读者也读过 10条 本文读者也读过 10条 1 王志兰 WANG Zhi lan 数学归纳法及其在数论方面的应用 期刊论文 青海师专学报 教育科学 2009 29 5 2 孟祥德 数学归纳法 在行列式证题中的关键 期刊论文 科技信息2010 10 3 刘威 数学归纳法在函数迭代中的应用 期刊论文 科教文汇2009 3 4 方冬云 FANG Dong yun 数学归纳法在图论中的应用 期刊论文 莆田学院学报2009 16 2 5 肖海燕 代钦 数学归纳法在几何教学中的应用 期刊论文 内蒙古师范大学学报 教育科学版 2011 24 4 6 赵丕卿 赵刚堂 ZHAO Pi qing ZHAO Gang tang 数学归纳法的一个推广