文档摘要

图论 图论（graph theory）提供了描述实体之间关系的数学语言。本文件涵盖节点、边、邻接矩阵、图的类型、度与连通性、图拉普拉斯、谱图理论，以及现实世界中的图应用。我们会在纯计算机科学的章节里更深入地讨论图。 到目前为止，这本书里的数据都活在规则结构上：$\mathbb{R}^n$ 中的向量（第 1 章）、作为数字网格的矩阵（第 2 章）、作为像素网格的图像（第 8 章）、作为有序列表的序列（第 7 章）。但许多现实系统是不规则的：社交网络没有网格结构，分子没有从左到右的顺序，道路网络也无法整齐地铺成一行行一列列。 图（graph）是表示这些不规则、关系型结构的数学工具。一个图刻画实体（节点）以及它们之间的关系（边）。

---