|
![C{VQ5PGUX1A${]4JKPAUPGA.png](http://seupress.com/files/105410/1507/55558326604_m.png)
前言 图论是组合数学的一个重要分支，与其他的数学分支，如群论、矩阵论、概率论、拓扑学、数值分析等有着密切的联系。凡有二元关系的系统，应用图论均可建立一种合适的数学模型，因而图论在许多学科领域，如计算机科学、通讯科学、运筹学、电网络分析、化学、物理、管理以及社会科学等领域具有重要地位和广泛应用。此外，图论的理论与方法也是数学竞赛、数学建模等的理论基础和工具。因此在本书的大部分章节中介绍了一些应用实例，特别在第9章收集了若干图论在数学建模中的应用案例，读者可以从中掌握利用图论解决实际问题的基本方法和技巧。目前，图论已成为计算机科学、运筹学、组合优化、机电等学科的基本课程之一，国内外许多高校不仅对数学系的本科学生开设了图论课程，也面向其他专业学生开设了图论选修课程。 本书是在卜月华编写的《图论及其应用》的基础上，根据浙江省重点建设教材的要求并结合本科学生的特点和多年来的教学实践，由卜月华、王维凡和吕新忠重新编写而成。全书共分9章，前6章由卜月华编写整理，第7章由王维凡编写整理，第8章和第9章由吕新忠编写整理。内容不仅涉及图论的基本概念和基本理论，还力求突出图论方法的应用，尤其是在数学竞赛和数学建模中的应用。为使读者在使用本书时能自觉地调动学习积极性，更好地领悟图论的本质，每章后都配置了丰富而有趣的习题。本书适合作为高等院校各专业图论课程的教材或参考书，也可以作为大学生数学建模集训的参考读物。 在本书的再版过程中，编者参阅了国内外许多优秀的图论专著、教材及学术论文，特别参考了宋增民教授编著的《图论与网络最优化》一书，许多使用过初版《图论及其应用》一书的教师也对这一次再版工作提出了宝贵意见。在此编者表示衷心的感谢。 本书是浙江省重点建设教材，在出版过程中得到了浙江师范大学的教育部综合改革试点专业“数学与应用数学专业”的大力支持，在此深表感谢。 由于编者水平有限，在编写过程中对内容虽经反复推敲与修改，仍不可避免存在一些错误与疏漏，恳请同行专家、使用本教材的教师和学生以及其他读者不吝赐教，提出宝贵意见。 编者 2015年1月 目录 1图的基本概念1 1.1图论发展史1 1.2图的定义2 1.3顶点的度5 1.4子图与图的运算9 1.5一些特殊的图11 1.6图的矩阵表示15 1.7有向图21 1.8Brouwer不动点定理24 习题126 2图的连通性29 2.1路和圈29 2.2连通图35 2.3连通度39 2.4可靠通讯网络的构造45 2.5最短路问题47 2.6单行道路系统的构造57 习题258 3树61 3.1树的基本性质61 3.2生成树68 3.3最优生成树73 3.4树形图76 习题386 4Euler环游和Hamilton圈89 4.1Euler环游89 4.2中国邮路问题95 4.3Hamilton图99 4.4旅行售货员问题108 习题4112 5图的对集和独立集116 5.1对集116 5.2二分图的对集122 5.3二分图最大对集算法128 5.4最优分派问题129 5.5独立集和覆盖132 5.6Ramsey数137 习题5144 6平面图147 6.1平面图及平面嵌入147 6.2平面图性质149 6.3几类特殊的平面图158 6.4图的曲面嵌入161 习题6164 7图的染色166 7.1顶点染色167 7.2边染色173 7.3列表染色181 7.4全染色186 7.5染色方法189 7.5.1权转移方法189 7.5.2概率方法192 7.5.3代数方法193 习题7195 8网络流197 8.1基本概念和基本定理197 8.2最大流问题的算法201 8.3最小费用流问题205 8.4最小费用流的算法208 8.4.1原始算法208 8.4.2对偶算法209 8.5计划评审方法和关键路线法211 8.5.1PERT网络图的一些基本概念212 8.5.2建立PERT网络图的准则和注意事项213 8.5.3 PERT网络图的合并与简化214 8.5.4PERT网络图的计算215 习题8219 9图论在数学建模中的应用220 9.1模型1：婚配问题220 9.1.1问题分析220 9.1.2模型建立220 9.1.3模型的求解221 9.2模型2:锁具装箱问题222 9.2.1分析与建模222 9.2.2模型的求解222 9.3模型3：最优截断切割问题223 9.4模型4：赛程安排227 9.4.1问题分析227 9.4.2图论模型的建立228 9.4.3完美赛程的编制方法230 9.4.4其他问题233 9.5模型5：乒乓球比赛队员出场顺序安排233 9.5.1实力强弱的理解233 9.5.2模型的建立与求解234 9.6模型6：灾情巡视路线236 9.6.1问题假设237 9.6.2模型的建立与求解237 习题9241 参考文献244 |
精品新书
|
| ||||||
|
| ||||||
|
| ||||||
|
| ||||||
 |
 |
