程序员的数学4：图论入门

本书沿袭“程序员的数学”系列平易近人的风格，用简练的语言和丰富的示例向程序员介绍了编程中所需的图论基础知识。内容包括小生成树、短路径问题、欧拉回路、哈密顿圈、图着色、流问题和匹配问题等。本书并未枯燥地讲解理论，而是通过大量代入了具体数值的示例，引导读者理解图论中的概念和定理。在讲解图算法时还详细拆分了算法的执行步骤，以便读者加深理解。

宫崎修一（作者） 1998年毕业于日本九州大学研究生院系统信息学研究科，获工学博士学位。现任日本京都大学学术信息媒体中心副教授，主要研究算法和计算复杂性理论。著作有《我的本算法书》（合著）。 卢晓南（译者） 本科就读于西安交通大学少年班、数学系。名古屋大学博士（信息科学）。现于山梨大学计算机系任助理教授。主要研究方向包括组合数学（离散数学）及其在信息科学、计算机科学、统计学中的应用。译著有《程序员的数学3：线性代数》。

第 1章 图的基础知识 1

1.1 什么是图 1

1.2 图的表示法 6

1.3 其他图论术语 9

1.4 几类特殊的图 17

1.5 图的度序列 26

章末习题 31

第 2章 小生成树 33

2.1 什么是小生成树 33

2.2 克鲁斯卡尔算法 35

2.3 普里姆算法 39

2.4 小斯坦纳树问题 41

章末习题 43

第3章 短路径问题 45

3.1 什么是短路径问题 45

3.2 迪杰斯特拉算法 46

章末习题 52

第4章 欧拉回路与哈密顿圈 53

4.1 定义 53

4.2 欧拉回路 56

4.3 哈密顿圈 59

章末习题 63

第5章 图着色 65

5.1 顶点着色 65

5.2 边着色 79

章末习题 84

第6章流问题 85

6.1 什么是流问题 85

6.2 福特- 富尔克森算法 89

6.3 流小割定理 96

章末习题 99

第7章 匹配问题 101

7.1 什么是匹配 101

7.2 二部图中的匹配 104

7.3 匈牙利算法 108

7.4 用求解流问题的算法求解匹配问题 115

章末习题 118

第8章 章末习题解答 119

索引 131

本书沿袭“程序员的数学”系列平易近人的风格，用简练的语言和丰富的示例向程序员介绍了编程中所需的图论基础知识。内容包括小生成树、短路径问题、欧拉回路、哈密顿圈、图着色、流问题和匹配问题等。本书并未枯燥地讲解理论，而是通过大量代入了具体数值的示例，引导读者理解图论中的概念和定理。在讲解图算法时还详细拆分了算法的执行步骤，以便读者加深理解。

宫崎修一（作者） 1998年毕业于日本九州大学研究生院系统信息学研究科，获工学博士学位。现任日本京都大学学术信息媒体中心副教授，主要研究算法和计算复杂性理论。著作有《我的本算法书》（合著）。 卢晓南（译者） 本科就读于西安交通大学少年班、数学系。名古屋大学博士（信息科学）。现于山梨大学计算机系任助理教授。主要研究方向包括组合数学（离散数学）及其在信息科学、计算机科学、统计学中的应用。译著有《程序员的数学3：线性代数》。