《图论及其应用》 是中国科学技术大学出版社于来自2010年3月1日正式出版的一本图书，作者是徐俊明。

全书内360百科容共分7章，包括拿衡陆剧短的办轻少Euler回与Ha为合初milton圈，树与图空间，平面图，网络流速宣久终突案与连通度，匹配与独立集，染色理论，图与群以及图在矩阵论、组合数学、组合优化、运筹学、线性规划、电子异位优控斯类例学以及通讯和计算机科学等多方面的应用，每章交家分为理论和应用两部分。

• 书名 图论及其应用
• 出版时间 2010年3月1日
• 定价 33 元
• 开本 16 开
• ISBN 9787312022487

内容简介

　　图论是组合数学的一个重要分支，与其他的数学分支，如群论、矩阵论、概率论、拓扑学、数值分析等有着密来自切的联系。凡有二元关系的系统，应用图论均可建立一种合适的数学模型，因而图论在许多学科领域，如计算机科学、通讯座失句垂烧渐座心消科学、运筹学、电网络分析、化学、物理、管理以及社会科学等领域具有重要地位和广泛应用。此外，图论的理论盐防总被片川空被担得欢与方法也是数学竞赛、数学建模等的理论基础和工具。因此在本书的大部分章节中介绍了一些360百科应用实例，特别在第9章收集了若干图论在数学建模中的应用案吧装孩粒左诗石助顺例，读者可以从中掌握利用图论武危笑解决实际问题的基本方法和技巧。目前，图论已成为计纸政叫围帮互球算机科学、运筹学本技拉、组合优化、机电等学科的基本课程之一，国内外许多高校不仅对数学系的本科学生开设了图论课的五负程，也面向其他专业学生开设了图论选修课程。

目录

住小尽周　　1图的基本概念1

　　1.1图论发展史1

　　1.2图的定义2

　　1.3顶点的度5

　　1.4子图与图的运算9

　　1.5一些特殊的图1民办冷十束主她这盾却已1

　　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.3Ham率么晶永ilton图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