图论导引-(第二版)

内容简介

    本书系统地介绍了图论的基本概念、基本定理和算法，同时还介绍了一些悬而未决的图论问题和图论的新研究成果，旨在帮助读者理解并掌握图的结构和解决图论问题的技巧。全书包含８章和７个附录。第１～４章介绍图的概念、树和距离、匹配问题和图的分解问题、图的连通性等基本内容；第５～８章分别介绍了组合图论、拓扑图论的知识，图论中的边和环，以及图论的其他主题。书中配有大量例题和超过１２００道习题，使读者容易理解书中的概念和定理，并掌握证明技巧。本书内容丰富，具有很多可选择阅读的章节，可以供不同层次的读者使用。

目录

第1章  基本概念<br/>
11  什么是图<br/>
1.1.1  定义<br/>
1.1.2  图模型<br/>
1.1.3  矩阵与同构<br/>
1.1.4  分解和特殊图<br/>
1.1.5  习题<br/>
12  路径、 环和迹<br/>
1.2.1  图的连通<br/>
1.2.2  二分图<br/>
1.2.3  欧拉回路<br/>
1.2.4  习题<br/>
13  顶点度和计数<br/>
1.3.1  计数和双射<br/>
1.3.2  极值问题<br/>
1.3.3  图解序列<br/>
1.3.4  习题<br/>
14  有向图<br/>
1.4.1  定义和例子<br/>
1.4.2  顶点度<br/>
1.4.3  欧拉有向图<br/>
1.4.4  定向图和竞赛图<br/>
1.4.5  习题<br/>
第2章  树和距离<br/>
21  基本性质<br/>
2.1.1  树的性质<br/>
2.1.2  树和图中的距离<br/>
2.1.3  不相交生成树（选学）<br/>
2.1.4  习题<br/>
22  生成树和枚举<br/>
2.2.1  树的枚举<br/>
2.2.2  图的生成树<br/>
2.2.3  分解和优美标记<br/>
2.2.4  分叉与欧拉有向图<br/>
（选学）<br/>
2.2.5  习题<br/>
23  优化和树<br/>
2.3.1  生成树<br/>
2.3.2  路径<br/>
2.3.3  计算机科学中的树<br/>
（选学）<br/>
2.3.4  习题<br/>
第3章  匹配和因子<br/>
31  匹配与覆盖<br/>
3.1.1  匹配<br/>
3.1.2  Hall匹配条件<br/>
3.1.3  定理<br/>
3.1.4  独立集与覆盖<br/>
3.1.5  支配集(选学)<br/>
3.1.6  习题<br/>
32  算法及应用<br/>
3.2.1  二分匹配<br/>
3.2.2  加权二分匹配<br/>
3.2.3  稳定匹配（选学）<br/>
3.2.4  快速二分匹配（选学）<br/>
3.2.5  习题<br/>
33  一般图中的匹配<br/>
3.3.1  Tutte 1因子定理<br/>
3.3.2  图的f因子（选学）<br/>
3.3.3  Edmonds开花算法<br/>
（选学）<br/>
3.3.4  习题<br/>
第4章  连通度和路径<br/>
41  割与连通度<br/>
4.1.1  连通度<br/>
4.1.2  边连通度通常<br/>
4.1.3  块<br/>
42  k通图<br/>
4.2.1  2连通图<br/>
4.2.2  有向图的连通度<br/>
4.2.3  k通图与k边连通图<br/>
4.2.4  Menger定理的应用<br/>
4.2.5  习题<br/>
43  网络流问题<br/>
4.3.1  网络流<br/>
4.3.2  整数流<br/>
4.3.3  供应与需求(选学)<br/>
4.3.4  习题<br/>
第5章  图的着色<br/>
51  顶点着色和上界<br/>
5.1.1  定义和实例<br/>
5.1.2  上界<br/>
5.1.3  Brooks定理<br/&

