演算法观点的图论

点击数:15 借阅数: 2

作者:张镇华著

出版社:国立台湾大学出版中心出版 国立台湾大学发行

出版年:2017

出版地:台北市

格式:PDF

ISBN:978-986-350-258-6 ; 986-350-258-8

内容简介

图论(Graph Theory)起源于1736年Leonhard Euler解答七桥问题的一篇文章,经过两百年的孕育,1936年Kőnig写出第一本图论专书,正式宣告这门学问诞生。此后,随着生产管理、军事、交通运输、电脑和通讯网路等各领域的应用需求,图论呈现爆炸性的发展。
 
在图论的各种研究方法中,较重要的有拓朴方法、机率方法、代数方法、演算法。有效的演算法能协助电脑达到快速计算,对实用端有很大的好处。从数学的观点来看,演算法其实是数学归纳法的化身,所以它可以用来帮忙证明定理;反过来说,一些定理的归纳法证明,也常能转化成演算法。本书在各处尽可能地展现数学归纳法和演算法的一体两面特性。
 
全书分为两部分,第一部分包含树图、匹配、连通度、平面图、图着色等图论的基础知识;第二部分则包含一些著名的专题,例如完美图、Ramsey理论、极值图论、拟阵理论等。适合相关领域教师授课时使用,亦可提供有兴趣的读者作为参考之用。

作者简介
 
张镇华
 
