图论相关概念
本页面概述了图论中的一些概念，这些概念并不全是在 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 的每条边 𝑒𝑘 =(𝑢𝑘,𝑣𝑘)ek=(uk,vk) 都被赋予一个数作为该边的 权 ，则称 𝐺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∈SN(v)
简单图
自环 (loop) ：对 𝐸E 中的边 𝑒 =(𝑢,𝑣)e=(u,v)，若 𝑢 =𝑣u=v，则 𝑒e 被称作一个自环．
重边 (multiple edge) ：若 𝐸E 中存在两个完全相同的元素（边）𝑒1,𝑒2e1,e2，则它们被称作（一组）重边．
简单图 (simple graph) ：若一个图中没有自环和重边，它被称为简单图．具有至少两个顶点的简单无向图中一定存在度相同的结点．（鸽巢原理）
如果一张图中有自环或重边，则称它为 多重图 (multigraph) ．
Warning
在无向图中 (𝑢,𝑣)(u,v) 和 (𝑣,𝑢)(v,u) 算一组重边，而在有向图中，𝑢 →𝑣u→v 和 𝑣 →𝑢v→u 不为重边．
Warning
在题目中，如果没有特殊说明，是可以存在自环和重边的，在做题时需特殊考虑．
度数
与一个顶点 𝑣v 关联的边的条数称作该顶点的 度 (degree) ，记作 𝑑(𝑣)d(v)．特别地，对于边 (𝑣,𝑣)(v,v)，则每条这样的边要对 𝑑(𝑣)d(v) 产生 22 的贡献．
对于无向简单图，有 𝑑(𝑣) =|𝑁(𝑣)|d(v)=|N(v)|．
握手定理（又称图论基本定理）：对于任何无向图 𝐺 =(𝑉,𝐸)G=(V,E)，有 ∑𝑣∈𝑉𝑑(𝑣) =2|𝐸|∑v∈Vd(v)=2|E|．
推论：在任意图中，度数为奇数的点必然有偶数个．
若 𝑑(𝑣) =0d(v)=0，则称 𝑣v 为 孤立点 (isolated vertex) ．
若 𝑑(𝑣) =1d(v)=1，则称 𝑣v 为 叶节点 (leaf vertex) /悬挂点 (pendant vertex) ．
若 2 ∣𝑑(𝑣)2∣d(v)，则称 𝑣v 为 偶点 (even vertex) ．
若 2 ∤𝑑(𝑣)2∤d(v)，则称 𝑣v 为 奇点 (odd vertex) ．图中奇点的个数是偶数．
若 𝑑(𝑣) =|𝑉| −1d(v)=|V|−1，则称 𝑣v 为 支配点 (universal vertex) ．
对一张图，所有节点的度数的最小值称为 𝐺G 的 最小度 (minimum degree) ，记作 𝛿(𝐺)δ(G)；最大值称为 最大度 (maximum degree) ，记作 Δ(𝐺)Δ(G)．即：𝛿(𝐺) =min𝑣∈𝐺𝑑(𝑣)δ(G)=minv∈Gd(v)，Δ(𝐺) =max𝑣∈𝐺𝑑(𝑣)Δ(G)=maxv∈Gd(v)．
在有向图 𝐺 =(𝑉,𝐸)G=(V,E) 中，以一个顶点 𝑣v 为起点的边的条数称为该顶点的 出度 (out-degree) ，记作 𝑑+(𝑣)d+(v)．以一个顶点 𝑣v 为终点的边的条数称为该节点的 入度 (in-degree) ，记作 𝑑−(𝑣)d−(v)．显然 𝑑+(𝑣) +𝑑−(𝑣) =𝑑(𝑣)d+(v)+d−(v)=d(v)．
对于任何有向图 𝐺 =(𝑉,𝐸)G=(V,E)，有：
∑𝑣∈𝑉𝑑+(𝑣)=∑𝑣∈𝑉𝑑−(𝑣)=|𝐸|∑v∈Vd+(v)=∑v∈Vd−(v)=|E|
若对一张无向图 𝐺 =(𝑉,𝐸)G=(V,E)，每个顶点的度数都是一个固定的常数 𝑘k，则称 𝐺G 为 𝑘 k\- 正则图 (𝑘k-regular graph)．
如果给定一个序列 a，可以找到一个图 G，以其为度数列，则称 a 是 可图化 的．
如果给定一个序列 a，可以找到一个简单图 G，以其为度数列，则称 a 是 可简单图化 的．
路径
途径 (walk) ：途径是连接一连串顶点的边的序列，可以为有限或无限长度．形式化地说，一条有限途径 𝑤w 是一个边的序列 𝑒1,𝑒2,…,𝑒𝑘e1,e2,…,ek，使得存在一个顶点序列 𝑣0,𝑣1,…,𝑣𝑘v0,v1,…,vk 满足 𝑒𝑖 =(𝑣𝑖−1,𝑣𝑖)ei=(vi−1,vi)，其中 𝑖 ∈[1,𝑘]i∈[1,k]．这样的途径可以简写为 𝑣0 →𝑣1 →𝑣2 →⋯ →𝑣𝑘v0→v1→v2→⋯→vk．通常来说，边的数量 𝑘k 被称作这条途径的 长度 （如果边是带权的，长度通常指途径上的边权之和，题目中也可能另有定义）．
迹 (trail) ：对于一条途径 𝑤w，若 𝑒1,𝑒2,…,𝑒𝑘e1,e2,…,ek 两两互不相同，则称 𝑤w 是一条迹．
路径 (path) （又称 简单路径 (simple path) ）：对于一条迹 𝑤w，若其连接的点的序列中点两两不同，则称 𝑤w 是一条路径．
回路 (circuit) ：对于一条迹 𝑤w，若 𝑣0 =𝑣𝑘v0=vk，则称 𝑤w 是一条回路．
环/圈 (cycle) （又称 简单回路/简单环 (simple circuit) ）：对于一条回路 𝑤w，若 𝑣0 =𝑣𝑘v0=vk 是点序列中唯一重复出现的点对，则称 𝑤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 =𝑢,𝑣𝑘 =𝑣v0=u,vk=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 =𝑢,𝑣𝑘 =𝑣v0=u,vk=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 不存在大小为 𝑘 −1k−1 的点割集，则称图 𝐺G 是 𝑘 k\- 点连通的 (𝑘k-vertex-connected)，而使得上式成立的最大的 𝑘k 被称作图 𝐺G 的 点连通度 (vertex connectivity) ，记作 𝜅(𝐺)κ(G)．（对于非完全图，点连通度即为最小点割集的大小，而完全图 𝐾𝑛Kn 的点连通度为 𝑛 −1n−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 不存在大小为 𝑘 −1k−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) 几乎与 22\- 点连通完全一致，除了一条边连接两个点构成的图，它是点双连通的，但不是 22\- 点连通的．换句话说，没有割点的连通图是点双连通的．
边双连通 ( 22-edge-connected) 与 22\- 边双连通完全一致．换句话说，没有桥的连通图是边双连通的．
与连通分量类似，也有 点双连通分量 (biconnected component) （极大点双连通子图）和 边双连通分量 ( 22-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 阶完全图记作 𝐾𝑛Kn．若有向图 𝐺G 满足任意不同两点间都有两条方向不同的边，则称 𝐺G 为 有向完全图 (complete digraph) ．
边集为空的图称为 无边图 (edgeless graph) 、空图 (empty graph) 或 零图 (null graph) ，𝑛n 阶无边图记作 ――𝐾𝑛K―n 或 𝑁𝑛Nn．𝑁𝑛Nn 与 𝐾𝑛Kn 互为补图．
Warning
零图 (null graph) 也可指 零阶图 (order-zero graph) 𝐾0K0，即点集与边集均为空的图．
若有向简单图 𝐺G 满足任意不同两点间都有恰好一条边（单向），则称 𝐺G 为 竞赛图 (tournament graph) ．
若无向简单图 𝐺 =(𝑉,𝐸)G=(V,E) 的所有边恰好构成一个圈，则称 𝐺G 为 环图/圈图 (cycle graph) ，𝑛n(𝑛 ≥3n≥3) 阶圈图记作 𝐶𝑛Cn．易知，一张图为圈图的充分必要条件是，它是 22\- 正则连通图．
若无向简单图 𝐺 =(𝑉,𝐸)G=(V,E) 满足，存在一个点 𝑣v 为支配点，其余点之间没有边相连，则称 𝐺G 为 星图/菊花图 (star graph) ，𝑛 +1n+1(𝑛 ≥1n≥1) 阶星图记作 𝑆𝑛Sn．
若无向简单图 𝐺 =(𝑉,𝐸)G=(V,E) 满足，存在一个点 𝑣v 为支配点，其它点之间构成一个圈，则称 𝐺G 为 轮图 (wheel graph) ，𝑛 +1n+1(𝑛 ≥3n≥3) 阶轮图记作 𝑊𝑛Wn．
若无向简单图 𝐺 =(𝑉,𝐸)G=(V,E) 的所有边恰好构成一条简单路径，则称 𝐺G 为 链 (chain/path graph) ，𝑛n 阶的链记作 𝑃𝑛Pn．易知，一条链由一个圈图删去一条边而得．
如果一张无向连通图不含环，则称它是一棵 树 (tree) ．相关内容详见 树基础．
如果一张无向连通图包含恰好一个环，则称它是一棵 基环树 (pseudotree) ．
如果一张有向弱连通图每个点的入度都为 11，则称它是一棵 基环外向树 ．
如果一张有向弱连通图每个点的出度都为 11，则称它是一棵 基环内向树 ．
多棵树可以组成一个 森林 (forest) ，多棵基环树可以组成 基环森林 (pseudoforest) ，多棵基环外向树可以组成 基环外向树森林 ，多棵基环内向树可以组成 基环内向森林 (functional graph) ．
如果一张无向连通图的每条边最多在一个环内，则称它是一棵 仙人掌 (cactus) ．多棵仙人掌可以组成 沙漠 ．
如果一张图的点集可以被分为两部分，每一部分的内部都没有连边，那么这张图是一张 二分图 (bipartite graph) ．如果二分图中任何两个不在同一部分的点之间都有连边，那么这张图是一张 完全二分图 (complete bipartite graph/biclique) ，一张两部分分别有 𝑛n 个点和 𝑚m 个点的完全二分图记作 𝐾𝑛,𝑚Kn,m．相关内容详见 二分图．
如果一张图可以画在一个平面上，且没有两条边在非端点处相交，那么这张图是一张 平面图 (planar graph) ．一张图的任何子图都不是 𝐾5K5 或 𝐾3,3K3,3 是其为一张平面图的充要条件．对于简单连通平面图 𝐺 =(𝑉,𝐸)G=(V,E) 且 𝑉 ≥3V≥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=(V1,E1),H=(V2,E2) 的交定义成图 𝐺 ∩𝐻 =(𝑉1∩𝑉2,𝐸1∩𝐸2)G∩H=(V1∩V2,E1∩E2)．
容易证明两个无向简单图的交还是无向简单图．
并 (union) ：图 𝐺 =(𝑉1,𝐸1),𝐻 =(𝑉2,𝐸2)G=(V1,E1),H=(V2,E2) 的并定义成图 𝐺 ∪𝐻 =(𝑉1∪𝑉2,𝐸1∪𝐸2)G∪H=(V1∪V2,E1∪E2)．
和 (sum)/直和 (direct sum) ：对于 𝐺 =(𝑉1,𝐸1),𝐻 =(𝑉2,𝐸2)G=(V1,E1),H=(V2,E2)，任意构造 𝐻′ ≅𝐻H′≅H 使得 𝑉(𝐻′) ∩𝑉1 =∅V(H′)∩V1=∅(𝐻′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)，𝑝odd(𝐺 −𝑉′) ≤|𝑉′|podd(G−V′)≤|V′|，其中 𝑝oddpodd 表示奇数阶连通分支数．
托特定理（推论） ：任何无桥 3 - 正则图都有完美匹配．
点覆盖
对于图 𝐺 =(𝑉,𝐸)G=(V,E)，若 𝑉′ ⊆𝑉V′⊆V 且 ∀𝑒 ∈𝐸∀e∈E 满足 𝑒e 的至少一个端点在 𝑉′V′ 中，则称 𝑉′V′ 是图 𝐺G 的一个 点覆盖 (vertex cover) ．
点覆盖集必为支配集，但极小点覆盖集不一定是极小支配集．
一个点集是点覆盖的充要条件是其补集是独立集，因此最小点覆盖的补集是最大独立集．求一张图的最小点覆盖是 NP 困难 的．
一张图的任何一个匹配的大小都不超过其任何一个点覆盖的大小．完全二分图 𝐾𝑛,𝑚Kn,m 的最大匹配和最小点覆盖大小都为 min(𝑛,𝑚)min(n,m)．
边覆盖
对于图 𝐺 =(𝑉,𝐸)G=(V,E)，若 𝐸′ ⊆𝐸E′⊆E 且 ∀𝑣 ∈𝑉∀v∈V 满足 𝑣v 与 𝐸′E′ 中的至少一条边相邻，则称 𝐸′E′ 是图 𝐺G 的一个 边覆盖 (edge cover) ．
最小边覆盖的大小记作 𝜌(𝐺)ρ(G)，可以由最大匹配贪心扩展求得：对于所有非匹配点，将其一条邻边加入最大匹配中，即得到了一个最小边覆盖．
最大匹配也可以由最小边覆盖求得：对于最小边覆盖中每对有公共点的边删去其中一条．
一张图的最小边覆盖的大小加上最大匹配的大小等于图的点数，即 𝜌(𝐺) +𝜈(𝐺) =|𝑉(𝐺)|ρ(G)+ν(G)=|V(G)|．
一张图的最大匹配的大小不超过最小边覆盖的大小，即 𝜈(𝐺) ≤𝜌(𝐺)ν(G)≤ρ(G)．特别地，完美匹配一定是一个最小边覆盖，这也是上式取到等号的唯一情况．
一张图的任何一个独立集的大小都不超过其任何一个边覆盖的大小．完全二分图 𝐾𝑛,𝑚Kn,m 的最大独立集和最小边覆盖大小都为 max(𝑛,𝑚)max(n,m)．
团
对于图 𝐺 =(𝑉,𝐸)G=(V,E)，若 𝑉′ ⊆𝑉V′⊆V 且 𝑉′V′ 中任意两个不同的顶点都相邻，则 𝑉′V′ 是图 𝐺G 的一个 团 (clique) ．团的导出子图是完全图．
如果一个团在加入任何一个顶点后都不再是一个团，则这个团是一个 极大团 (maximal clique) ．
一张图的最大团的大小记作 𝜔(𝐺)ω(G)，最大团的大小等于其补图最大独立集的大小，即 𝜔(𝐺) =𝛼(¯𝐺)ω(G)=α(G¯)．求一张图的最大团是 NP 困难 的．
参考资料
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 协议之条款下提供，附加条款亦可能应用