跳转至

# 图论相关概念

本页面概述了图论中的一些概念，这些概念并不全是在 OI 中常见的，对于 OIer 来说，只需掌握本页面中的基础部分即可，如果在学习中碰到了不懂的概念，可以再来查阅．

Warning

图论相关定义在不同教材中往往会有所不同，遇到的时候需根据上下文加以判断．

## 图

图 (graph) 是一个二元组 𝐺 =(𝑉(𝐺),𝐸(𝐺))G=(V(G),E(G))．其中 𝑉(𝐺)V(G) 是非空集，称为 点集 (vertex set)，对于 𝑉 V 中的每个元素，我们称其为 顶点 (vertex) 或 节点 (node)，简称 点；𝐸(𝐺)E(G) 为 𝑉(𝐺)V(G) 各结点之间边的集合，称为 边集 (edge set)．

常用 𝐺 =(𝑉,𝐸)G=(V,E) 表示图．

当 𝑉,𝐸 V,E 都是有限集合时，称 𝐺 G 为 有限图．

当 𝑉 V 或 𝐸 E 是无限集合时，称 𝐺 G 为 无限图．

图有多种，包括 无向图 (undirected graph)，有向图 (directed graph)，混合图 (mixed graph) 等．

若 𝐺 G 为无向图，则 𝐸 E 中的每个元素为一个无序二元组 (𝑢,𝑣)(u,v)，称作 无向边 (undirected edge)，简称 边 (edge)，其中 𝑢,𝑣 ∈𝑉 u,v∈V．设 𝑒 =(𝑢,𝑣)e=(u,v)，则 𝑢 u 和 𝑣 v 称为 𝑒 e 的 端点 (endpoint)．

若 𝐺 G 为有向图，则 𝐸 E 中的每一个元素为一个有序二元组 (𝑢,𝑣)(u,v)，有时也写作 𝑢 →𝑣 u→v，称作 有向边 (directed edge) 或 弧 (arc)，在不引起混淆的情况下也可以称作 边 (edge)．设 𝑒 =𝑢 →𝑣 e=u→v，则此时 𝑢 u 称为 𝑒 e 的 起点 (tail)，𝑣 v 称为 𝑒 e 的 终点 (head)，起点和终点也称为 𝑒 e 的 端点 (endpoint)．并称 𝑢 u 是 𝑣 v 的直接前驱，𝑣 v 是 𝑢 u 的直接后继．

为什么起点是 tail，终点是 head？

边通常用箭头表示，而箭头是从「尾」指向「头」的．

若 𝐺 G 为混合图，则 𝐸 E 中既有 有向边，又有 无向边．

若 𝐺 G 的每条边 𝑒 𝑘 =(𝑢 𝑘,𝑣 𝑘)e k=(u k,v k) 都被赋予一个数作为该边的 权，则称 𝐺 G 为 赋权图．如果这些权都是正实数，就称 𝐺 G 为 正权图．

图 𝐺 G 的点数 |𝑉(𝐺)||V(G)| 也被称作图 𝐺 G 的 阶 (order)．

形象地说，图是由若干点以及连接点与点的边构成的．

## 相邻

在无向图 𝐺 =(𝑉,𝐸)G=(V,E) 中，若点 𝑣 v 是边 𝑒 e 的一个端点，则称 𝑣 v 和 𝑒 e 是 关联的 (incident) 或 相邻的 (adjacent)．对于两顶点 𝑢 u 和 𝑣 v，若存在边 (𝑢,𝑣)(u,v)，则称 𝑢 u 和 𝑣 v 是 相邻的 (adjacent)．

一个顶点 𝑣 ∈𝑉 v∈V 的 邻域 (neighborhood) 是所有与之相邻的顶点所构成的集合，记作 𝑁(𝑣)N(v)．

一个点集 𝑆 S 的邻域是所有与 𝑆 S 中至少一个点相邻的点所构成的集合，记作 𝑁(𝑆)N(S)，即：

𝑁(𝑆)=⋃𝑣∈𝑆 𝑁(𝑣)N(S)=⋃v∈S N(v)

## 简单图

自环 (loop)：对 𝐸 E 中的边 𝑒 =(𝑢,𝑣)e=(u,v)，若 𝑢 =𝑣 u=v，则 𝑒 e 被称作一个自环．

重边 (multiple edge)：若 𝐸 E 中存在两个完全相同的元素（边）𝑒 1,𝑒 2 e 1,e 2，则它们被称作（一组）重边．

