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

本书可以帮助读者对图论的研究和相关理论的学习,有利于提高其分析问题、解决问题 的能力。

图论起源于一个非常经典的问题柯尼斯堡问题。1738年，瑞士数学家欧拉解决 了柯尼斯堡问题，由此图论诞生。欧拉也成为图论的创始人。1859年，英国数学家汉密尔顿发明了一种游戏:在一个规则的实心十二面体的20个顶点标出世界著名的20个城市，要求游戏者寻找一条沿着各边通过每个顶点刚好一次的闭回路，即 绕行世界。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。 这个生成圈后来被称为汉密尔顿回路。这个问题后来就称作汉密尔顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为汉密尔顿问题，从而引起广泛的注意和研究。 全书共分七章，主要内容包括图的基本概念、树、欧拉通路与哈密顿通路、复杂网络分 析概述、随机网络和小世界网络、无标度网络、网络中的社团结构等。书中除对重要部分进 行解释外，还通过例题的讲述，使图论的内容变得更加通俗易懂，便于理解和解决。 本书可以帮助读者对图论的研究和相关理论的学习，有利于提高其分析问题、解决问题 的能力。 本书由山东交通学院黄宝华主编，全书编写分工如下:黄宝华编写第1章、第7章并承担全书的统稿工作；山东交通学院曹向阳编写第2、3章;河北工程大学王贺封编写第4章；常州市新北自然资源和规划技术保障中心佟国功编写第5章;烟台市福山区不动产登记中心孙涛编写第6章。雷佳辉、曹媛、潘文亮、于成负责资料搜集和书稿整理工作。本书得到泰山产 业 领 军 人 才 工 程 项 目 (tscy 20231229) 及 山 东 省 自 然 科 学 基 金 青 年 项 目 (ZR2022QD146)基于GIS和RS的土地利用都市化转型时空过程和机理研究基金支持。 中国科学院烟台海岸带研究所高志强研究员审阅了全书，提出许多宝贵意见，在此表示 衷心的感谢。限于编者水平，书中难免存在不足之处，敬请各位同行及读者批评指正。 编 者 2024年7月

山东交通学院,副教授,博士研究生

前言
第一章图的基本概念 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