1952年生于南投县草屯镇;1982年取得康乃尔大学运筹学博士学位;1983年回国,先后任教于中央大学数学系、交通大学应用数学系、台湾大学数学系;2017年退休。主要研究领域在离散数学及组合最优化,特别是图论及其演算法,发表的两百多篇论文涵盖图的控制集、图着色、群试理论等。

  • 序(第5页)
  • 目录(第9页)
  • 图目录(第13页)
  • 符号表(第18页)
  • 第一部 基础篇(第21页)
  • 1.1. 图论缘起——话说1736 年(第23页)
  • 第1章 通论(第23页)
  • 1.2. 图的定义(第26页)
  • 1.3. 路径(第31页)
  • 1.4. Euler 图(第35页)
  • 1.5. Euler 回路的应用(第39页)
  • 1.6. 度序列(第42页)
  • 1.7. 证明Brouwer 定点定理(第47页)
  • 1.8. 习题(第50页)
  • 1.9. 参考文献(第53页)
  • 2.1. 演算法起源(第57页)
  • 第2章 演算法简介(第57页)
  • 2.2. 演算法的复杂度(第58页)
  • 2.3. 资料结构(第64页)
  • 2.4. 表列和图的表示法(第69页)
  • 2.5. Euler 回路的案例(第73页)
  • 2.6. 联集寻找问题(第76页)
  • 2.7. 习题(第79页)
  • 2.8. 参考文献(第82页)
  • 3.1. 树是简单但重要的图(第85页)
  • 第3章 树(第85页)
  • 3.2. 树的基本性质(第87页)
  • 3.3. 树的中心问题(第91页)
  • 3.4. 树或图的遍历搜寻法(第95页)
  • 3.5. 生成树计数(第99页)
  • 3.6. 最小生成树(第105页)
  • 3.7. 习题(第110页)
  • 3.8. 参考文献(第113页)
  • 4.1. 婚姻问题面面观(第117页)
  • 第4章 匹配(第117页)
  • 4.2. 匹配和完美匹配(第119页)
  • 4.3. 二分图匹配(第123页)
  • 4.4. 加权二分图匹配(第131页)
  • 4.5. 一般图匹配(第135页)
  • 4.6. Edmonds 花被演算法(第138页)
  • 4.7. 稳定婚姻问题(第142页)
  • 4.8. 习题(第145页)
  • 4.9. 参考文献(第149页)
  • 5.1. 团结在一起(第153页)
  • 第5章 图的连通度(第153页)
  • 5.2. 连通度和边连通度(第154页)
  • 5.3. 2-连通图(第160页)
  • 5.4. k-连通图和Menger定理(第166页)
  • 5.5. 最小连通图(第170页)
  • 5.6. 网路流问题(第173页)
  • 5.7. 习题(第177页)
  • 5.8. 参考文献(第180页)
  • 第6章 平面图(第183页)
  • 6.1. 老死不相往来的誓言(第183页)
  • 6.2. 平面图(第184页)
  • 6.3. Euler 多面体公式(第189页)
  • 6.4. Kuratowski定理(第193页)
  • 6.5. 外围平面图(第199页)
  • 6.6. 平面程度的度量(第202页)
  • 6.7. 习题(第209页)
  • 6.8. 参考文献(第212页)
  • 第7章 图着色(第215页)
  • 7.1. 地图着色(第215页)
  • 7.2. 点着色数和它的上界(第218页)
  • 7.3. 点着色数的下界(第221页)
  • 7.4. 平面图着色(第225页)
  • 7.5. 边着色(第232页)
  • 7.6. 列表着色(第239页)
  • 7.7. 习题(第243页)
  • 7.8. 参考文献(第248页)
  • 第8章 Hamilton 圈(第253页)
  • 8.1. 环游世界(第253页)
  • 8.2. 有Hamilton圈的必要条件(第255页)
  • 8.3. 有Hamilton圈的充分条件(第257页)
  • 8.4. 平面图的Hamilton圈(第262页)
  • 8.5. 有向图的Hamilton圈(第265页)
  • 8.6. 推销员问题(第267页)
  • 8.7. 习题(第269页)
  • 8.8. 参考文献(第273页)
  • 第二部专题篇(第277页)
  • 9.1. Shannon 零错容量(第279页)
  • 第9章 完美图(第279页)
  • 9.2. 完美图定义和猜想(第282页)
  • 9.3. 可比图:第一类传统完美图(第284页)
  • 9.4. 弦图:第二类传统完美图(第287页)
  • 9.5. 检验弦图(第291页)
  • 9.6. 完美图定理(第294页)
  • 9.7. 通往强完美图定理的道路(第297页)
  • 9.8. 习题(第302页)
  • 9.9. 参考文献(第304页)
  • 10.1. 幸福结局问题(第307页)
  • 第10章 Ramsey理论(第307页)
  • 10.2. 第二层Ramsey数(第310页)
  • 10.3. Ramsey定理(第316页)
  • 10.4. 图Ramsey数(第320页)
  • 10.5. 任意长度等差数列(第322页)
  • 10.6. 证明van der Waerden定理(第328页)
  • 10.7. 习题(第332页)
  • 10.8. 参考文献(第334页)
  • 11.1. 令人疯狂的乐趣(第337页)
  • 第11章 极值图论(第337页)
  • 11.2. 禁用完全图(第338页)
  • 11.3. 禁用完全二分图(第343页)
  • 11.4. 禁用完全多分图(第347页)
  • 11.5. 禁用路径图(第350页)
  • 11.6. 禁用圈图(第355页)
  • 11.7. 习题(第356页)
  • 11.8. 参考文献(第358页)
  • 12.1. 计数的艺术(第361页)
  • 第12章 机率方法(第361页)
  • 12.2. 机率空间(第363页)
  • 12.3. 期望值(第367页)
  • 12.4. 更动法(第370页)
  • 12.5. 二阶矩法和门槛函数(第374页)
  • 12.6. 局部引理(第376页)
  • 12.7. 习题(第380页)
  • 12.8. 参考文献(第383页)
  • 第13章 代数方法(第385页)
  • 13.1. 图论和代数关系密切(第385页)
  • 13.2. 图的特征值(第387页)
  • 13.3. 图参数和特征值的关系(第391页)
  • 13.4. 特殊图的特征值(第395页)
  • 13.5. 强正则图(第400页)
  • 13.6. 组合零点定理(第404页)
  • 13.7. 习题(第409页)
  • 13.8. 参考文献(第411页)
  • 第14章 拟阵(第413页)
  • 14.1. 拟阵起源(第413页)
  • 14.2. 继承系统(第414页)
  • 14.3. 拟阵基本性质(第419页)
  • 14.4. 对偶拟阵(第424页)
  • 14.5. 拟阵和平面图(第428页)
  • 14.6. 拟阵相交(第430页)
  • 14.7. 拟阵和(第432页)
  • 14.8. 习题(第435页)
  • 14.9. 参考文献(第437页)
  • 第15章 NP-完全问题(第441页)
  • 15.1. 难中之难、无过此难(第441页)
  • 15.2. Turing机器(第443页)
  • 15.3. Cook定理(第446页)
  • 15.4. 点覆蓋、独立集和点团(第451页)
  • 15.5. 路径和圈(第453页)
  • 15.6. 着色问题(第457页)
  • 15.7. 习题(第462页)
  • 15.8. 参考文献(第464页)
  • 索引(第465页)