简单图 (simple graph)：若一个图中没有自环和重边，它被称为简单图．具有至少两个顶点的简单无向图中一定存在度相同的结点．（鸽巢原理）

如果一张图中有自环或重边，则称它为 多重图 (multigraph)．

Warning

在无向图中 (𝑢,𝑣)(u,v) 和 (𝑣,𝑢)(v,u) 算一组重边，而在有向图中，𝑢 →𝑣 u→v 和 𝑣 →𝑢 v→u 不为重边．

Warning

在题目中，如果没有特殊说明，是可以存在自环和重边的，在做题时需特殊考虑．

## 度数

与一个顶点 𝑣 v 关联的边的条数称作该顶点的 度 (degree)，记作 𝑑(𝑣)d(v)．特别地，对于边 (𝑣,𝑣)(v,v)，则每条这样的边要对 𝑑(𝑣)d(v) 产生 2 2 的贡献．

对于无向简单图，有 𝑑(𝑣) =|𝑁(𝑣)|d(v)=|N(v)|．

握手定理（又称图论基本定理）：对于任何无向图 𝐺 =(𝑉,𝐸)G=(V,E)，有 ∑𝑣∈𝑉 𝑑(𝑣) =2|𝐸|∑v∈V d(v)=2|E|．

推论：在任意图中，度数为奇数的点必然有偶数个．

若 𝑑(𝑣) =0 d(v)=0，则称 𝑣 v 为 孤立点 (isolated vertex)．

若 𝑑(𝑣) =1 d(v)=1，则称 𝑣 v 为 叶节点 (leaf vertex)/悬挂点 (pendant vertex)．

若 2 ∣𝑑(𝑣)2∣d(v)，则称 𝑣 v 为 偶点 (even vertex)．

若 2 ∤𝑑(𝑣)2∤d(v)，则称 𝑣 v 为 奇点 (odd vertex)．图中奇点的个数是偶数．

若 𝑑(𝑣) =|𝑉| −1 d(v)=|V|−1，则称 𝑣 v 为 支配点 (universal vertex)．

对一张图，所有节点的度数的最小值称为 𝐺 G 的 最小度 (minimum degree)，记作 𝛿(𝐺)δ(G)；最大值称为 最大度 (maximum degree)，记作 Δ(𝐺)Δ(G)．即：𝛿(𝐺) =m i n 𝑣∈𝐺 𝑑(𝑣)δ(G)=min v∈G d(v)，Δ(𝐺) =m a x 𝑣∈𝐺 𝑑(𝑣)Δ(G)=max v∈G d(v)．

在有向图 𝐺 =(𝑉,𝐸)G=(V,E) 中，以一个顶点 𝑣 v 为起点的边的条数称为该顶点的 出度 (out-degree)，记作 𝑑+(𝑣)d+(v)．以一个顶点 𝑣 v 为终点的边的条数称为该节点的 入度 (in-degree)，记作 𝑑−(𝑣)d−(v)．显然 𝑑+(𝑣) +𝑑−(𝑣) =𝑑(𝑣)d+(v)+d−(v)=d(v)．

对于任何有向图 𝐺 =(𝑉,𝐸)G=(V,E)，有：

∑𝑣∈𝑉 𝑑+(𝑣)=∑𝑣∈𝑉 𝑑−(𝑣)=|𝐸|∑v∈V d+(v)=∑v∈V d−(v)=|E|

若对一张无向图 𝐺 =(𝑉,𝐸)G=(V,E)，每个顶点的度数都是一个固定的常数 𝑘 k，则称 𝐺 G 为 𝑘 k- 正则图 (𝑘 k-regular graph)．

如果给定一个序列 a，可以找到一个图 G，以其为度数列，则称 a 是 可图化 的．

如果给定一个序列 a，可以找到一个简单图 G，以其为度数列，则称 a 是 可简单图化 的．

## 路径

途径 (walk)：途径是连接一连串顶点的边的序列，可以为有限或无限长度．形式化地说，一条有限途径 𝑤 w 是一个边的序列 𝑒 1,𝑒 2,…,𝑒 𝑘 e 1,e 2,…,e k，使得存在一个顶点序列 𝑣 0,𝑣 1,…,𝑣 𝑘 v 0,v 1,…,v k 满足 𝑒 𝑖 =(𝑣 𝑖−1,𝑣 𝑖)e i=(v i−1,v i)，其中 𝑖 ∈[1,𝑘]i∈[1,k]．这样的途径可以简写为 𝑣 0 →𝑣 1 →𝑣 2 →⋯ →𝑣 𝑘 v 0→v 1→v 2→⋯→v k．通常来说，边的数量 𝑘 k 被称作这条途径的 长度（如果边是带权的，长度通常指途径上的边权之和，题目中也可能另有定义）．

