本书包含作者对 “图论”学科的深刻理解,清晰地介绍了图论中的基本定理和方法示例,帮助读者提高自身 的分析能力并学习如何利用所学知识解决实际问题。
图论是数学的一个分支,主要研究由顶点（或称节点）和边组成的图的结构、性质和算法。图论不仅在纯数 学领域有重要的应用价值,在计算机科学、物理、化学、生物学、社会学等领域也发挥着至关重要的作用。
全书共七章,主要内容包括图的基本概念、树、欧拉通路与哈密顿通路、复杂网络分析概述、随机网络和小世界网络、无标度网络、网络中的社团结构等。

前言
第一章图的基本概念 1
1.1有向图和无向图 1
1.2完全图、稀疏图、稠密图 2
1.3二部图与完全二部图 5
1.4图的同构 7
1.5子图 7
1.6正则图 8
1.7路 9
1.8连通图 10
1.9 邻接矩阵与关联矩阵11
第二章 树 13
2.1 割点 (Cut-vertex)和割边 (Cut-edge) 13
2.2 树与森林 16
2.3 生成树及最小生成树 20
2.4 克鲁斯卡尔 (Kruskal)算法 20
2.5 普里姆 (Prim)算法 22
2.6 中心点选址问题 23
2.7 中位点选址问题 24
第三章 欧拉通路与哈密顿通路 26
3.1 引言 26
3.2 欧拉通路与欧拉回路 27
3.3 哈密顿通路与哈密顿回路 30
3.4 欧拉图的应用 33
3.5 哈密顿图的应用 34
第四章 复杂网络分析概述 36
4.1 复杂网络介绍 36
4.2 复杂网络的静态指标 41
4.3 度的相关性 43
4.4 路径、直径、平均最短路径长度、介数 47
4.5 集聚系数 51
4.6 网络传递性 52
4.7 富人俱乐部 53
第五章 随机网络和小世界网络 56
5.1 伯努利试验与二项分布 56
5.2 泊松分布 57
5.3 随机网络 60
5.4 小世界现象 64
5.5 小世界网络 65
第六章 无标度网络 71
6.1 无标度性质 71
6.2 无标度网络的枢纽节点 71
6.3 无标度网络的度分布 74
6.4 BA无标度网络 79
第七章 网络中的社团结构 83
7.1 社团在网络科学中的含义 83
7.2 社团结构的分类 84
7.3 社团结构的比较 85
7.4 社团划分算法 86
参考文献 94