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

本书系统地介绍了图论的基本概念、基本定理和算法，同时还介绍了一些悬而未决的图论问题和图论的新研究成果，旨在帮助读者理解并掌握图的结构和解决图论问题的技巧。

本书作者是Illinois大学数学系的资深教授Douglas B. West。他长期从事图论理论和组合优化方面的研究工作，发表论文100多篇。他的其他著作，如《Mathematical Thinking: Problem-Solving and Proofs》、《Combinatorial Mathematics》和《The Art of Combinatorics》，也深受读者的喜爱。本书出版于20世纪90年代末，是一部图论方面的优秀教材，一直是Illinois大学数学系本科生和研究生图论课程的教科书。

第1章 基本概念
1.1 什么是图
1.1.1 定义
1.1.2 图模型
1.1.3 矩阵与同构
1.1.4 分解和特殊图
1.1.5 习题
1.2 路径、 环和迹
1.2.1 图的连通
1.2.2 二分图
1.2.3 欧拉回路
1.2.4 习题
1.3 顶点度和计数
1.3.1 计数和双射
1.3.2 极值问题 第1章 基本概念
  1.1 什么是图
    1.1.1 定义
    1.1.2 图模型
    1.1.3 矩阵与同构
    1.1.4 分解和特殊图
    1.1.5 习题
  1.2 路径、 环和迹
    1.2.1 图的连通
    1.2.2 二分图
    1.2.3 欧拉回路
    1.2.4 习题
  1.3 顶点度和计数
    1.3.1 计数和双射
    1.3.2 极值问题
    1.3.3 图解序列
    1.3.4 习题
  1.4 有向图
    1.4.1 定义和例子
    1.4.2 顶点度
    1.4.3 欧拉有向图
    1.4.4 定向图和竞赛图
    1.4.5 习题
第2章 树和距离
  2.1 基本性质
    2.1.1 树的性质
    2.1.2 树和图中的距离
    2.1.3 不相交生成树（选学）
    2.1.4 习题
  2.2 生成树和枚举
    2.2.1 树的枚举
    2.2.2 图的生成树
    2.2.3 分解和优美标记
    2.2.4 分叉与欧拉有向图（选学）
    2.2.5 习题
  2.3 优化和树
    2.3.1 最小生成树
    2.3.2 最短路径
    2.3.3 计算机科学中的树（选学）
    2.3.4 习题
第3章 匹配和因子
  3.1 匹配与覆盖
    3.1.1 最大匹配
    3.1.2 Hall匹配条件
    3.1.3 最小最大定理
    3.1.4 独立集与覆盖
    3.1.5 支配集(选学)
    3.1.6 习题
  3.2 算法及应用
    3.2.1 最大二分匹配
    3.2.2 加权二分匹配
    3.2.3 稳定匹配（选学）
    3.2.4 快速二分匹配（选学）
    3.2.5 习题
  3.3 一般图中的匹配
    3.3.1 Tutte 1-因子定理
    3.3.2 图的f-因子（选学）
    3.3.3 Edmonds开花算法（选学）
    3.3.4 习题
第4章 连通度和路径
  4.1 割与连通度
    4.1.1 连通度
    4.1.2 边连通度通常
    4.1.3 块
  4.2 k-通图
    4.2.1 2.连通图
    4.2.2 有向图的连通度
    4.2.3 k.通图与k.边连通图
    4.2.4 Menger定理的应用
    4.2.5 习题
  4.3 网络流问题
    4.3.1 最大网络流
    4.3.2 整数流
    4.3.3 供应与需求(选学)
    4.3.4 习题
第5章 图的着色
  5.1 顶点着色和上界
    5.1.1 定义和实例
    5.1.2 上界
    5.1.3 Brooks定理
    5.1.4 习题
  5.2 k-色图的构造
    5.2.1 大色数图
    5.2.2 极值问题与Turan定理
    5.2.3 颜色临界图
    5.2.4 强制细分
    5.2.5 习题
  5.3 计数方面的问题
    5.3.1 真着色的计数
    5.3.2 弦图
    5.3.3 完美图点滴
    5.3.4 环定向的计数(选学)
    5.3.5 习题
