应急食品——图论

忘忧兽

2025-09-20 22:39:22

发布于：江西

7阅读

0回复

0点赞

图论核心知识点与解题技巧（初一级别 / CSP 备考适用）

一、图论基础概念（必背）

图的定义：图（Graph）由顶点（Vertex，也叫节点）集合 $V$ 和边（Edge）集合 $E$ 组成，记为 $G=(V, E)$ 。顶点用于表示对象，边表示对象之间的关系。
有向图与无向图：

有向图：边具有方向性，例如 $<u, v>$ 表示从顶点 $u$ 指向顶点 $v$ 的边，信息或关系是单向传递的，类似网页链接，网页 $A$ 链接到网页 $B$ ，不代表 $B$ 也链接到 $A$ 。
无向图：边没有方向， $(u, v)$ 表示 $u$ 和 $v$ 之间有连接，关系是双向的，比如社交网络中的好友关系，若 $A$ 是 $B$ 的好友，那么 $B$ 也是 $A$ 的好友。

顶点的度数：

无向图：顶点的度数是与该顶点相连的边的数量。例如在一个简单无向图中，若顶点 $A$ 连接了 $3$ 条边，那么顶点 $A$ 的度数为 $3$ 。
有向图：分为入度和出度。入度是指向该顶点的边的数量，出度是从该顶点出发的边的数量。比如在一个表示任务依赖关系的有向图中，任务 $B$ 有 $2$ 个前置任务指向它，同时它指向 $1$ 个后续任务，那么任务 $B$ 的入度为 $2$ ，出度为 $1$ 。

路径与环：

路径：是一个顶点序列 $v_1, v_2, \cdots, v_k$ ，其中任意相邻的顶点 $v_i$ 和 $ v_{i + 1}$ 之间都有一条边相连。例如在图中从顶点 $1$ 经过边到顶点 $2$ ，再到顶点 $3$ ，则 $1 - 2 - 3$ 构成一条路径。
环：在无向图中，是至少包含一条边且起始和结束顶点相同的路径；在有向图中，是从某个顶点出发，沿着有向边经过一系列顶点后又回到该顶点的路径。例如在一个无向图中，顶点 $A - B - C - A$ 构成一个环；在有向图中 $A \to B \to C \to A$ 构成有向环。

连通图与强连通图：

连通图（针对无向图）：若图中任意两个顶点之间都存在路径，则称该图为连通图。比如一个表示城市交通的无向图，若任意两个城市之间都有道路可达，那么这个图就是连通图。
强连通图（针对有向图）：若有向图中任意两个顶点 $u$ 和 $v$ 之间，既存在从 $u$ 到 $ v$ 的路径，也存在从 $v$ 到 $u$ 的路径，则称该图为强连通图。例如在一个表示公交站点单向线路的有向图中，若任意两个站点都能通过公交线路相互到达，就是强连通图。

简单图与多重图：

简单图：没有自环（即顶点到自身的边）且任意两个顶点之间最多只有一条边相连的图。如常见的表示人际关系的图，两个人之间要么是朋友关系（一条边），要么不是，且自己不会和自己成为朋友（无自环）。
多重图：允许有重复边，即同一对顶点之间可以有多条边，也可能存在自环。例如在一个表示城市间不同类型交通线路（公路、铁路等）的图中，两个城市之间可能既有公路连接又有铁路连接，这就形成了多重图。

加权图：边带有权重的图，权重可以表示距离、成本、时间等实际意义的数值。例如在一个表示城市间距离的加权图中，边的权重就是两个城市之间的实际距离。
子图：从原图中选取部分顶点和这些顶点之间的边所构成的图。例如在一个大型社交网络中，选取其中一个小团体成员及其相互关系，就构成了原图的一个子图。
连通分量（无向图）：无向图中的极大连通子图。极大性意味着在这个子图中添加任何一个不属于它的顶点，都会破坏其连通性。例如一个非连通的无向图可能由多个相互独立的连通区域组成，每个区域就是一个连通分量。
强连通分量（有向图）：有向图中的极大强连通子图。不同强连通分量之间可能存在单向路径，但不存在相互可达的路径。例如在一个复杂的有向任务依赖图中，可以划分出多个强连通分量，每个分量内的任务相互依赖，不同分量之间有一定的单向依赖关系。
完全图：对于无向图，若任意两个不同顶点之间都有一条边相连，则称为完全图。假设有 $n$ 个顶点，边的数量为 $\frac{n(n - 1)}{2}$ 。例如 $3$ 个顶点的完全无向图，每个顶点都与另外两个顶点相连，共 $3$ 条边。
二分图：顶点可以被分为两个不相交的集合 $A$ 和 $B$ ，使得图中的每条边都连接集合 $A$ 中的一个顶点和集合 $B$ 中的一个顶点。比如在一个学生和课程的关系图中，学生为一个集合，课程为另一个集合，边表示学生选修课程，这可以构成一个二分图。
有向无环图（DAG）：有向图中不存在环的图。在实际应用中，如课程先修关系图，课程 $A$ 是课程 $B$ 的先修课程，就有一条从 $A$ 到 $B$ 的有向边，且不会出现课程之间相互依赖成环的情况，这就是典型的有向无环图。
欧拉图：包含一条经过每条边且每条边只经过一次的闭合路径（欧拉回路）的图。例如在一个一笔画问题中，如果一个图形可以从某一点出发，不重复地遍历所有边后回到起点，那么这个图形对应的图就是欧拉图。
哈密顿图：包含一个经过每个顶点且每个顶点只经过一次的路径（哈密顿路径）的图。类似于旅行商问题，商人要访问每个城市一次且仅一次，若能找到这样的路线，对应的城市连接图就是哈密顿图。
平面图：可以嵌入在平面上，使得边不相交的图。例如一些简单的电路布线图，若能在平面上合理布局线路而不出现交叉，对应的图就是平面图。

