1 基本概念
图论研究的核心对象是图，它用有限或可数的点与线来抽象描述事物之间的联系。作为离散数学的重要组成部分，图论既建立形式化定义，也关注如何借助图来表达关系、路径与结构特征。
1.1 图的定义与组成
图通常由顶点集合和边集合构成。不同类型的图在边的方向、重复性以及允许的自连接等方面存在差异，这些约定决定了图的具体性质和适用场景。
1.1.1 顶点与边
顶点是图中的基本元素，常用来表示对象、状态或位置；边则表示顶点之间的联系。若边不带方向，表示两点之间的对等关系；若带方向，则强调起点与终点的区分。根据问题背景，边还可以赋予权重，用于刻画距离、成本、容量等信息。
1.1.2 有向图与无向图
无向图中的边没有方向，适合描述对称关系，如朋友关系或双向通行道路。有向图中的边则具有方向，常用于表示单向流动、先后依赖或转移关系。许多现实问题在建模时会根据关系是否对称来选择图的类型。
1.1.3 简单图与多重图
简单图通常不允许自环，也不允许同一对顶点之间出现多条边，因此结构较为规整。多重图则允许重边存在，适合表达多种不同联系并存的情形。若允许顶点与自身相连，则称为含自环的图，这在一些代数和网络模型中较常见。
1.2 图的表示方法
图在理论研究中常以集合方式描述，而在计算机中则需要转化为便于存储和运算的数据结构。不同表示法各有优劣，通常取决于图的稠密程度及所需操作类型。
1.2.1 邻接矩阵
邻接矩阵用一个方阵记录顶点之间是否相连，若图带权，也可直接记录边的权值。该表示方式便于判断两点是否相邻，并适合矩阵运算，但在顶点较多而边较少时会占用较大空间。
1.2.2 邻接表
邻接表为每个顶点保存其相邻顶点的列表，是处理稀疏图时常用的表示方式。它在遍历邻接点时效率较高，也较节省存储空间，因此在图算法实现中应用广泛。
1.2.3 关联矩阵
关联矩阵通过行表示顶点、列表示边，矩阵元素反映某顶点是否与某条边相关。对于无向图和有向图，其元素取值规则略有不同。该表示法在研究边与顶点关系、代数结构时具有一定便利性。
1.3 图的基本术语
图论发展过程中形成了一套较为稳定的术语体系，用来描述顶点、边及其组合所呈现的结构特征。这些概念是后续研究连通性、路径和图算法的基础。
1.3.1 度与入度出度
在无向图中，某顶点相连的边数称为该顶点的度；自环在计数时通常按特殊规则处理。在有向图中，进入顶点的边数称为入度，离开顶点的边数称为出度。这些量常用于判断网络负载、连接强度和结构分布。
1.3.2 子图与补图
子图是从原图中选取部分顶点与边所形成的新图，保留了原图的一部分结构。补图则是在同一顶点集合上，将原图中不存在的边补充出来，原有边则不再保留。补图常用于研究图的对偶结构与稠密程度。
1.3.3 同构与自同构
若两个图的顶点可以一一对应，且这种对应保持边关系不变，则称这两个图同构，表示它们在结构上本质相同。自同构是图到自身的同构，用来刻画图内部的对称性。判定同构通常较为复杂，是图论中的经典难题之一。
2 图的特殊类型
在一般图的基础上，图论研究了许多具有典型性质的特殊图类。这些图往往在结构上更规整，便于分析，也常作为证明和算法设计的标准对象。
2.1 完全图与二分图
完全图和二分图是两类极具代表性的图。前者强调任意两点都相连，后者则体现顶点的分组结构与边的限制条件。
2.1.1 完全图的性质
完全图中任意两个不同顶点之间都有边相连，因此它的边数达到给定顶点数下的最大值。完全图在极值问题中十分重要，也常作为比较标准。其对称性较强，结构分析相对直接。
2.1.2 二分图的判定
二分图可以将顶点划分为两个不相交的部分，且每条边都连接来自不同部分的顶点。判断一个图是否为二分图，常可通过检验是否存在奇长度回路来完成。二分图在匹配、调度和资源分配中应用广泛。
2.1.3 完全二分图
完全二分图是在二分图基础上进一步要求两个部分之间的每一对顶点都相连。它是研究二分结构与匹配问题的重要模型。记号上通常用两侧顶点数表示其规模。
2.2 路径、回路与环
路径概念用于描述从一个顶点沿边到达另一个顶点的过程，而回路与环则关注起点终点是否重合以及是否允许重复顶点和边。
2.2.1 简单路径与简单回路
简单路径是指顶点不重复的路径，简单回路则是起点与终点相同且除首尾外其余顶点不重复的闭合路径。它们在图的结构分析中具有基础地位，常用于判定连通性和寻找特殊子结构。
2.2.2 欧拉路与欧拉回路
欧拉路是恰好经过每条边一次的路径，欧拉回路则要求最终回到起点。此类问题最早与桥梁巡游相关，因此具有典型的历史意义。欧拉性质主要取决于顶点度数的奇偶分布。
2.2.3 哈密顿路与哈密顿回路
哈密顿路要求每个顶点恰好经过一次，哈密顿回路则在此基础上回到起点。这类问题更关注顶点访问顺序，通常比欧拉问题更难判定。它在旅行路线、访问规划和组合优化中经常出现。
2.3 树与森林
树是图论中最重要的基本结构之一，具有无回路、连通等典型特征。森林则是由若干棵树组成的图，是树的自然推广。
2.3.1 树的定义与性质
树是连通且不含回路的无向图。它满足若干等价性质，例如任意两点之间存在唯一简单路径，或边数等于顶点数减一。树结构简洁，在层次化表示与递归处理中很有价值。
2.3.2 根树与有根树
当树中指定一个顶点作为根时，便形成有根树，也称根树。此时边常被赋予从根向外的层次方向，便于描述父子关系、层级结构和搜索过程。根树在数据结构和表示层次信息时十分常见。
2.3.3 森林与生成树
森林是不含回路的图，可能由多棵树组成。若从一个连通图中选取若干边，使其既保持连通又不含回路，则得到生成树。生成树在网络设计与最优连接问题中占有重要地位。
3 图的性质
图的性质反映了结构是否连通、是否可平面绘制以及顶点之间的距离关系等。这些性质既是理论研究对象，也是算法分析的重要依据。
3.1 连通性
连通性描述图中顶点是否能够通过路径彼此到达，是图论中最基础的整体性质之一。它直接影响图的分解方式和可达性分析。
3.1.1 连通图与连通分量
在无向图中，若任意两顶点之间都存在路径，则称图为连通图。若图不连通，则可分解为若干互不相交的连通分量，每个分量内部连通而分量之间彼此隔离。连通分量反映了图的自然分块。
3.1.2 强连通与弱连通
在有向图中，若任意两顶点之间都能沿有向边互相到达，则称为强连通。若忽略边的方向后图变为连通，则称为弱连通。二者分别反映了方向约束下的严格可达性与宽松连通性。
3.1.3 割点与桥
割点是指删除该顶点及其相关边后，会使图的连通分量数增加的顶点；桥则是删除后会使图断开的边。它们是衡量网络脆弱性的关键概念，常用于识别结构中的关键节点与关键连接。
3.2 平面图
平面图研究的是能否在平面上无交叉地绘制图，以及这种绘制方式所带来的结构约束。该主题在拓扑图论与图着色中都很重要。
3.2.1 平面嵌入
如果一个图可以在平面上画出，且边仅在端点处相交，则称其具有平面嵌入。不同的嵌入方式可能对应不同的面划分，但它们共享同一图的组合结构。平面嵌入问题与地图、线路布局等模型密切相关。
3.2.2 欧拉公式
对于连通平面图，顶点数、边数与面数之间满足经典的欧拉公式。该公式揭示了平面图的基本数量关系，并可用于判断某些图是否可能是平面图。它是平面图理论中的核心结论之一。
3.2.3 克拉特斯基定理
克拉特斯基定理给出了平面图的一个判定性表述，说明某些最小非平面图具有特殊的结构地位。它与库拉托夫斯基定理密切相关，常用于从局部结构推断整体可平面性。相关结论对平面图分类有重要意义。
3.3 图的度量性质
度量性质关注图中点与点之间的距离以及由此导出的中心、半径等概念，常用于网络分析和结构优化。
3.3.1 距离与直径
两个顶点之间最短路径的长度称为它们的距离。图中所有顶点对距离的最大值称为直径。直径越小，通常意味着网络中信息或资源传递更为迅速。
3.3.2 中心与半径
某顶点到其他顶点距离的最大值称为该点的离心率。离心率最小的顶点构成图的中心，而这个最小值称为半径。中心点常被视为网络中的“核心”位置。
3.3.3 围长与周长
在图论中，围长通常指最短回路的长度，而周长有时用于描述最长回路或某种闭合结构的长度，具体含义需结合语境。它们反映图中环结构的尺度，对分析稀疏性和局部复杂度有帮助。
4 图论中的经典问题
图论不仅研究结构本身，也形成了若干具有代表性的组合优化问题。这些问题往往具有明确的实际背景，并推动了图算法的发展。
4.1 图着色
图着色研究如何给图的元素赋予颜色，使相邻对象满足特定限制。它与资源分配、冲突避免和频率规划等问题关系密切。
4.1.1 顶点着色
顶点着色要求相邻顶点颜色不同。若希望使用尽量少的颜色，就会引出最优着色问题。该问题在课程安排、任务分组和冲突调度中具有典型应用。
4.1.2 边着色
边着色要求共享同一顶点的边不能同色。此类模型适用于通信信道分配、班次安排等场景。与顶点着色相比，边着色的约束对象转向了连接关系本身。
4.1.3 色数与染色多项式
图的色数是完成合法顶点着色所需的最少颜色数，是衡量图复杂程度的重要参数。染色多项式则从计数角度描述在给定颜色数下合法着色方案的数量，体现了图的组合结构特征。
4.2 匹配问题
匹配关注图中互不冲突的边集合，是二分图和一般图中都极为重要的研究对象。它在分配和配对问题中尤为常见。
4.2.1 最大匹配
最大匹配是边数最多的匹配，表示在不发生顶点冲突的前提下尽可能多地配对。其求解是经典优化问题，在资源匹配和关系分配中用途广泛。
4.2.2 完美匹配
完美匹配要求图中的每个顶点都恰好与一条匹配边相接，从而实现完全配对。并非所有图都存在完美匹配，这一性质通常受顶点数奇偶性和结构条件影响。
4.2.3 二分图匹配
二分图匹配是匹配理论中的核心分支，因结构清晰而便于算法设计。它常被用于求解任务与人员之间的一一对应问题，也与许多网络流模型存在深刻联系。
4.3 覆盖问题
覆盖问题与匹配相互关联，关注用尽量少的元素“覆盖”图中的所有边或顶点，是组合优化中的基本模型。
4.3.1 点覆盖
点覆盖是指选取若干顶点，使图中每条边至少有一个端点被选中。最小点覆盖问题要求覆盖所有边的同时选取的顶点尽量少。它在监控布设和控制点选择中具有解释意义。
4.3.2 边覆盖
边覆盖是指选取若干边，使每个顶点至少与所选边中的一条相接。与点覆盖相比，它更强调通过边来触及所有顶点。该问题常与匹配理论结合分析。
4.3.3 最小覆盖与极大覆盖
最小覆盖要求在满足覆盖条件的前提下使规模尽量小，而极大覆盖则强调在当前条件下已无法再通过加入元素获得更强覆盖。二者体现了“最优”与“不可扩展”两种不同的极值概念。
5 重要算法
图论算法是将理论结构转化为可执行过程的关键桥梁。许多经典算法已成为计算机科学和运筹优化中的基础工具。
5.1 最短路径算法
最短路径问题研究在带权图中如何找到两点之间代价最小的路径，或某一点到其他点的最优到达方式。不同算法适用于不同权值条件。
5.1.1 Dijkstra算法
Dijkstra算法用于求解非负权图中的单源最短路径。它通过逐步确定当前已知距离最小的顶点，并不断更新周边路径长度，具有清晰的贪心思想。该算法实现简洁，应用极广。
5.1.2 Bellman-Ford算法
Bellman-Ford算法能够处理含有负权边的单源最短路径问题，只要图中不存在从源点可达的负权回路。它通过反复松弛边来逐步逼近最优解，适合更一般的权值环境。
5.1.3 Floyd-Warshall算法
Floyd-Warshall算法用于求解任意两点之间的最短路径，也称全源最短路径算法。它基于动态规划思想，通过逐步引入中间顶点来更新路径长度，适合顶点数不太大的密集图。
5.2 最小生成树算法
最小生成树问题是在加权连通图中寻找总权值最小的生成树，是网络铺设与连接成本优化的经典模型。
5.2.1 Prim算法
Prim算法从一个起始顶点出发，逐步向外扩展，每次选择连接已选集合与未选顶点的最小权边。它更像“生长”一棵树，因此在稠密图中常表现良好。
5.2.2 Kruskal算法
Kruskal算法按边权从小到大排序，依次尝试加入边，只要不形成回路就保留。它基于全局选边思想，适合边数较少的稀疏图，并与并查集等数据结构配合紧密。
5.2.3 生成树的应用
生成树可用于构建最省成本的通信网络、电力网络和道路连接方案。除最小生成树外，生成树的结构分析还常出现在网络可靠性、拓扑简化与组合计数中。
5.3 网络流算法
网络流研究在带容量限制的有向网络中，如何从源点向汇点输送尽可能多的“流量”。这类模型在运输、分配和资源调度中十分典型。
5.3.1 最大流问题
最大流问题要求在容量约束下，使从源点到汇点的总流量达到最大。它不仅具有重要的实际背景，也与割、匹配和线性规划之间存在密切联系。
5.3.2 最小割问题
最小割是将源点与汇点分开的边集，使跨越割的总容量最小。最大流与最小割之间存在经典对应关系，这一联系构成了网络流理论的核心之一。
5.3.3 增广路方法
增广路方法通过不断寻找可以增加流量的路径并调整流值，逐步逼近最大流。它思想直观，是许多最大流算法的基础框架，也便于理解网络流的本质。
6 进阶主题
在基础概念和经典算法之外，图论还发展出许多更具代数性、组合性和随机性的研究方向。这些主题往往与现代数学和复杂系统分析密切相关。
6.1 图的谱理论
谱理论把图转化为矩阵对象，通过研究矩阵特征值和特征向量来揭示图的结构信息。它在数学、物理和数据分析中都很活跃。
6.1.1 邻接矩阵特征值
邻接矩阵的特征值反映了图的整体连接模式和某些对称性质。特征值分布可用于判断图的稠密程度、连通特性以及某些极值结构。
6.1.2 拉普拉斯矩阵
拉普拉斯矩阵由度矩阵与邻接矩阵组合而成，常用于刻画图的连通性、扩散过程和谱性质。它在聚类、随机游走与谱分割中具有重要作用。
6.1.3 谱与结构性质
图的谱与其连通性、二分性、扩展性等结构特征存在深层联系。尽管谱信息不能完全决定图的结构，但它提供了强有力的全局描述手段。
6.2 图的枚举与计数
枚举与计数研究给定条件下图的数量、不同标号图的个数以及相关组合结构的统计规律，是组合数学的重要内容。
6.2.1 图的数量统计
当顶点数固定时，可研究满足不同约束的图有多少种。随着顶点数增长，图的总数迅速增加，这一现象体现了图组合空间的巨大规模。
6.2.2 组合计数方法
组合计数常借助递推、生成函数、包容排斥等工具完成图结构统计。不同计数技术适用于不同图类，可用于求解边数、连通图数或特定子图数目。
6.2.3 Pólya计数思想
Pólya计数思想利用群作用与等价分类来避免重复计数，特别适合处理具有对称性的图结构。它在标号与非标号图的枚举中非常有用。
6.3 随机图与复杂网络
随机图理论通过概率方法研究图的典型性质，而复杂网络则关注现实网络中常见的非平凡结构模式。二者共同推动了图论向应用科学扩展。
6.3.1 随机图模型
随机图模型通过随机方式生成边，从而分析图在平均意义下的性质。它可用于研究连通阈值、度分布和子图出现概率等问题。
6.3.2 小世界网络
小世界网络兼具较短平均路径和较高聚集性，常被用来描述一些现实系统中的“近邻紧密、远距可达”特征。这类网络模型直观地解释了局部团簇与全局快速连通并存的现象。
6.3.3 无标度网络
无标度网络的度分布常呈现幂律特征，少数顶点拥有大量连接，而多数顶点连接较少。该结构在某些自然和技术网络中十分常见，因而成为复杂网络研究的重点对象。
7 应用领域
图论的价值不仅体现在抽象数学中，也体现在对现实问题的建模、分析与求解中。它的应用横跨计算、管理、工程与生命科学等多个方向。
7.1 计算机科学中的应用
计算机科学是图论最重要的应用领域之一。无论是算法设计、数据组织还是网络通信，图模型都提供了统一的描述语言。
7.1.1 数据结构与算法
许多数据结构，如树、堆和图的邻接表示，都与图论紧密相关。图算法也常作为基础教学内容，用于训练搜索、优化和复杂度分析能力。
7.1.2 计算复杂性
图论中的若干经典问题，如着色、匹配和哈密顿问题，常被用来研究计算复杂性边界。它们在“可高效求解”与“难以求解”之间划出重要分界。
7.1.3 计算机网络
计算机网络可抽象为图，其中设备作为顶点，连接作为边。借助图论可以分析路由、带宽分配、冗余设计和网络鲁棒性等问题。
7.2 运筹学中的应用
运筹学强调资源优化与决策支持，图论为其提供了自然的模型语言和高效算法工具。许多实际规划问题都能转化为图上的最优化任务。
7.2.1 任务分配
任务分配问题可以用二分图匹配或网络流模型表示，从而实现人员、机器与任务之间的合理对应。图论方法能够帮助降低冲突并提高资源利用率。
7.2.2 物流与路径规划
物流运输与路径规划常涉及最短路径、最小生成树和网络流问题。图模型可以清晰表达站点、道路和成本关系，为路线设计和运输优化提供依据。
7.2.3 调度问题
调度问题中，任务之间的先后约束、资源冲突和时间安排都可借助图来表示。通过着色、排序和匹配等工具，能够构造较为有效的调度方案。
7.3 其他学科中的应用
图论作为通用的关系建模工具，也广泛渗透到自然科学与生命科学中。只要研究对象之间存在联系、转换或依赖，就可能出现图模型。
7.3.1 化学结构分析
在化学中，分子常被表示为图，原子对应顶点，化学键对应边。这样的表示有助于分析分子结构、异构体数量以及某些性质之间的关系。
7.3.2 社会网络分析
社会网络可视为由个体及其关系构成的图。图论方法能够刻画群体结构、中心人物、传播路径和社群划分，因此在社会关系研究中很常见。
7.3.3 生物信息学
在生物信息学中，基因、蛋白质和代谢通路之间的关联常被建模为图。通过分析这些网络，可以辅助理解功能模块、相互作用模式和信息传递过程。