第6章 可平面图
  6.1 嵌入与欧拉公式
    6.1.1 平面作图
    6.1.2 对偶图
    6.1.3 欧拉（Euler）公式
    6.1.4 习题
  6.2 可平面图的特征
    6.2.1 Kuratowski定理的预备知识
    6.2.2 凸嵌入
    6.2.3 可平面性的测试(选学)
    6.2.4 习题
  6.3 可平面性的参数
    6.3.1 可平面图的着色
    6.3.2 交叉数
    6.3.3 具有更高亏格的表面(选学)
    6.3.4 习题
第7章 边和环
  7.1 线图与边着色
    7.1.1 边着色
    7.1.2 线图的性质(选学)
    7.1.3 习题
  7.2 哈密顿环
    7.2.1 必要条件
    7.2.2 充分条件
    7.2.3 有向图中的环(选学)
    7.2.4 习题
  7.3 可平面性、 着色与环
    7.3.1 Tait定理
    7.3.2 Grinberg定理
    7.3.3 鲨鱼图(选学)
    7.3.4 流与环覆盖(选学)
    7.3.5 习题
第8章 其他主题
  8.1 完美图
    8.1.1 完全图定理
    8.1.2 弦图的再研究
    8.1.3 其他完美图类
    8.1.4 非完美图
    8.1.5 强完美图猜想
    8.1.6 习题
  8.2 拟阵
    8.2.1 遗传系统及示例
    8.2.2 拟阵的性质
    8.2.3 生成函数
    8.2.4 拟阵的对偶
    8.2.5 拟阵的子式与可平面对偶
    8.2.6 拟阵的交
    8.2.7 拟阵的并
    8.2.8 习题
  8.3 拉姆齐理论
    8.3.1 鸽巢原理的再研究
    8.3.2 拉姆齐(Ramsey)定理
    8.3.3 拉姆齐数
    8.3.4 图的拉姆齐理论
    8.3.5 Sperner引理和带宽
    8.3.6 习题
  8.4 其他极值问题
    8.4.1 图的编码
    8.4.2 分叉和流言
    8.4.3 序列着色和可选择性
    8.4.4 由路径和环构成的划分
    8.4.5 周长
    8.4.6 习题
  8.5 随机图
    8.5.1 存在性和数学期望
    8.5.2 几乎所有图均具有的性质
    8.5.3 阈值函数
    8.5.4 图的演变和图的参数
    8.5.5 连通度、 团和着色
    8.5.6 鞅
    8.5.7 习题
  8.6 图的特征值
    8.6.1 特征多项式
    8.6.2 线性代数和实对称阵
    8.6.3 特征值和图参数
    8.6.4 正则图的特征值
    8.6.5 特征值与扩张图
    8.6.6 强正则图
    8.6.7 习题
附录A 数学基础
附录B 最优化和复杂度
附录C 部分习题提示
附录D 术语表
附录E 补充阅读
附录F 参考文献
附录G 术语对照表