二、图的表示方法（理解）

邻接矩阵：用一个二维数组 $matrix$ 来表示图中顶点之间的邻接关系。对于无向图，如果顶点 $i$ 和顶点 $j$ 之间有边相连，则 $matrix[i][j] = matrix[j][i] = 1$ （对于无权图），若有权则存储边的权重；对于有向图，如果存在从顶点 $i$ 到顶点 $j$ 的有向边，则 $matrix[i][j] = 1$ （无权）或存储权重。例如一个 $3$ 个顶点的无向图，若顶点 $1$ 和顶点 $2$ 相连，顶点 $2$ 和顶点 $3$ 相连，其邻接矩阵为 $\begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}$ 。邻接矩阵的优点是直观，便于判断两点之间是否有边相连，缺点是空间复杂度较高，为 $O(n^2)$ ，适用于稠密图（边的数量接近 $n(n - 1)$ 的图）。
邻接表：对每个顶点，用一个链表（或数组）存储与之直接相连的顶点。例如顶点 $v$ 的邻接表中存储着所有与 $v$ 有边相连的顶点。对于无向图，若顶点 $1$ 与顶点 $2$ 、顶点 $3$ 相连，那么顶点 $1$ 的邻接表可能是 $[2, 3]$ ；对于有向图，若存在从顶点 $1$ 到顶点 $2$ 、顶点 $3$ 的有向边，顶点 $1$ 的邻接表同样是 $[2, 3]$ 。邻接表空间复杂度为 $O(n + m)$ ，其中 $n$ 是顶点数， $m$ 是边数，适用于稀疏图（边的数量远小于 $n(n - 1)$ 的图），在查找某个顶点的邻接顶点时效率较高。

三、图论核心性质（掌握）

握手定理（度数和与边数的关系）：在任何图中，所有顶点的度数之和等于边数的两倍。即 $\sum_{v \in V} degree(v) = 2m$ ，其中 $degree(v)$ 表示顶点 $v$ 的度数， $m$ 是边数。例如在一个有 $4$ 条边的无向图中，所有顶点度数之和为 $8$ 。这个性质可以帮助我们通过已知的度数或边数信息，推导其他未知量。
连通图的边数下限：对于一个包含 $ n $ 个顶点的连通无向图，至少需要 $ n - 1 $ 条边。例如 $ 3 $ 个顶点的连通无向图，最少有 $ 2 $ 条边（如 $ 1 - 2 - 3 $ 这样的线性连接）。当边数恰好为 $ n - 1 $ 时，图的结构是一棵树，树是一种特殊的连通无向图，无环且边数最少。
有向无环图（DAG）的性质：

一定存在入度为 $0$ 的顶点和出度为 $0$ 的顶点。例如在一个课程先修关系的 DAG 中，必定有不需要先修其他课程的基础课程（入度为 $0$ ），也有没有后续课程的最终课程（出度为 $0$ ）。
可以进行拓扑排序，将顶点排成一个线性序列，使得对于每一条有向边 $<u, v>$ ，顶点 $u$ 在序列中出现在顶点 $v$ 之前。拓扑排序在解决任务调度、依赖关系等问题中非常重要。

二分图的判定性质：一个图是二分图当且仅当图中不存在奇数长度的环。例如在一个表示男女匹配的图中，如果不存在奇数个顶点依次相连形成环的情况，那么这个图就是二分图，可以将顶点划分为男性集合和女性集合，且边只连接不同集合的顶点。
欧拉图的判定性质：

无向图是欧拉图当且仅当图是连通的且每个顶点的度数都是偶数。例如一个 “日” 字形的无向图，每个顶点度数为偶数且连通，存在欧拉回路，可以从某点出发一笔画遍历所有边回到起点。
有向图是欧拉图当且仅当图是强连通的且每个顶点的入度等于出度。例如在一个表示单向循环道路的有向图中，若每个路口进入和出去的道路数量相等且任意两点可相互到达，就满足欧拉图条件。

哈密顿图的一些必要条件（非充分）：若图 $G=(V, E)$ 是哈密顿图，对于 $V$ 的任意非空真子集 $S$ ，均有 $w(G - S) \leq |S|$ ，其中 $w(G - S)$ 表示图 $G$ 删除顶点集 $S$ 后得到的子图的连通分量个数， $|S|$ 表示集合 $S$ 中顶点的个数。例如在一个有 $5$ 个顶点的图中，若删除 $2$ 个顶点后，剩余子图的连通分量个数不超过 $2$ ，则该图有可能是哈密顿图，但不满足此条件一定不是哈密顿图。
平面图的欧拉公式：对于连通的平面图，有 $n - m + f = 2$ ，其中 $ n $ 是顶点数， $m$ 是边数， $f$ 是面数（包括外部无限面）。例如一个简单的三角形平面图，顶点数 $n = 3$ ，边数 $m = 3$ ，面数 $f = 2$ （内部一个面和外部无限面），满足 $3 - 3 + 2 = 2$ 。通过这个公式，已知其中两个量可以求解第三个量，在判断图是否为平面图以及计算相关参数时很有用。