图论核心知识点与解题技巧（初一级别 / CSP 备考适用）
一、图论基础概念（必背）
1. 图的定义：图（Graph）由顶点（Vertex，也叫节点）集合VVV和边（Edge）集合 EEE 组成，记为 G=(V,E)G=(V, E)G=(V,E)。顶点用于表示对象，边表示对象之间的关系 。
2. 有向图与无向图：
* 有向图：边具有方向性，例如 <u,v><u, v><u,v> 表示从顶点 uuu 指向顶点 vvv 的边，信息或关系是单向传递的，类似网页链接，网页 AAA 链接到网页 BBB，不代表 BBB 也链接到 AAA。
* 无向图：边没有方向，(u,v)(u, v)(u,v) 表示 uuu 和 vvv 之间有连接，关系是双向的，比如社交网络中的好友关系，若 AAA 是 BBB 的好友，那么 BBB 也是 AAA 的好友 。
1. 顶点的度数：
* 无向图：顶点的度数是与该顶点相连的边的数量。例如在一个简单无向图中，若顶点 AAA 连接了 333 条边，那么顶点 AAA 的度数为 333。
* 有向图：分为入度和出度。入度是指向该顶点的边的数量，出度是从该顶点出发的边的数量。比如在一个表示任务依赖关系的有向图中，任务 BBB 有 222 个前置任务指向它，同时它指向 111 个后续任务，那么任务 BBB 的入度为 222，出度为 111。
1. 路径与环：
* 路径：是一个顶点序列 v1,v2,⋯ ,vkv_1, v_2, \cdots, v_kv1 ,v2 ,⋯,vk ，其中任意相邻的顶点 viv_ivi 和 $ v_{i + 1}$ 之间都有一条边相连。例如在图中从顶点 111 经过边到顶点 222，再到顶点 333，则 1−2−31 - 2 - 31−2−3 构成一条路径。
* 环：在无向图中，是至少包含一条边且起始和结束顶点相同的路径；在有向图中，是从某个顶点出发，沿着有向边经过一系列顶点后又回到该顶点的路径。例如在一个无向图中，顶点 A−B−C−AA - B - C - AA−B−C−A 构成一个环；在有向图中 A→B→C→AA \to B \to C \to AA→B→C→A 构成有向环 。
1. 连通图与强连通图：
* 连通图（针对无向图）：若图中任意两个顶点之间都存在路径，则称该图为连通图。比如一个表示城市交通的无向图，若任意两个城市之间都有道路可达，那么这个图就是连通图。
* 强连通图（针对有向图）：若有向图中任意两个顶点 uuu 和 vvv 之间，既存在从 uuu 到 $ v$ 的路径，也存在从 vvv 到 uuu 的路径，则称该图为强连通图。例如在一个表示公交站点单向线路的有向图中，若任意两个站点都能通过公交线路相互到达，就是强连通图。
1. 简单图与多重图：
* 简单图：没有自环（即顶点到自身的边）且任意两个顶点之间最多只有一条边相连的图。如常见的表示人际关系的图，两个人之间要么是朋友关系（一条边），要么不是，且自己不会和自己成为朋友（无自环）。
* 多重图：允许有重复边，即同一对顶点之间可以有多条边，也可能存在自环。例如在一个表示城市间不同类型交通线路（公路、铁路等）的图中，两个城市之间可能既有公路连接又有铁路连接，这就形成了多重图。
1. 加权图：边带有权重的图，权重可以表示距离、成本、时间等实际意义的数值。例如在一个表示城市间距离的加权图中，边的权重就是两个城市之间的实际距离。
2. 子图：从原图中选取部分顶点和这些顶点之间的边所构成的图。例如在一个大型社交网络中，选取其中一个小团体成员及其相互关系，就构成了原图的一个子图。
3. 连通分量（无向图）：无向图中的极大连通子图。极大性意味着在这个子图中添加任何一个不属于它的顶点，都会破坏其连通性。例如一个非连通的无向图可能由多个相互独立的连通区域组成，每个区域就是一个连通分量。
4. 强连通分量（有向图）：有向图中的极大强连通子图。不同强连通分量之间可能存在单向路径，但不存在相互可达的路径。例如在一个复杂的有向任务依赖图中，可以划分出多个强连通分量，每个分量内的任务相互依赖，不同分量之间有一定的单向依赖关系。
5. 完全图：对于无向图，若任意两个不同顶点之间都有一条边相连，则称为完全图。假设有 nnn 个顶点，边的数量为 n(n−1)2\frac{n(n - 1)}{2}2n(n−1) 。例如 333 个顶点的完全无向图，每个顶点都与另外两个顶点相连，共 333 条边。
6. 二分图：顶点可以被分为两个不相交的集合 AAA 和 BBB，使得图中的每条边都连接集合 AAA 中的一个顶点和集合 BBB 中的一个顶点。比如在一个学生和课程的关系图中，学生为一个集合，课程为另一个集合，边表示学生选修课程，这可以构成一个二分图。
7. 有向无环图（DAG）：有向图中不存在环的图。在实际应用中，如课程先修关系图，课程 AAA 是课程 BBB 的先修课程，就有一条从 AAA 到 BBB 的有向边，且不会出现课程之间相互依赖成环的情况，这就是典型的有向无环图。
8. 欧拉图：包含一条经过每条边且每条边只经过一次的闭合路径（欧拉回路）的图。例如在一个一笔画问题中，如果一个图形可以从某一点出发，不重复地遍历所有边后回到起点，那么这个图形对应的图就是欧拉图。
9. 哈密顿图：包含一个经过每个顶点且每个顶点只经过一次的路径（哈密顿路径）的图。类似于旅行商问题，商人要访问每个城市一次且仅一次，若能找到这样的路线，对应的城市连接图就是哈密顿图 。
10. 平面图：可以嵌入在平面上，使得边不相交的图。例如一些简单的电路布线图，若能在平面上合理布局线路而不出现交叉，对应的图就是平面图。
二、图的表示方法（理解）
1. 邻接矩阵：用一个二维数组 matrixmatrixmatrix 来表示图中顶点之间的邻接关系。对于无向图，如果顶点 iii 和顶点 jjj 之间有边相连，则 matrix[i][j]=matrix[j][i]=1matrix[i][j] = matrix[j][i] = 1matrix[i][j]=matrix[j][i]=1（对于无权图），若有权则存储边的权重；对于有向图，如果存在从顶点 iii 到顶点 jjj 的有向边，则 matrix[i][j]=1matrix[i][j] = 1matrix[i][j]=1（无权）或存储权重。例如一个 333 个顶点的无向图，若顶点 111
和顶点 222 相连，顶点 222 和顶点 333 相连，其邻接矩阵为 [010101010]\begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix} 010 101 010 。邻接矩阵的优点是直观，便于判断两点之间是否有边相连，缺点是空间复杂度较高，为 O(n2)O(n^2)O(n2)，适用于稠密图（边的数量接近 n(n−1)n(n - 1)n(n−1) 的图） 。
2. 邻接表：对每个顶点，用一个链表（或数组）存储与之直接相连的顶点。例如顶点 vvv 的邻接表中存储着所有与 vvv 有边相连的顶点。对于无向图，若顶点 111 与顶点 222、顶点 333 相连，那么顶点 111 的邻接表可能是 [2,3][2, 3][2,3]；对于有向图，若存在从顶点 111 到顶点 222、顶点 333 的有向边，顶点 111 的邻接表同样是 [2,3][2, 3][2,3] 。邻接表空间复杂度为 O(n+m)O(n + m)O(n+m)，其中 nnn 是顶点数， mmm 是边数，适用于稀疏图（边的数量远小于 n(n−1)n(n - 1)n(n−1)
的图），在查找某个顶点的邻接顶点时效率较高 。
三、图论核心性质（掌握）
1. 握手定理（度数和与边数的关系）：在任何图中，所有顶点的度数之和等于边数的两倍。即 ∑v∈Vdegree(v)=2m\sum_{v \in V} degree(v) = 2m∑v∈V degree(v)=2m，其中 degree(v)degree(v)degree(v) 表示顶点 vvv 的度数， mmm 是边数。例如在一个有 444 条边的无向图中，所有顶点度数之和为 888 。这个性质可以帮助我们通过已知的度数或边数信息，推导其他未知量。
2. 连通图的边数下限：对于一个包含 $ n $ 个顶点的连通无向图，至少需要 $ n - 1 $ 条边。例如 $ 3 $ 个顶点的连通无向图，最少有 $ 2 $ 条边（如 $ 1 - 2 - 3 $ 这样的线性连接）。当边数恰好为 $ n - 1 $ 时，图的结构是一棵树，树是一种特殊的连通无向图，无环且边数最少 。
3. 有向无环图（DAG）的性质：
* 一定存在入度为 000 的顶点和出度为 000 的顶点。例如在一个课程先修关系的 DAG 中，必定有不需要先修其他课程的基础课程（入度为 000），也有没有后续课程的最终课程（出度为 000）。
* 可以进行拓扑排序，将顶点排成一个线性序列，使得对于每一条有向边 <u,v><u, v><u,v>，顶点 uuu 在序列中出现在顶点 vvv 之前。拓扑排序在解决任务调度、依赖关系等问题中非常重要 。
1. 二分图的判定性质：一个图是二分图当且仅当图中不存在奇数长度的环。例如在一个表示男女匹配的图中，如果不存在奇数个顶点依次相连形成环的情况，那么这个图就是二分图，可以将顶点划分为男性集合和女性集合，且边只连接不同集合的顶点 。
2. 欧拉图的判定性质：
* 无向图是欧拉图当且仅当图是连通的且每个顶点的度数都是偶数。例如一个 “日” 字形的无向图，每个顶点度数为偶数且连通，存在欧拉回路，可以从某点出发一笔画遍历所有边回到起点。
* 有向图是欧拉图当且仅当图是强连通的且每个顶点的入度等于出度。例如在一个表示单向循环道路的有向图中，若每个路口进入和出去的道路数量相等且任意两点可相互到达，就满足欧拉图条件 。
1. 哈密顿图的一些必要条件（非充分）：若图 G=(V,E)G=(V, E)G=(V,E) 是哈密顿图，对于 VVV 的任意非空真子集 SSS，均有 w(G−S)≤∣S∣w(G - S) \leq |S|w(G−S)≤∣S∣，其中 w(G−S)w(G - S)w(G−S) 表示图 GGG 删除顶点集 SSS 后得到的子图的连通分量个数，∣S∣|S|∣S∣ 表示集合 SSS 中顶点的个数。例如在一个有 555 个顶点的图中，若删除 222 个顶点后，剩余子图的连通分量个数不超过 222，则该图有可能是哈密顿图，但不满足此条件一定不是哈密顿图 。
2. 平面图的欧拉公式：对于连通的平面图，有 n−m+f=2n - m + f = 2n−m+f=2，其中 $ n $ 是顶点数， mmm 是边数， fff是面数（包括外部无限面）。例如一个简单的三角形平面图，顶点数 n=3n = 3n=3，边数 m=3m = 3m=3，面数 f=2f = 2f=2（内部一个面和外部无限面），满足 3−3+2=23 - 3 + 2 = 23−3+2=2 。通过这个公式，已知其中两个量可以求解第三个量，在判断图是否为平面图以及计算相关参数时很有用 。
> （注：文档1112\frac{11}{12}1211 的内容由 AI 生成）
> （注：不为干啥，不为加精）
> 给个赞吧QwQ