迹 (trail)：对于一条途径 𝑤 w，若 𝑒 1,𝑒 2,…,𝑒 𝑘 e 1,e 2,…,e k 两两互不相同，则称 𝑤 w 是一条迹．

路径 (path)（又称 简单路径 (simple path)）：对于一条迹 𝑤 w，若其连接的点的序列中点两两不同，则称 𝑤 w 是一条路径．

回路 (circuit)：对于一条迹 𝑤 w，若 𝑣 0 =𝑣 𝑘 v 0=v k，则称 𝑤 w 是一条回路．

环/圈 (cycle)（又称 简单回路/简单环 (simple circuit)）：对于一条回路 𝑤 w，若 𝑣 0 =𝑣 𝑘 v 0=v k 是点序列中唯一重复出现的点对，则称 𝑤 w 是一个环．

Warning

关于路径的定义在不同地方可能有所不同，如，「路径」可能指本文中的「途径」，「环」可能指本文中的「回路」．如果在题目中看到类似的词汇，且没有「简单路径」/「非简单路径」（即本文中的「途径」）等特殊说明，最好询问一下具体指什么．

## 子图

对一张图 𝐺 =(𝑉,𝐸)G=(V,E)，若存在另一张图 𝐻 =(𝑉′,𝐸′)H=(V′,E′) 满足 𝑉′ ⊆𝑉 V′⊆V 且 𝐸′ ⊆𝐸 E′⊆E，则称 𝐻 H 是 𝐺 G 的 子图 (subgraph)，记作 𝐻 ⊆𝐺 H⊆G．

若对 𝐻 ⊆𝐺 H⊆G，满足 ∀𝑢,𝑣 ∈𝑉′∀u,v∈V′，只要 (𝑢,𝑣) ∈𝐸(u,v)∈E，均有 (𝑢,𝑣) ∈𝐸′(u,v)∈E′，则称 𝐻 H 是 𝐺 G 的 导出子图/诱导子图 (induced subgraph)．

容易发现，一个图的导出子图仅由子图的点集决定，因此点集为 𝑉′V′(𝑉′ ⊆𝑉 V′⊆V) 的导出子图称为 𝑉′V′ 导出的子图，记作 𝐺[𝑉′]G[V′]．

若 𝐻 ⊆𝐺 H⊆G 满足 𝑉′ =𝑉 V′=V，则称 𝐻 H 为 𝐺 G 的 生成子图/支撑子图 (spanning subgraph)．

显然，𝐺 G 是自身的子图，支撑子图，导出子图；无边图 是 𝐺 G 的支撑子图．原图 𝐺 G 和无边图都是 𝐺 G 的平凡子图．

如果一张无向图 𝐺 G 的某个生成子图 𝐹 F 为 𝑘 k- 正则图，则称 𝐹 F 为 𝐺 G 的一个 𝑘 k- 因子 (𝑘 k-factor)．

如果有向图 𝐺 =(𝑉,𝐸)G=(V,E) 的导出子图 𝐻 =𝐺[𝑉∗]H=G[V∗] 满足 ∀𝑣 ∈𝑉∗,(𝑣,𝑢) ∈𝐸∀v∈V∗,(v,u)∈E，有 𝑢 ∈𝑉∗u∈V∗，则称 𝐻 H 为 𝐺 G 的一个 闭合子图 (closed subgraph)．

## 连通

### 无向图

对于一张无向图 𝐺 =(𝑉,𝐸)G=(V,E)，对于 𝑢,𝑣 ∈𝑉 u,v∈V，若存在一条途径使得 𝑣 0 =𝑢,𝑣 𝑘 =𝑣 v 0=u,v k=v，则称 𝑢 u 和 𝑣 v 是 连通的 (connected)．由定义，任意一个顶点和自身连通，任意一条边的两个端点连通．

若无向图 𝐺 =(𝑉,𝐸)G=(V,E)，满足其中任意两个顶点均连通，则称 𝐺 G 是 连通图 (connected graph)，𝐺 G 的这一性质称作 连通性 (connectivity)．

若 𝐻 H 是 𝐺 G 的一个连通子图，且不存在 𝐹 F 满足 𝐻 ⊊𝐹 ⊆𝐺 H⊊F⊆G 且 𝐹 F 为连通图，则 𝐻 H 是 𝐺 G 的一个 连通块/连通分量 (connected component)（极大连通子图）．

