图论简明教程

　　内容简介目录本书是一本通俗易懂的图论入门教材。全书共分11章，其中第1章回顾了图论所需的数学基础知识；第2章讲解了图论领域的各种基本概念；后面的8章讲解了几类特殊的图及应用，并给出了一些重要而常用的算法；最后一章讨论两个附加的专题：Ramsey理论和图支配。为了便于读者理解和掌握基本理论，书中不仅提供了丰富的例题，而且每节后配有大量习题，并在书的最后提供部分习题的答案。图论是一门应用范围非常广泛的科学。本书针对初学者编写，采用实例、示意图、课后练习等手段，逐步揭示图论中的典型问题、解决策略以及重要应用。本书具有系统性、理论性和实用性强的特点，可作为大专院校计算机科学、数学、社会科学、商学以及工程学等专业的教科书，亦可供其他科技工作者作为参考书目。本书起点低，不需要高等数学的知识，所以也可以作为中学生奥林匹克竞赛相关学科的课外读物。◆专门针对初学者编写◆使学生深刻领会图论的广泛用途◆将算法和图论有机结合起来译者序 当欧拉在1736年访问哥尼斯堡城时， 他发现当地有一条名叫普雷哥尔的河流横经城中， 在河上建有七座桥. 市民们正在从事一项非常有趣的消遣活动， 这项活动是在星期六进行的， 要求一次走过所有七座桥， 且每座桥只能经过一次， 而且起点与终点必须是同一地点. 这项活动难倒了许多人. 这类似于常见的"一笔画"问题. 欧拉证明了这是不可能完成的， 理由如下：除了起点以外， 每次画到一个点， 那么一定会离开这个点， 所以与该点相连的边数一定为偶数：由于最后必须回到起点， 所以与起点相连的边亦为偶数. 七桥所对应的图形中， 没有一点连有偶数条边， 因此上述的任务是不可能实现的. 此后， 欧拉发表了著名的论文《依据几何位置的解题方法》， 这是图论领域的第一篇论文， 标志着图论的诞生. 这种利用模型图来解决问题的方法在当时还只是个别现象……. 图论的真正发展始于二十世纪五六十年代， 这和计算机技术的发展是同步的. 由此也可以说， 图论是一门既古老又年轻的学科， 正日益显现出活力. 本书的英文原名是A friendly introduction to graph theory， 正如名称所表述的那样， 书中的内容通俗易懂， 对读者的基础知识要求不高， 各种概念十分清楚， 所有的证明和算法也都力求简洁明了. 此外， 虽是一本以理论为主的书， 但作者引用了大量现实生活的事例， 既使得内容趣味盎然， 又能引导读者理论联系实际. 总之， 这是一本出色的图论入门教材， 可以为读者打下良好的理论基础. 本书主要由李慧霸. 王凤芹翻译. 全书最后由李慧霸统稿. 在翻译过程中， 顾剑. 钟鸣. 吕雅帅. 王睿伯. 于潇. 孙元波. 万光宇给予我们很大的帮助， 在此特别感谢. 我们还要特别感谢严琰同志在这段时间对我们的支持和鼓励. 肖国尊负责本书翻译质量和进度的控制与管理. 在本书翻译过程中， 我们对书中的疏漏之处进行了更正. 此外， 对一些笔误和排版错误也进行了校正. 敬请各位读者就本书提供反馈意见， 我们希望通过读者的意见来了解自己的不足， 以求在今后的译作中更多地和更切实际地考虑读者的需要. 译者 Fred Buckley和Marty Lewinter分别任教于Baruch大学和Purchase大学， 他们的研究领域包括图论. 经典几何学. 数论以及数学史. 图论是一门极有趣味的学问， 其广阔的应用领域涵盖了人类学. 计算机科学. 化学. 环境保护. 流体动力学. 心理学. 社会学. 交通管理. 电信领域等等. 在20世纪， 随着运筹学的出现， 图论更是为确立其卓越的地位起到了十分重要的作用. 严格地讲， 图论是组合数学的一个分支， 例如， 它交叉运用了拓扑学. 群论和数论. 图论中定理和证明的难度高低不等， 有的简单易懂， 有的几乎不可理解， 然而图论终究还只是研究点和线的学问. 图论的应用非常广泛， 不仅局限于数学和计算机科学， 因此各专业的学生都应该打下一定的图论基础， 这样他们就会多掌握一种强大而灵活的工具来分析和处理自己学科领域中的问题. 这本教材主要面向本科水平的读者， 使他们能比较容易理解. 我们仅仅假设读者具有一定的代数基础， 因此， 本书敞开了一座大门， 无论数学. 计算机科学. 社会科学. 商学还是工程学专业的学生， 只要有需求， 你都能尽早地接触这个精彩而颇有裨益的研究领域. 虽然这是一本易懂的教材， 但读的时候还是应该拿上纸和笔：这不是睡前的休闲读物. 书中的习题有易有难， 能够体现相应章节的内容. 书后有解答或提示， 其涵盖了大部分的习题. 此外， 应该意识到， 数学不是一项观赏性质的体育赛事（当然当您看到有人对某个重要结论做出了简单得惊人的证明， 您也一定会觉得这是一件激动人心的事）， 请务必要做习题， 否则当您读到最后一章时， 第一章的内容就会被忘到脑后. 能够做完较难习题的勤勉的学生会得到很大益处：为今后的图论研究打下坚实基础， 他们也会有能力将图论的思想应用到纷乱复杂的现实问题中去. 在第1章， 我们讨论了必备的基础概念， 读者应该熟练掌握这些内容. 我们虽然称这一章为复习， 但其内容仍然十分完备， 提供了必要的数学工具来帮助读者理解全书其余部分的内容. 因此这一章讲了集合. 函数. 奇偶性. 数学归纳法. 证明技巧. 计数原理. 排列组合. Pascal三角形和组合恒等式. 对于不熟悉证明技巧的学生来说， 本章对他们会有很大的帮助. 而对于基础比较扎实的学生， 老师可有选择地跳过本章的部分甚至全部内容. 如前所述， 图论的应用极为广泛. 在第2章中， 我们将介绍图论中最基本的概念， 同时也将展示图论的一些应用领域. 当然， 我们也会在后面看到许多其他的应用. 有一类非常重要的图值得我们用单独的一章（第3章）来介绍， 这就是树. 由于结构简单， 树常常被用作新理论的试验场. 树的概念起源于许多领域， 例如分析商务层次. 求具有最小代价的运输网络等等， 此外树也是计算机科学中的一种十分重要的数据结构. 树是更大的一类图的特例， 这类图称作二分图. 在第3章中， 我们讲述了树. 二分图以及它们的应用. 最后， 本章以工作分配问题结束. 距离的概念在图论的理论和实践中应用很广泛， 许多有关图的操作都需要使用距离， 例如同构判定. 凸面问题. 另外， 距离也是许多对称概念的基础. 许多图中心的概念亦由距离来定义， 中心的概念在场地布局问题中起着关键的作用. 图论的众多算法都与距离相关， 这些算法往往需要在图中搜索各种长度的路. 距离也在连通性问题中扮演着重要的角色， 而连通性问题涉及到计算机网络的可靠性和健壮性问题， 因而占有十分关键的地位. 在第4章， 我们将讨论关于距离和连通性的一些重要概念和结论， 然后作为总结， 我们将解决一个场地布局问题， 并给出计算机网络的可靠性概念. 图论中许多的理论和实际问题都需要我们以某种方法遍历整个图. 例如在某些问题中， 我们的目标是求出一条迹或回路， 满足经过每条边一次且仅一次， 在另一些问题中， 我们可能需要求出一条路或圈， 满足经过每个结点一次且仅一次. 我们在第5章中讨论这些问题， 然后以两个著名的问题结束， 这两个问题是中国邮递员问题和旅行售货员问题. 许多由图论描述的现实问题都需要把结点集或边集划分为一些不相交的子集， 使同一子集中的所有元素互不相邻. 这类问题中比较常见的有：安排会议或考试的日程以免冲突， 还有安排化学品的存储以避免互相反应. 这些问题都与第6章的主题一图着色相关. 矩阵是由数字组成的矩形表. 在计算机中存储图的一种最简单的方法就是用矩阵， 或者说数组， 这是矩阵在计算机科学中的对应数据结构. 图论有效地利用了矩阵， 将其作为检测结构和其他性质的工具. 在第7章中， 我们首先复习了矩阵的一些基本概念， 然后讲述了矩阵在图论中的一些应用. 图论和计算机科学之间有着千丝万缕的联系， 因此算法在现代图论中占有举足轻重的地位， 以至好几本著作都专注于图的算法. 在第8章中， 我们将简单地介绍一下图论算法及其应用. 首先给出了重要的广度优先搜索和深度优先搜索算法， 然后考察了图着色和树编码算法， 其他一些算法也在行文中有所体现. 我们将不在这里考察算法的效率和NP完全性， 但是建议有兴趣的读者参考一下Buckley和Harary. Chartrand和Oellermann还有Gould对这些问题的讨论. 如果能在平面内将图画出且使其边各不相交叉， 那么这个图就是可平面化的. 可平面图曾经受到了多年的广泛关注， 其原因在于一个长期困惑人们的问题：四色猜想， 这个问题最终花费了一百多年的时间才得到证明. 时至今日， 可平面图在其应用领域仍然占有很重要的地位， 例如在运筹学中的场地布局， 或是计算机科学中的印刷电路板设计等问题中， 可平面图都起着至关重要的作用. 在第9章中我们就来讨论可平面图及其性质. 简单的图论模型不足以刻画某些现实问题， 我们已经见过不少这样的实例. 在第10章， 我们将考虑另一些结构. 有向图和图类似， 只是边有方向. 有些问题中， 流（信息. 交通. 液体. 电子等）的方向性比较重要， 有向图就是对这种问题建模的. 当有向边上存在流量的大小限制后， 就得到了网络. 一类特殊的没有圈的有向图称统筹图， 它的边上有权， 表示工作持续时间. 这种有向图用来安排复杂工程的各项工作. 在第10章， 将介绍不同种类的有向图及特点， 也将研究网络流问题并给出求最大流的算法， 最后讨论统筹图及其应用. 在第11章， 我们讨论了两个专题：Ramsey理论和图支配. 前者涉及图的边着色， 而后者则与距离和独立性有关， 并且有着广泛的应用. 这两个专题有一个共同之处， 那就是研究它们都很有趣. 我们衷心希望这本书将带来一个愉快的阅读过程， 正如我们愉快的写作过程一样. 第1章基础知识 1. 1数学预备知识 1. 1. 1取整运算 1. 1. 2奇偶性 1. 1. 3集合 1. 1. 4子集 1. 1. 5集合运算 1. 1. 6笛卡尔积 习题1. 1 1. 2数学归纳法 1. 2. 1数学归纳法 1. 2. 2第二数学归纳法 习题1. 2 1. 3排列组合 1. 3. 1排列 1. 3. 2组合 习题1. 3 1. 4Pascal三角形与组合恒等式 1. 4. 1递归式 1. 4. 2Pascal三角形行性质 1. 4. 3几个组合恒等式 习题1. 4 本章难题与工程 参考文献 推荐读物 第2章图的基本概念与应用 2. 1图论模型 2. 1. 1图 2. 1. 2数学模型 2. 1. 3在化学领域的应用 2. 1. 4商业应用：仓库／零售店问题 2. 1. 5应用：最短航线问题 2. 1. 6应用：冰淇淋车的路线图 2. 1. 7应用：旅行售货员问题 2. 1. 8应用：考试时间安排问题 2. 1. 9应用：一个任务分配模型 习题2. 1 2. 2子图与图的分类 2. 2. 1基本概念 2. 2. 2子图 2. 2. 3一些重要类型的图 习题2. 2 2. 3图的同构 2. 3. 1度序列 习题2. 3 2. 4图操作 2. 4. 1并与和 2. 4. 2边与结点的删除 2. 4. 3补图 2. 4. 4笛卡尔积 2. 4. 5超立方体 2. 4. 6网格 2. 4. 7线图 2. 4. 8边收缩 习题2. 4 参考文献 推荐读物 第3章树与二分图 3. 1树的性质 3. 1. 1树的一些性质 3. 1. 2树的度序列 3. 1. 3非同构树 3. 1. 4树的叶子数 3. 1. 5饱和烃 习题3. 1 3. 2最小生成树 3. 2. 1生成树 3. 2. 2生成树中的k-差结点 3. 2. 3最小代价生成树 习题3. 2 3. 3分图 习题3. 3 3. 4匹配与工作分配问题 3. 4. 1分图中的匹配 3. 4. 2最大匹配 3. 4. 3分图中的完全匹配 3. 4. 4相异代表系 3. 4. 5更一般的匹配 习题3. 4 参考文献 推荐读物 第4章距离与连通性 4. 1图的距离 4. 1. 1偏心距. 中心. 半径与直径 4. 1. 2树与距离 4. 1. 3树的中心 4. 1. 4自补图与距离 4. 1. 5树的重心 习题4. 1 4. 2图的连通性 4. 2. 1割点. 桥与连通性 4. 2. 2块 4. 2. 3Menger定理 习题4. 2 4. 3应用 4. 3. 1F-图 4. 3. 2网络可靠性 4. 3. 3简单的概率计算 习题4. 3 参考文献 推荐读物 第5章欧拉图与哈密顿图 5. 1欧拉图 5. 1. 1多重图 5. 1. 2哥尼斯堡七桥问题 习题5. 1 5. 2哈密顿图的性质 5. 2. 1哈密顿图 5. 2. 2哈密顿游戏 5. 2. 3哈密顿图的充分条件 5. 2. 4均匀连通图与哈密顿连通图 5. 2. 5网格与哈密顿图 5. 2. 6超立方体 习题5. 2 5. 3应用 5. 3. 1中国邮递员问题 5. 3. 2旅行售货员问题 习题5. 3 参考文献 推荐读物 第6章图着色 6. 1结点着色与独立集 6. 1. 1色数 6. 1. 2色数与独立性 6. 1. 3可惟一七着色图 习题6. 1 6. 2边着色 6. 2. 1边色数 6. 2. 2Kn中的单色三角形 习题6. 2 6. 3图着色的应用 习题6. 3 参考文献 推荐读物 第7章矩阵 7. 1矩阵的基本概念 7. 1. 1矩阵运算 7. 1. 2矩阵的乘法 习题7. 1 7. 2邻接矩阵 7. 2. 1一个简单的实例 7. 2. 2图的邻接矩阵 7. 2. 3关联矩阵 7. 2. 4不同类型图的邻接矩阵 7. 2. 5子阵和矩阵的块 习题7. 2 7. 3距离矩阵 7. 3. 1一个简单的实例 7. 3. 2由A推出D 7. 3. 3距离矩阵的图化 习题7. 3 参考文献 推荐读物 第8章图算法 8. 1图搜索 8. 1. 1广度优先搜索 8. 1. 2深度优先搜索 习题8. 1 8. 2图着色算法 8. 2. 1顺序着色 8. 2. 2最大色度着色 习题8. 2 8. 3树编码 Priifer编码 树的二进制编址 习题8. 3 参考文献 推荐读物 第9章可平面图 9. 1可平面性 9. 1. 1欧拉公式 9. 1. 2可平面图中的边数 9. 1. 3可平面图的特性 习题9. 1 9. 2可平面图， 图着色和镶嵌 9. 2. 1图与地图 9. 2. 2嵌入 习题9. 2 9. 3对偶图和可平面图的应用 9. 3. 1对偶性 9. 3. 2场地布局 习题9. 3 参考文献 推荐读物 第10章有向图与网络 10. 1有向图 10. 1. 1强有向化 10. 1. 2有向无圈图及偏序 10. 1. 3锦标赛 习题10. 1 10. 2网络 10. 2. 1网络中的距离 10. 2. 2网络流 10. 2. 3极小割和最小割 10. 2. 4最大流最小割定理 10. 2. 5求增流半路径 10. 2. 6网络. 匹配和连通性 习题10. 2 10. 3关键路径法 10. 3. 1统筹图 10. 3. 2关键路径法 习题10. 3 参考文献 推荐读物 第11章专题讨论 11. 1RAMSAY理论 11. 1. 1Ramsey定理 11. 1. 2一般化ramsey数 习题11. 1 11. 2图支配 11. 2. 1支配的概念 11. 2. 2覆盖. 支配和独立集 习题11. 2 参考文献 推荐读物 附录A部分习题答案 第1章 习题1. 1 习题1. 2 习题1. 3 习题1. 4 第2章 习题2. 1 习题2. 2 习题2. 3 习题2. 4 第3章 习题3. 1 习题3. 2 习题3. 3 习题3. 4 第4章 习题4. 1 习题4. 2 习题4. 2 第5章 习题5. 1 习题5. 2 习题5. 3 第6章 习题6. 1 习题6. 2 习题6. 3 第7章 习题7. 1 习题7. 2 习题7. 3 第8章 习题8. 1 习题8. 2 习题8. 3 第9章 习题9. 1 习题9. 2 习题9. 3 第10章 习题10. 1 习题10. 2 附录B本书符号列表