　　刘茂红所著的《中国互联网产业组织实证研究》从网络经济发展入手，在借鉴研究中国工业集中度决定因素的基础上，通过文献分析和逻辑推理，解决了中国网络经济发展中的一系列实证性问题。本文条理清晰，说理明确，运用的数据及模型都能直观的体现中国互联网产业的市场行为，为我国网络经济的发展奠定了理论与实证基础。译  者  序
　　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道。通过这些习题， 读者可以深刻理解图论的基本概念和证明技巧， 并能够学习到正文未包括的知识。
　　与其他图论教材相比， 本书包含了更多的基本内容， 具有更多可供选择阅读的章节， 包含了更多的新研究结果和悬而未决的问题， 并且特别强调图论论证方法的学习和掌握。基本内容可以帮助读者建立图论的知识框架， 掌握图论的基本证明方法。选读内容是对基本知识的有益补充和延伸， 而最新的研究成果和悬而未决的问题则可以帮助读者接触图论研究的前沿。因此，本书可供不同层次的读者使用。它可以作为高等院校数学系本科生、 研究生， 计算机专业和其他专业研究生的图论课程教材， 也可以作为有关教师和工程技术人员参考书。
　　本书由哈尔滨工业大学骆吉洲和李建中合作翻译完成。译者在深刻理解本书的基础上力求准确， 对于发现的多处笔误和印刷错误，在翻译时进行了更正。在本书的翻译过程中， 译者得到了多位同事和朋友的帮助， 他们提出了很多中肯的意见和建议， 使译者受益良多。在此一并致谢！ 同时也向提出宝贵意见的所有读者表示感谢。
　　限于水平， 译文中疏漏和错误难免， 敬请读者批评指正。
　　前    言
　　图论是训练离散数学证明技巧的乐园， 其结果在计算科学、社会科学和自然科学等各个领域具有广泛应用。本书为本科生或研究生提供了一个或两个学期的图论课程内容。本书不要求任何图论的预备知识。尽管本书包含了许多算法和应用， 但重点是理解图的结构和分析图论问题的技巧。
　　目前已经有许多图论的教科书。由J.A.Bondy和U.S.R.Murty撰写的经典教材《图论及应用》（Graph Theory with Applications,Macmillan/NorthHolland\[1976\]）突出了证明和应用两个方面， 故本书的原型参照了该书。图论至今仍是一个年轻的学科， 应该如何介绍图论的知识， 大家仍然没有一致的看法。内容的选择和顺序的安排， 证明方法的选择， 目标的选择， 习题的选择等一直是有争议问题。对本书多次修改使我懂得了对于上述问题做出决策是多么得困难。本书是我对上述有争议问题的一点贡献。
　　关于第二版
　　第二版的修订采用了更简洁的行文方式， 以方便学生学习和教师教学。全书总体内容没有太大变化， 只是对内容的表述方式做了修改， 使其更易理解， 这一点在本书的前几部分尤其明显。有关第二版的变化， 稍后将详细论述， 在此仅做一个概述。
　　● 必修内容中出现的选修内容现在用“*”号区分。这些内容不会在后续内容中使用， 因而可以跳过。忽略多数选修内容以后， 本书可以作为一学期的图论教学内容。当某一小节被标记为“可选”时， 该小节的全部内容都是选修的， 这时不再标记该小节中的各个项。
　　● 对于缺乏基础知识的学生， 附录A概述了有关集合、逻辑、归纳法、计数、二项式系数、关系和鸽巢原理等方面的相关知识。
　　● 重新叙述和分析了很多证明， 并增加了更多的例子。
　　● 增加了350多道习题， 其中多数是第1～7章中比较容易的题目。这样， 本书的总习题量超过了1200道。
　　● 增加了100多幅插图。本书的插图总量超过了400幅。为区别插图中包括的几种类型的边框， 本书把原有的实线和虚线改变为粗线和实线， 提高了插图的清晰度。
　　● 相对简单的问题都集中放在各节习题的前面部分， 用来作为热身练习。一些习题被改写， 使其语义更清楚。
　　● 对习题的提示做了补充， 增加了一个“部分习题提示”的附录。
　　● 为了易于查找， 在附录D中给出了全书的术语表。
　　● 有关欧拉回路、有向图和Turn定理的内容被重新编排， 以提高学习的效率。
　　● 第6章和第7章调换了顺序以便先介绍平面性的思想。与复杂性有关的部分改编为附录。
　　● 改正了专业术语中的错误， 并更加强调与本书内容直接相关的术语。
　　本书特点
　　本书特点就是使学生能够深入理解本书的内容。本书包括对证明技巧的讨论、 1200多道习题、 400多幅插图以及许多例子。本书正文中出现的结论都有详细完整的证明。
　　很多本科学生在开始学习图论前都很少涉足证明技巧， 附录A提供的背景阅读材料有助于初学者。如果初学者在理解和书写证明时有困难， 应该结合第1章仔细阅读附录A。虽然本书前面的一些章节仍然讨论了一些证明技巧（特别是归纳法）， 但是更多的背景知识已经放到附录A中。
　　多数的习题需要证明。很多本科学生在论证问题方面的实践不足， 这将影响他们对于图论和其他数学知识的兴趣。抛开数学而言， 论证问题方面的智能训练也是极其重要的。我希望学生喜欢这种训练。学生在求解问题时， 应该注意语言的使用（“说出的即是你要表达的”）， 而且表达准确（“表达的即是你要说出的”）。
　　虽然图论中许多名词本身就表明了它们各自的定义， 但太多的专业术语定义会阻碍阅读的流畅性。数学家喜欢一开始就给出一系列的定义。但学生们大都愿意在熟练掌握一个概念后再去接受下一个概念， 这样他们会学得更好。学生的这个意愿和审稿者的建议使我推迟了很多定义的给出， 直到需要的时候。例如， 笛卡儿积的定义出现在5.1节的着色问题部分， 线图的定义则分别出现在4.2节的Menger定理部分和7.1节的边着色部分， 诱导子图的定义和连接的定义分别被推迟到1.2节和3.1节。
　　书中将有向图的介绍推迟到1.4节。如果在介绍图的同时介绍有向图， 会使学生产生迷惑。在第1章的最后介绍有向图比较容易学习， 能够在了解两种图的差别的同时加强对基本概念的理解。在连通性问题上， 本书仍将这两个模型放在一起讨论。
　　本书比其他图论书籍包含了更多的内容。作为“其他主题”的可选择章节， 最后一章聚集很多图论的新的研究结果， 使得本书能供不同层次的读者使用。本科生的教学内容可以由前7章组成（去掉大部分选修内容）， 第8章可作为有兴趣的学生的主题阅读材料。研究生的教学内容可以如下构成： 第1章和第2章作为推荐阅读材料， 在课堂上快速进入第3章， 并讲授第8章的一些主题内容。第8章及前面章节的选修内容也可作为高级图论课程的基本内容。
　　图论中很多结果都存在多种证明， 这将有助于提高学生采用多种方法处理问题的灵活性。对于同一个问题， 本书可能在注记中谈及一些不同的证明方法， 另外一些留作练习。
　　很多习题都有提示， 一些提示在习题中直接给出， 另一些在附录C中给出。标记了“－”的问题比较简单， 标记了“＋”的问题将比较难。标记了“+”的问题不应该作为本科学生的作业。标记了“！”的问题特别有价值和启发性。标记了“*”的问题将涉及可选内容。
　　每组习题都以标记“－”的习题开始， 根据相关章节内容的先后顺序排列。这些习题的结束由一组点标记。这部分习题要么是检查对概念的理解， 要么是对这部分内容的结论的直接应用。作者在课堂上推荐做一些这样的练习作为热身， 在完成主要作业题（多数这样的习题标记了“！”）之前检查学生对基本概念的理解。多数标记“－”的问题是很好的考试题。如果在考试中使用其他习题， 从附录C中提供一些提示是很好的做法。
　　涉及多个概念的习题出现在最后一个相关概念介绍完之后。正文中一个概念介绍完后有时会有指针指向与该概念相关的习题， 全书有很多这样的指针。每小节对本节习题的引用仅由该习题的相应编号给出， 对其他习题的交叉引用将通过其章、节和习题编号给出。
　　内容组织和修改
　　在第一版中， 我力求内容的承接关系以及证明难度和算法复杂性循序渐进。
　　在第二版中， 我继续保持这种风格。欧拉回路和哈密顿环仍在不同章节， 并离得更远。欧拉回路的简单介绍在1.2节，