### 有向图

对于一张有向图 𝐺 =(𝑉,𝐸)G=(V,E)，对于 𝑢,𝑣 ∈𝑉 u,v∈V，若存在一条途径使得 𝑣 0 =𝑢,𝑣 𝑘 =𝑣 v 0=u,v k=v，则称 𝑢 u 可达 𝑣 v．由定义，任意一个顶点可达自身，任意一条边的起点可达终点．（无向图中的连通也可以视作双向可达．）

若一张有向图的节点两两互相可达，则称这张图是 强连通的 (strongly connected)．

若一张有向图的边替换为无向边后可以得到一张连通图，则称原来这张有向图是 弱连通的 (weakly connected)．

与连通分量类似，也有 弱连通分量 (weakly connected component)（极大弱连通子图）和 强连通分量 (strongly connected component)（极大强连通子图）．

相关算法请参见 强连通分量．

### 割

相关算法请参见 割点和桥 以及 双连通分量．

在本部分中，有向图的「连通」一般指「强连通」．

对于连通图 𝐺 =(𝑉,𝐸)G=(V,E)，若 𝑉′ ⊆𝑉 V′⊆V 且 𝐺[𝑉∖𝑉′]G[V∖V′]（即从 𝐺 G 中删去 𝑉′V′ 中的点）不是连通图，则 𝑉′V′ 是图 𝐺 G 的一个 点割集 (vertex cut/separating set)．大小为一的点割集又被称作 割点 (cut vertex)．

对于连通图 𝐺 =(𝑉,𝐸)G=(V,E) 和整数 𝑘 k，若 |𝑉| ≥𝑘 +1|V|≥k+1 且 𝐺 G 不存在大小为 𝑘 −1 k−1 的点割集，则称图 𝐺 G 是 𝑘 k- 点连通的 (𝑘 k-vertex-connected)，而使得上式成立的最大的 𝑘 k 被称作图 𝐺 G 的 点连通度 (vertex connectivity)，记作 𝜅(𝐺)κ(G)．（对于非完全图，点连通度即为最小点割集的大小，而完全图 𝐾 𝑛 K n 的点连通度为 𝑛 −1 n−1．）

对于图 𝐺 =(𝑉,𝐸)G=(V,E) 以及 𝑢,𝑣 ∈𝑉 u,v∈V 满足 𝑢 ≠𝑣 u≠v，𝑢 u 和 𝑣 v 不相邻，𝑢 u 可达 𝑣 v，若 𝑉′ ⊆𝑉 V′⊆V，𝑢,𝑣 ∉𝑉′u,v∉V′，且在 𝐺[𝑉∖𝑉′]G[V∖V′] 中 𝑢 u 和 𝑣 v 不连通，则 𝑉′V′ 被称作 𝑢 u 到 𝑣 v 的点割集．𝑢 u 到 𝑣 v 的最小点割集的大小被称作 𝑢 u 到 𝑣 v 的 局部点连通度 (local connectivity)，记作 𝜅(𝑢,𝑣)κ(u,v)．

还可以在边上作类似的定义：

对于连通图 𝐺 =(𝑉,𝐸)G=(V,E)，若 𝐸′ ⊆𝐸 E′⊆E 且 𝐺′ =(𝑉,𝐸 ∖𝐸′)G′=(V,E∖E′)（即从 𝐺 G 中删去 𝐸′E′ 中的边）不是连通图，则 𝐸′E′ 是图 𝐺 G 的一个 边割集 (edge cut)．大小为一的边割集又被称作 桥 (bridge)．

对于连通图 𝐺 =(𝑉,𝐸)G=(V,E) 和整数 𝑘 k，若 𝐺 G 不存在大小为 𝑘 −1 k−1 的边割集，则称图 𝐺 G 是 𝑘 k- 边连通的 (𝑘 k-edge-connected)，而使得上式成立的最大的 𝑘 k 被称作图 𝐺 G 的 边连通度 (edge connectivity)，记作 𝜆(𝐺)λ(G)．（对于任何图，边连通度即为最小边割集的大小．）

对于图 𝐺 =(𝑉,𝐸)G=(V,E) 以及 𝑢,𝑣 ∈𝑉 u,v∈V 满足 𝑢 ≠𝑣 u≠v，𝑢 u 可达 𝑣 v，若 𝐸′ ⊆𝐸 E′⊆E，且在 𝐺′ =(𝑉,𝐸 ∖𝐸′)G′=(V,E∖E′) 中 𝑢 u 和 𝑣 v 不连通，则 𝐸′E′ 被称作 𝑢 u 到 𝑣 v 的边割集．𝑢 u 到 𝑣 v 的最小边割集的大小被称作 𝑢 u 到 𝑣 v 的 局部边连通度 (local edge-connectivity)，记作 𝜆(𝑢,𝑣)λ(u,v)．

