图论相关概念¶
本页面概述了图论中的常见概念。多数内容足以覆盖信息学竞赛（OI）中的基本需求，若学习过程中遇到不熟悉的术语，可返回此页面查阅。
图（Graph）¶
图是一个二元组 $G = (V, E)$，其中：
- $V(G)$：非空集合，称为点集（vertex set），其元素为顶点（vertex）或节点（node）。
- $E(G)$：顶点对之间的集合，称为边集（edge set），其元素称为边（edge）。
图分为以下几类：
- 无向图（Undirected Graph）：$E$ 中每个元素是无序对 $(u, v)$。
- 有向图（Directed Graph）：$E$ 中每个元素是有序对 $(u, v)$，也写作 $u \to v$。
- 混合图（Mixed Graph）：同时包含有向边和无向边。
其他属性包括：
- 赋权图（Weighted Graph）：边附带权值。
- 正权图：所有边权为正实数。
- 有限图 / 无限图：$V$ 和 $E$ 是有限集合时称为有限图，否则为无限图。
- 图的阶（Order）：点数 $\left| V \right|$。
简单图与多重图¶
- 自环（Loop）：边的两个端点相同，即 $(v, v)$。
- 重边（Multiple Edge）：存在两个完全相同的边（在无向图中，$(u, v)$ 与 $(v, u)$ 视为相同）。
- 简单图（Simple Graph）：无自环和重边的图。
- 多重图（Multigraph）：包含自环或重边的图。
在竞赛中若未特别说明，默认允许图中存在自环与重边，需注意题意。
度数（Degree）¶
- 无向图中，顶点 $v$ 的度记作 $d(v)$，表示与 $v$ 相连的边数。
- 有向图中：
- 出度：从 $v$ 出发的边数，记作 $d^+(v)$。
- 入度：以 $v$ 为终点的边数，记作 $d^-(v)$。
- 有 $d(v) = d^+(v) + d^-(v)$。
特殊类型顶点：
- $d(v) = 0$：孤立点（Isolated Vertex）
- $d(v) = 1$：叶节点 / 悬挂点（Leaf / Pendant Vertex）
- $d(v) = |V| - 1$：支配点（Universal Vertex）
- $d(v)$ 为偶数：偶点（Even Vertex）
- $d(v)$ 为奇数：奇点（Odd Vertex）
其他术语：
- 最小度 $\delta(G) = \min d(v)$
- 最大度 $\Delta(G) = \max d(v)$
- k-正则图（k-Regular Graph）：所有顶点的度均为 $k$ 的图。
- 可图化 / 可简单图化：存在某图，其度数列为给定序列。
握手定理：对于无向图，有 $$ \sum_{v \in V} d(v) = 2|E| $$ 推论：奇点数量一定为偶数。
路径相关¶
- 途径（Walk）：顶点和边交替组成的序列，允许重复。
- 迹（Trail）：不重复边的途径。
- 路径（Path）：不重复点的迹（又称简单路径）。
- 回路（Circuit）：起点等于终点的迹。
- 环 / 圈（Cycle）：起点等于终点，且中间不含重复点的回路（又称简单回路）。
子图（Subgraph）¶
设 $G = (V, E)$，若 $H = (V', E')$ 满足 $V' \subseteq V$ 且 $E' \subseteq E$，则 $H$ 是 $G$ 的子图。
分类：
- 导出子图 / 诱导子图（Induced Subgraph）：$E'$ 包含所有在 $E$ 中连接 $V'$ 中点对的边，记作 $G[V']$。
- 生成子图 / 支撑子图（Spanning Subgraph）：$V' = V$。
- k-因子（k-Factor）：$G$ 的某个生成子图是 $k$-正则图。
- 闭合子图（Closed Subgraph）：有向图中，若一个导出子图包含所有能到其内部点的边，则为闭合子图。
连通性（Connectivity）¶
无向图¶
- 连通：若存在从 $u$ 到 $v$ 的路径。
- 连通图（Connected Graph）：任意两点连通。
- 连通块 / 连通分量（Connected Component）：极大连通子图。
有向图¶
- 可达：存在从 $u$ 到 $v$ 的路径。
- 强连通图（Strongly Connected Graph）：任意两点互相可达。
- 弱连通图（Weakly Connected Graph）：忽略边方向后为连通图。
- 强连通分量 / 弱连通分量：极大强 / 弱连通子图。
稀疏图 / 稠密图¶
- 稀疏图（Sparse Graph）：边数远小于 $|V|^2$。
- 稠密图（Dense Graph）：边数接近 $|V|^2$。
该划分通常用于分析算法复杂度差异：
- 稠密图：$O(|V|^2)$ 和 $O(|E|)$ 算法效率相近；
- 稀疏图：$O(|E|)$ 明显更优。
补图（Complement Graph）¶
对于无向简单图 $G = (V, E)$，其补图记作 $\bar G$，满足：
- $V(\bar G) = V(G)$
- $(u, v) \in E(\bar G) \iff (u, v) \notin E(G)$，其中 $u \ne v$
反图（Transpose Graph）¶
对于有向图 $G = (V, E)$，其反图（转置图）记作 $G^T = (V, E')$，其中：
\[
E' = \{(v, u) \mid (u, v) \in E\}
\]
即将所有边的方向反转。