　　Fred Buckley和Marty Lewinter分别任教于Baruch大学和Purchase大学，他们的研究领域包括图论、经典几何学、数论以及数学史。

第1章  基础知识
 1. 1  数学预备知识
 1. 1. 1  取整运算
 1. 1. 2  奇偶性
 1. 1. 3  集合
 1. 1. 4  子集
 1. 1. 5  集合运算
 1. 1. 6  笛卡尔积
 习题1. 1
 1. 2  数学归纳法
 1. 2. 1  数学归纳法
 1. 2. 2  第二数学归纳法
 习题1. 2
 1. 3  排列组合
 1. 3. 1  排列
 1. 3. 2  组合
 习题1. 3
 1. 4  Pascal三角形与组合恒等式
 1. 4. 1  递归式
 1. 4. 2  Pascal三角形行性质
 1. 4. 3  几个组合恒等式
 习题1. 4
 本章难题与工程
 参考文献
 推荐读物
 第2章  图的基本概念与应用
 2. 1  图论模型
 2. 1. 1  图
 2. 1. 2  数学模型
 2. 1. 3  在化学领域的应用
 2. 1. 4  商业应用：仓库／零售店问题
 2. 1. 5  应用：最短航线问题
 2. 1. 6  应用：冰淇淋车的路线图
 2. 1. 7  应用：旅行售货员问题
 2. 1. 8  应用：考试时间安排问题
 2. 1. 9  应用：一个任务分配模型
 习题2. 1
 2. 2  子图与图的分类
 2. 2. 1  基本概念
 2. 2. 2  子图
 2. 2. 3  一些重要类型的图
 习题2. 2
 2. 3  图的同构
 2. 3. 1  度序列
 习题2. 3
 2. 4  图操作
 2. 4. 1  并与和
 2. 4. 2  边与结点的删除
 2. 4. 3  补图
 2. 4. 4  笛卡尔积
 2. 4. 5  超立方体
 2. 4. 6  网格
 2. 4. 7  线图
 2. 4. 8  边收缩
 习题2. 4
 参考文献
 推荐读物
 第3章  树与二分图
 3. 1  树的性质
 3. 1. 1  树的一些性质
 3. 1. 2  树的度序列
 3. 1. 3  非同构树
 3. 1. 4  树的叶子数
 3. 1. 5  饱和烃
 习题3. 1
 3. 2  最小生成树
 3. 2. 1  生成树
 3. 2. 2  生成树中的k-差结点
 3. 2. 3  最小代价生成树
 习题3. 2
 3. 3    分图
 习题3. 3
 3. 4  匹配与工作分配问题
 3. 4. 1  分图中的匹配
 3. 4. 2  最大匹配
 3. 4. 3  分图中的完全匹配
 3. 4. 4  相异代表系
 3. 4. 5  更一般的匹配
 习题3. 4
 参考文献
 推荐读物
 第4章  距离与连通性
 4. 1  图的距离
 4. 1. 1  偏心距. 中心. 半径与直径
 4. 1. 2  树与距离
 4. 1. 3  树的中心
 4. 1. 4  自补图与距离
 4. 1. 5  树的重心
 习题4. 1
 4. 2  图的连通性
 4. 2. 1  割点. 桥与连通性
 4. 2. 2  块
 4. 2. 3  Menger定理
 习题4. 2
 4. 3  应用
 4. 3. 1  F-图
 4. 3. 2  网络可靠性
 4. 3. 3  简单的概率计算
 习题4. 3
 参考文献
 推荐读物
 第5章  欧拉图与哈密顿图
 5. 1  欧拉图
 5. 1. 1  多重图
 5. 1. 2  哥尼斯堡七桥问题
 习题5. 1
 5. 2  哈密顿图的性质
 5. 2. 1  哈密顿图
 5. 2. 2  哈密顿游戏
 5. 2. 3  哈密顿图的充分条件
 5. 2. 4  均匀连通图与哈密顿连通图
 5. 2. 5  网格与哈密顿图
 5. 2. 6  超立方体
 习题5. 2
 5. 3  应用
 5. 3. 1  中国邮递员问题
 5. 3. 2  旅行售货员问题
 习题5. 3
 参考文献
 推荐读物
 第6章  图着色
 6. 1  结点着色与独立集
 6. 1. 1  色数
 6. 1. 2  色数与独立性
 6. 1. 3  可惟一七着色图
 习题6. 1
 6. 2  边着色
 6. 2. 1  边色数
 6. 2. 2  Kn中的单色三角形
 习题6. 2
 6. 3  图着色的应用
 习题6. 3
 参考文献
 推荐读物
 第7章  矩阵
 7. 1  矩阵的基本概念
 7. 1. 1  矩阵运算
 7. 1. 2  矩阵的乘法
 习题7. 1
 7. 2  邻接矩阵
 7. 2. 1  一个简单的实例
 7. 2. 2  图的邻接矩阵
 7. 2. 3  关联矩阵
 7. 2. 4  不同类型图的邻接矩阵
 7. 2. 5  子阵和矩阵的块
 习题7. 2
 7. 3  距离矩阵
 7. 3. 1  一个简单的实例
 7. 3. 2  由A推出D
 7. 3. 3  距离矩阵的图化
 习题7. 3
 参考文献
 推荐读物
 第8章  图算法
 8. 1  图搜索
 8. 1. 1  广度优先搜索
 8. 1. 2  深度优先搜索
 习题8. 1
 8. 2  图着色算法
 8. 2. 1  顺序着色
 8. 2. 2  最大色度着色
 习题8. 2
 8. 3  树编码
 Priifer编码
 树的二进制编址
 习题8. 3
 参考文献
 推荐读物
 第9章  可平面图
 9. 1  可平面性
 9. 1. 1  欧拉公式
 9. 1. 2  可平面图中的边数
 9. 1. 3  可平面图的特性
 习题9. 1
 9. 2  可平面图, 图着色和镶嵌
 9. 2. 1  图与地图
 9. 2. 2  嵌入
 习题9. 2
 9. 3  对偶图和可平面图的应用
 9. 3. 1  对偶性
 9. 3. 2  场地布局
 习题9. 3
 参考文献
 推荐读物
 第10章  有向图与网络
 10. 1  有向图
 10. 1. 1  强有向化
 10. 1. 2  有向无圈图及偏序
 10. 1. 3  锦标赛
 习题10. 1
 10. 2  网络
 10. 2. 1  网络中的距离
 10. 2. 2  网络流
 10. 2. 3  极小割和最小割
 10. 2. 4  最大流最小割定理
 10. 2. 5  求增流半路径
 10. 2. 6  网络. 匹配和连通性
 习题10. 2
 10. 3  关键路径法
 10. 3. 1  统筹图
 10. 3. 2  关键路径法
 习题10. 3
 参考文献
 推荐读物
 第11章  专题讨论
 11. 1  RAMSAY理论
 11. 1. 1  Ramsey定理
 11. 1. 2  一般化ramsey数
 习题11. 1
 11. 2  图支配
 11. 2. 1  支配的概念
 11. 2. 2  覆盖. 支配和独立集
 习题11. 2
 参考文献
 推荐读物
 附录A  部分习题答案
 第1章
 习题1. 1
 习题1. 2
 习题1. 3
 习题1. 4
 第2章
 习题2. 1
 习题2. 2
 习题2. 3
 习题2. 4
 第3章
 习题3. 1
 习题3. 2
 习题3. 3
 习题3. 4
 第4章
 习题4. 1
 习题4. 2
 习题4. 2
 第5章
 习题5. 1
 习题5. 2
 习题5. 3
 第6章
 习题6. 1
 习题6. 2
 习题6. 3
 第7章
 习题7. 1
 习题7. 2
 习题7. 3
 第8章
 习题8. 1
 习题8. 2
 习题8. 3
 第9章
 习题9. 1
 习题9. 2
 习题9. 3
 第10章
 习题10. 1
 习题10. 2
 附录B  本书符号列表