点双连通 (biconnected) 几乎与 2 2- 点连通完全一致，除了一条边连接两个点构成的图，它是点双连通的，但不是 2 2- 点连通的．换句话说，没有割点的连通图是点双连通的．

边双连通 (2 2-edge-connected) 与 2 2- 边双连通完全一致．换句话说，没有桥的连通图是边双连通的．

与连通分量类似，也有 点双连通分量 (biconnected component)（极大点双连通子图）和 边双连通分量 (2 2-edge-connected component)（极大边双连通子图）．

Whitney 定理：对任意的图 𝐺 G，有 𝜅(𝐺) ≤𝜆(𝐺) ≤𝛿(𝐺)κ(G)≤λ(G)≤δ(G)．（不等式中的三项分别为点连通度、边连通度、最小度．）

## 稀疏图/稠密图

若一张图的边数远小于其点数的平方，那么它是一张 稀疏图 (sparse graph)．

若一张图的边数接近其点数的平方，那么它是一张 稠密图 (dense graph)．

这两个概念并没有严格的定义，一般用于讨论 时间复杂度 为 𝑂(|𝑉|2)O(|V|2) 的算法与 𝑂(|𝐸|)O(|E|) 的算法的效率差异（在稠密图上这两种算法效率相当，而在稀疏图上 𝑂(|𝐸|)O(|E|) 的算法效率明显更高）．

## 补图

对于无向简单图 𝐺 =(𝑉,𝐸)G=(V,E)，它的 补图 (complement graph) 指的是这样的一张图：记作 ¯𝐺 G¯，满足 𝑉(¯𝐺) =𝑉(𝐺)V(G¯)=V(G)，且对任意节点对 (𝑢,𝑣)(u,v)，(𝑢,𝑣) ∈𝐸(¯𝐺)(u,v)∈E(G¯) 当且仅当 (𝑢,𝑣) ∉𝐸(𝐺)(u,v)∉E(G)．

## 反图

对于有向图 𝐺 =(𝑉,𝐸)G=(V,E)，它的 反图 (transpose graph) 指的是点集不变，每条边反向得到的图，即：若 𝐺 G 的反图为 𝐺′ =(𝑉,𝐸′)G′=(V,E′)，则 𝐸′ ={(𝑣,𝑢)|(𝑢,𝑣) ∈𝐸}E′={(v,u)|(u,v)∈E}．

## 特殊的图

若无向简单图 𝐺 G 满足任意不同两点间均有边，则称 𝐺 G 为 完全图 (complete graph)，𝑛 n 阶完全图记作 𝐾 𝑛 K n．若有向图 𝐺 G 满足任意不同两点间都有两条方向不同的边，则称 𝐺 G 为 有向完全图 (complete digraph)．

边集为空的图称为 无边图 (edgeless graph)、空图 (empty graph) 或 零图 (null graph)，𝑛 n 阶无边图记作 ――𝐾 𝑛 K―n 或 𝑁 𝑛 N n．𝑁 𝑛 N n 与 𝐾 𝑛 K n 互为补图．

Warning

零图 (null graph) 也可指 零阶图 (order-zero graph) 𝐾 0 K 0，即点集与边集均为空的图．

若有向简单图 𝐺 G 满足任意不同两点间都有恰好一条边（单向），则称 𝐺 G 为 竞赛图 (tournament graph)．

若无向简单图 𝐺 =(𝑉,𝐸)G=(V,E) 的所有边恰好构成一个圈，则称 𝐺 G 为 环图/圈图 (cycle graph)，𝑛 n(𝑛 ≥3 n≥3) 阶圈图记作 𝐶 𝑛 C n．易知，一张图为圈图的充分必要条件是，它是 2 2- 正则连通图．

若无向简单图 𝐺 =(𝑉,𝐸)G=(V,E) 满足，存在一个点 𝑣 v 为支配点，其余点之间没有边相连，则称 𝐺 G 为 星图/菊花图 (star graph)，𝑛 +1 n+1(𝑛 ≥1 n≥1) 阶星图记作 𝑆 𝑛 S n．