摘要与插图

译  者  序
1736年， 瑞士数学家L.Euler在他的一篇论文中讨论了Knigsberg七桥问题， 由此产生了一个全新的数学分支——图论（graph theory）。在经历了200多年的发展之后， 图论已经积累了大量的理论和结果， 其应用领域也逐步扩大。， 图论主要用来讨论游戏中遇到的问题；19世纪晚期，  图论已经被用来研究电网络方程组和有机化学中的分子结构；  20世纪中叶以后， 借助于计算机，  图论又被用来求解生产管理、 军事、 交通运输、 计算机和通信网络等领域中的许多离散性问题， 同时图论中一些问题也借助于计算机得到了证明。如今，  图论本身及其在物理、 化学、 运筹学、 计算机科学、 电子学、 信息论、 控制论、 网络理论、 社会科学和管理科学等领域中的应用越来越受到人们的重视。因此， 作为理工科相关专业的学生， 全面系统地学习图论中的概念、 基本定理和算法， 并了解图论中一些悬而未决的问题是十分必要的。本书为学习和掌握这些知识提供了一部的教科书。
本书由Douglas B.West教授所著。Douglas B.West教授是Illinois大学数学系的教授， 长期从事图论理论和组合优化方面的研究工作。他的其他著作， 如Mathematical Thinking: ProblemSolving and Proofs，Combinatorial Mathematics和The Art of Combinatorics， 也深受读者的喜爱。本书一直是Illinois大学数学系本科生和研究生图论课程的教科书。本书的翻译和出版， 对于国内读者学习并应用图论知识具有重要意义。有幸承担该书的翻译工作， 我们感到十分荣幸。
本书旨在介绍图论的基本概念、基本定理和算法， 帮助读者理解掌握图的结构和解决图论问题的技巧。本书在系统介绍图论的基本概念、基本定理和算法的同时， 还介绍了一些悬而未决的图论问题， 并配置了大量的例题和习题。图论中许多问题都有多个证明， 作者对这些证明进行了精心选择。纵观全书， 作者深入浅出、全面地介绍了图论的证明技巧。证明与应用实例并举是本书的一个重要特点， 使读者容易理解书中的概念和定理。该书配置了大量习题， 总量超过1200道。通过这些习题， 读者可以深刻理解图论的基本概念和证明技巧， 并能够学习到正文未包括的知识。
与其他图论教材相比， 本书包含了更多的基本内容， 具有更多可供选择阅读的章节， 包含了更多的新研究结果和悬而未决的问题， 并且强调图论论证方法的学习和掌握。基本内容可以帮助读者建立图论的知识框架， 掌握图论的基本证明方法。选读内容是对基本知识的有益补充和延伸， 而的研究成果和悬而未决的问题则可以帮助读者接触图论研究的前沿。因此，本书可供不同层次的读者使用。它可以作为高等院校数学系本科生、 研究生， 计算机专业和其他专业研究生的图论课程教材， 也可以作为有关教师和工程技术人员参考书。
本书由哈尔滨工业大学骆吉洲和李建中合作翻译完成。译者在深刻理解本书的基础上力求准确， 对于发现的多处笔误和印刷错误，在翻译时进行了更正。在本书的翻译过程中， 译者得到了多位同事和朋友的帮助， 他们提出了很多中肯的意见和建议， 使译者受益良多。在此一并致谢！ 同时也向提出宝贵意见的所有读者表示感谢。
限于水平， 译文中疏漏和错误难免， 敬请读者批评指正。如有任何建议， 请发送邮件至luojizhou@hit.edu.cn。前    言
前    言
图论是训练离散数学证明技巧的乐园， 其结果在计算科学、社会科学和自然科学等各个领域具有广泛应用。本书为本科生或研究生提供了一个或两个学期的图论课程内容。本书不要求任何图论的预备知识。尽管本书包含了许多算法和应用， 但