若无向简单图 𝐺 =(𝑉,𝐸)G=(V,E) 满足，存在一个点 𝑣 v 为支配点，其它点之间构成一个圈，则称 𝐺 G 为 轮图 (wheel graph)，𝑛 +1 n+1(𝑛 ≥3 n≥3) 阶轮图记作 𝑊 𝑛 W n．

若无向简单图 𝐺 =(𝑉,𝐸)G=(V,E) 的所有边恰好构成一条简单路径，则称 𝐺 G 为 链 (chain/path graph)，𝑛 n 阶的链记作 𝑃 𝑛 P n．易知，一条链由一个圈图删去一条边而得．

如果一张无向连通图不含环，则称它是一棵 树 (tree)．相关内容详见 树基础．

如果一张无向连通图包含恰好一个环，则称它是一棵 基环树 (pseudotree)．

如果一张有向弱连通图每个点的入度都为 1 1，则称它是一棵 基环外向树．

如果一张有向弱连通图每个点的出度都为 1 1，则称它是一棵 基环内向树．

多棵树可以组成一个 森林 (forest)，多棵基环树可以组成 基环森林 (pseudoforest)，多棵基环外向树可以组成 基环外向树森林，多棵基环内向树可以组成 基环内向森林 (functional graph)．

如果一张无向连通图的每条边最多在一个环内，则称它是一棵 仙人掌 (cactus)．多棵仙人掌可以组成 沙漠．

如果一张图的点集可以被分为两部分，每一部分的内部都没有连边，那么这张图是一张 二分图 (bipartite graph)．如果二分图中任何两个不在同一部分的点之间都有连边，那么这张图是一张 完全二分图 (complete bipartite graph/biclique)，一张两部分分别有 𝑛 n 个点和 𝑚 m 个点的完全二分图记作 𝐾 𝑛,𝑚 K n,m．相关内容详见 二分图．

如果一张图可以画在一个平面上，且没有两条边在非端点处相交，那么这张图是一张 平面图 (planar graph)．一张图的任何子图都不是 𝐾 5 K 5 或 𝐾 3,3 K 3,3 是其为一张平面图的充要条件．对于简单连通平面图 𝐺 =(𝑉,𝐸)G=(V,E) 且 𝑉 ≥3 V≥3，|𝐸| ≤3|𝑉| −6|E|≤3|V|−6．

## 同构

两个图 𝐺 G 和 𝐻 H，如果存在一个双射 𝑓 :𝑉(𝐺) →𝑉(𝐻)f:V(G)→V(H)，且满足 (𝑢,𝑣) ∈𝐸(𝐺)(u,v)∈E(G)，当且仅当 (𝑓(𝑢),𝑓(𝑣)) ∈𝐸(𝐻)(f(u),f(v))∈E(H)，则我们称 𝑓 f 为 𝐺 G 到 𝐻 H 的一个 同构 (isomorphism)，且图 𝐺 G 与图 𝐻 H 是 同构的 (isomorphic)，记作 𝐺 ≅𝐻 G≅H．

从定义可知，若 𝐺 ≅𝐻 G≅H，必须满足：

- |𝑉(𝐺)| =|𝑉(𝐻)|,|𝐸(𝐺)| =|𝐸(𝐻)||V(G)|=|V(H)|,|E(G)|=|E(H)|
- 𝐺 G 和 𝐻 H 结点度的非增序列相同
- 𝐺 G 和 𝐻 H 存在同构的导出子图

## 无向简单图的二元运算

对于无向简单图，我们可以定义如下二元运算：

交 (intersection)：图 𝐺 =(𝑉 1,𝐸 1),𝐻 =(𝑉 2,𝐸 2)G=(V 1,E 1),H=(V 2,E 2) 的交定义成图 𝐺 ∩𝐻 =(𝑉 1∩𝑉 2,𝐸 1∩𝐸 2)G∩H=(V 1∩V 2,E 1∩E 2)．

容易证明两个无向简单图的交还是无向简单图．

并 (union)：图 𝐺 =(𝑉 1,𝐸 1),𝐻 =(𝑉 2,𝐸 2)G=(V 1,E 1),H=(V 2,E 2) 的并定义成图 𝐺 ∪𝐻 =(𝑉 1∪𝑉 2,𝐸 1∪𝐸 2)G∪H=(V 1∪V 2,E 1∪E 2)．

和 (sum)/直和 (direct sum)：对于 𝐺 =(𝑉 1,𝐸 1),𝐻 =(𝑉 2,𝐸 2)G=(V 1,E 1),H=(V 2,E 2)，任意构造 𝐻′ ≅𝐻 H′≅H 使得 𝑉(𝐻′) ∩𝑉 1 =∅V(H′)∩V 1=∅(𝐻′H′ 可以等于 𝐻 H)．此时与 𝐺 ∪𝐻′G∪H′ 同构的任何图称为 𝐺 G 和 𝐻 H 的和/直和/不交并，记作 𝐺 +𝐻 G+H 或 𝐺 ⊕𝐻 G⊕H．

若 𝐺 G 与 𝐻 H 的点集本身不相交，则 𝐺 ∪𝐻 =𝐺 +𝐻 G∪H=G+H．

比如，森林可以定义成若干棵树的和．

并与和的区别

可以理解为，「并」会让两张图中「名字相同」的点、边合并，而「和」则不会．

## 特殊的点集/边集

### 支配集

对于无向图 𝐺 =(𝑉,𝐸)G=(V,E)，若 𝑉′ ⊆𝑉 V′⊆V 且 ∀𝑣 ∈(𝑉 ∖𝑉′)∀v∈(V∖V′) 存在边 (𝑢,𝑣) ∈𝐸(u,v)∈E 满足 𝑢 ∈𝑉′u∈V′，则 𝑉′V′ 是图 𝐺 G 的一个 支配集 (dominating set)．

无向图 𝐺 G 最小的支配集的大小记作 𝛾(𝐺)γ(G)．求一张图的最小支配集是 NP 困难 的．

对于有向图 𝐺 =(𝑉,𝐸)G=(V,E)，若 𝑉′ ⊆𝑉 V′⊆V 且 ∀𝑣 ∈(𝑉 ∖𝑉′)∀v∈(V∖V′) 存在边 (𝑢,𝑣) ∈𝐸(u,v)∈E 满足 𝑢 ∈𝑉′u∈V′，则 𝑉′V′ 是图 𝐺 G 的一个 出 - 支配集 (out-dominating set)．类似地，可以定义有向图的 入 - 支配集 (in-dominating set)．

有向图 𝐺 G 最小的出 - 支配集大小记作 𝛾+(𝐺)γ+(G)，最小的入 - 支配集大小记作 𝛾−(𝐺)γ−(G)．

### 边支配集

对于图 𝐺 =(𝑉,𝐸)G=(V,E)，若 𝐸′ ⊆𝐸 E′⊆E 且 ∀𝑒 ∈(𝐸 ∖𝐸′)∀e∈(E∖E′) 存在 𝐸′E′ 中的边与其有公共点，则称 𝐸′E′ 是图 𝐺 G 的一个 边支配集 (edge dominating set)．

求一张图的最小边支配集是 NP 困难 的．

### 独立集

对于图 𝐺 =(𝑉,𝐸)G=(V,E)，若 𝑉′ ⊆𝑉 V′⊆V 且 𝑉′V′ 中任意两点都不相邻，则 𝑉′V′ 是图 𝐺 G 的一个 独立集 (independent set)．

图 𝐺 G 最大的独立集的大小记作 𝛼(𝐺)α(G)．求一张图的最大独立集是 NP 困难 的．

### 匹配

对于图 𝐺 =(𝑉,𝐸)G=(V,E)，若 𝐸′ ⊆𝐸 E′⊆E 且 𝐸′E′ 中任意两条不同的边都没有公共的端点，且 𝐸′E′ 中任意一条边都不是自环，则 𝐸′E′ 是图 𝐺 G 的一个 匹配 (matching)，也可以叫作 边独立集 (independent edge set)．如果一个点是匹配中某条边的一个端点，则称这个点是 被匹配的 (matched)/饱和的 (saturated)，否则称这个点是 不被匹配的 (unmatched)．

边数最多的匹配被称作一张图的 最大匹配 (maximum-cardinality matching)．图 𝐺 G 的最大匹配的大小记作 𝜈(𝐺)ν(G)．

如果边带权，那么权重之和最大的匹配被称作一张图的 最大权匹配 (maximum-weight matching)．

如果一个匹配在加入任何一条边后都不再是一个匹配，那么这个匹配是一个 极大匹配 (maximal matching)．最大的极大匹配就是最大匹配，任何最大匹配都是极大匹配．极大匹配一定是边支配集，但边支配集不一定是匹配．最小极大匹配和最小边支配集大小相等，但最小边支配集不一定是匹配．求最小极大匹配是 NP 困难的．

如果在一个匹配中所有点都是被匹配的，那么这个匹配是一个 完美匹配 (perfect matching)．如果在一个匹配中只有一个点不被匹配，那么这个匹配是一个 准完美匹配 (near-perfect matching)．

求一张普通图或二分图的匹配或完美匹配个数都是 #P 完全 的．

对于一个匹配 𝑀 M，若一条路径以非匹配点为起点，每相邻两条边的其中一条在匹配中而另一条不在匹配中，则这条路径被称作一条 交替路径 (alternating path)；一条在非匹配点终止的交替路径，被称作一条 增广路径 (augmenting path)．

托特定理：𝑛 n 阶无向图 𝐺 G 有完美匹配当且仅当对于任意的 𝑉′ ⊂𝑉(𝐺)V′⊂V(G)，𝑝 o d d(𝐺 −𝑉′) ≤|𝑉′|p odd(G−V′)≤|V′|，其中 𝑝 o d d p odd 表示奇数阶连通分支数．

托特定理（推论）：任何无桥 3 - 正则图都有完美匹配．

### 点覆盖

对于图 𝐺 =(𝑉,𝐸)G=(V,E)，若 𝑉′ ⊆𝑉 V′⊆V 且 ∀𝑒 ∈𝐸∀e∈E 满足 𝑒 e 的至少一个端点在 𝑉′V′ 中，则称 𝑉′V′ 是图 𝐺 G 的一个 点覆盖 (vertex cover)．

点覆盖集必为支配集，但极小点覆盖集不一定是极小支配集．

一个点集是点覆盖的充要条件是其补集是独立集，因此最小点覆盖的补集是最大独立集．求一张图的最小点覆盖是 NP 困难 的．

一张图的任何一个匹配的大小都不超过其任何一个点覆盖的大小．完全二分图 𝐾 𝑛,𝑚 K n,m 的最大匹配和最小点覆盖大小都为 m i n(𝑛,𝑚)min(n,m)．

### 边覆盖

对于图 𝐺 =(𝑉,𝐸)G=(V,E)，若 𝐸′ ⊆𝐸 E′⊆E 且 ∀𝑣 ∈𝑉∀v∈V 满足 𝑣 v 与 𝐸′E′ 中的至少一条边相邻，则称 𝐸′E′ 是图 𝐺 G 的一个 边覆盖 (edge cover)．

最小边覆盖的大小记作 𝜌(𝐺)ρ(G)，可以由最大匹配贪心扩展求得：对于所有非匹配点，将其一条邻边加入最大匹配中，即得到了一个最小边覆盖．

最大匹配也可以由最小边覆盖求得：对于最小边覆盖中每对有公共点的边删去其中一条．

一张图的最小边覆盖的大小加上最大匹配的大小等于图的点数，即 𝜌(𝐺) +𝜈(𝐺) =|𝑉(𝐺)|ρ(G)+ν(G)=|V(G)|．

一张图的最大匹配的大小不超过最小边覆盖的大小，即 𝜈(𝐺) ≤𝜌(𝐺)ν(G)≤ρ(G)．特别地，完美匹配一定是一个最小边覆盖，这也是上式取到等号的唯一情况．

一张图的任何一个独立集的大小都不超过其任何一个边覆盖的大小．完全二分图 𝐾 𝑛,𝑚 K n,m 的最大独立集和最小边覆盖大小都为 m a x(𝑛,𝑚)max(n,m)．

### 团

对于图 𝐺 =(𝑉,𝐸)G=(V,E)，若 𝑉′ ⊆𝑉 V′⊆V 且 𝑉′V′ 中任意两个不同的顶点都相邻，则 𝑉′V′ 是图 𝐺 G 的一个 团 (clique)．团的导出子图是完全图．

如果一个团在加入任何一个顶点后都不再是一个团，则这个团是一个 极大团 (maximal clique)．

一张图的最大团的大小记作 𝜔(𝐺)ω(G)，最大团的大小等于其补图最大独立集的大小，即 𝜔(𝐺) =𝛼(¯𝐺)ω(G)=α(G¯)．求一张图的最大团是 NP 困难 的．

## 参考资料

OI 中转站 - 图论概念梳理

Wikipedia（以及相关概念的对应词条）

离散数学（修订版），田文成 周禄新 编著，天津文学出版社，P184-187

戴一奇，胡冠章，陈卫．图论与代数结构 [M]. 北京：清华大学出版社，1995.

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：ouuan, CCXXXI, Enter-tainer, Tiphereth-A, Backl1ght, c-forrest, EndlessCheng, Ir1d, Great-designer, IceySakura, Kaiser-Yang, mgt, shuzhouliu, sshwy, Steaunk, StudyingFather, xiaoh1024, zidian257, zjxx
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用