图论相关概念
是时候写这篇总结了。部分内容还有待考证。
不过大部分都是直接从 参考文献[1] 搬过来的。
图的定义
图 (graph) 是一个二元组 \(G=(V(G), E(G))\) ,其中:
\(V(G)\) 是非空集,称为 点集 (vertex set) 。
对于 \(V(G)\) 中的每个元素,我们称其为 顶点 (vertex) 或 节点 (node),简称 点 。
\(\left| V(G) \right|\) 也被称作图 \(G\) 的 阶 (order)。
\(E(G)\) 为 \(V(G)\) 各节点之间边的集合,称为 边集 (edge set)。
形象地说,图是由若干点以及连接点与点的边构成的。
事实上,我们常用 \(G=(V,E)\) 表示图,其中 \(V\) 表示点集,\(E\) 表示边集。
带权图
若 \(G\) 的每条边 \(e_k=(u_k,v_k)\) 都被赋予一个数作为该边的 权,则称 \(G\) 为 赋权图 或 带权图。
如果这些权都是正实数,就称 \(G\) 为 正权图。
有限图与无限图
设 \(G = (V,E)\) ,则
当 \(V\) 和 \(E\) 都是有限集合时,称 \(G\) 为 有限图。
当 \(V\) 或 \(E\) 是无限集合时,称 \(G\) 为 无限图。
无向图、有向图、混合图
图有多种,包括 无向图 (undirected graph),有向图 (directed graph),混合图 (mixed graph) 等。
若 \(G\) 为无向图,则 \(E\) 中的每个元素为一个无序二元组 \((u, v)\),称作 无向边 (undirected edge),简称 边 (edge),其中 \(u, v \in V\)。设 \(e = (u, v)\),则 \(u\) 和 \(v\) 称为 \(e\) 的 端点 (endpoint)。
若 \(G\) 为有向图,则 \(E\) 中的每一个元素为一个有序二元组 \((u, v)\),有时也写作 \(u \to v\),称作 有向边 (directed edge) 或 弧 (arc),在不引起混淆的情况下也可以称作 边 (edge)。设 \(e = u \to v\),则此时 \(u\) 称为 \(e\) 的 起点 (tail),\(v\) 称为 \(e\) 的 终点 (head),起点和终点也称为 \(e\) 的 端点 (endpoint)。并称 \(u\) 是 \(v\) 的直接前驱,\(v\) 是 \(u\) 的直接后继。
若 \(G\) 为混合图,则 \(E\) 中既有向边,又有无向边。
为什么起点是 tail,终点是 head 呢?
因为边通常用箭头表示,而箭头是从“尾”指向“头”的。
“节点” 与 “结点”
不知道你有没有好奇过, “节点” 和 “结点”
究竟有什么区别?
- 节点是一个实体具有处理的能力
- 结点是一个交叉点,是一个标记,一般算法中的点都称为结点。
节点被认为是一个实体,有处理能力,比如网络上的一台计算机。
而结点则只是一个交叉点,像“结绳记事”,打个结,做个标记,仅此而已。
在数据结构中,对于线性结构通常用“结点”描述,对于非线性结构通常用“节点”描述。
然而“节点”和“结点”的混淆使用已成普遍现象。
相邻
在无向图 \(G = (V, E)\) 中,若点 \(v\) 是边 \(e\) 的一个端点,则称 \(v\) 和 \(e\) 是 关联的 (incident) 或 相邻的 (adjacent)。对于两顶点 \(u\) 和 \(v\),若存在边 \((u, v)\),则称 \(u\) 和 \(v\) 是 相邻的 (adjacent)。
一个顶点 \(v \in V\) 的 邻域 (neighborhood) 是所有与之相邻的顶点所构成的集合,记作 \(N(v)\)。
一个点集 \(S\) 的邻域是所有与 \(S\) 中至少一个点相邻的点所构成的集合,记作 \(N(S)\),即:
\[ N(S) = \bigcup_{v \in S} N(v) \]
度数
与一个顶点 \(v\) 关联的边的条数称作该顶点的 度 (degree),记作 \(d(v)\)。特别地,对于边 \((v, v)\),则每条这样的边要对 \(d(v)\) 产生 \(2\) 的贡献。
对于无向简单图,有 \(d(v) = \left| N(v) \right|\)。
握手定理(又称图论基本定理):对于任何无向图 \(G = (V, E)\),有 \(\sum_{v \in V} d(v) = 2 \left| E \right|\)。
推论:在任意图中,度数为奇数的点必然有偶数个。
若 \(d(v) = 0\),则称 \(v\) 为 孤立点 (isolated vertex)。
若 \(d(v) = 1\),则称 \(v\) 为 叶节点 (leaf vertex)/悬挂点 (pendant vertex)。
若 \(2 \mid d(v)\),则称 \(v\) 为 偶点 (even vertex)。
若 \(2 \nmid d(v)\),则称 \(v\) 为 奇点 (odd vertex)。图中奇点的个数是偶数。
若 \(d(v) = \left| V \right| - 1\),则称 \(v\) 为 支配点 (universal vertex)。
对一张图,所有节点的度数的最小值称为 \(G\) 的 最小度 (minimum degree),记作 \(\delta (G)\);最大值称为 最大度 (maximum degree),记作 \(\Delta (G)\)。即:\(\delta (G) = \min_{v \in G} d(v)\),\(\Delta (G) = \max_{v \in 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)\),有:
\[ \sum_{v \in V} d^+(v) = \sum_{v \in V} d^-(v) = \left| E \right| \]
若对一张无向图 \(G = (V, E)\),每个顶点的度数都是一个固定的常数 \(k\),则称 \(G\) 为 \(k\) - 正则图 (\(k\)-regular graph)。
如果给定一个序列 \(a\),可以找到一个图 \(G\),以其为度数列,则称 \(a\) 是 可图化 的。
如果给定一个序列 \(a\),可以找到一个简单图 \(G\),以其为度数列,则称 \(a\) 是 可简单图化 的。
简单图
自环 (loop):对 \(E\) 中的边 \(e = (u, v)\),若 \(u = v\),则 \(e\) 被称作一个自环。
重边 (multiple edge):若 \(E\) 中存在两个完全相同的元素(边)\(e_1, e_2\),则它们被称作(一组)重边。
在无向图中 \((u, v)\) 和 \((v, u)\) 算一组重边,而在有向图中,\(u \to v\) 和 \(v \to u\) 不为重边。
在题目中,如果没有特殊说明,是可以存在自环和重边的,在做题时需特殊考虑。
简单图 (simple graph):若一个图中没有自环和重边,它被称为简单图。具有至少两个顶点的简单无向图中一定存在度相同的节点。(鸽巢原理)
如果一张图中有自环或重边,则称它为 多重图 (multigraph)。
路径
途径 (walk):途径是连接一连串顶点的边的序列,可以为有限或无限长度。形式化地说,一条有限途径 \(w\) 是一个边的序列 \(e_1, e_2, \ldots, e_k\),使得存在一个顶点序列 \(v_0, v_1, \ldots, v_k\) 满足 \(e_i = (v_{i-1}, v_i)\),其中 \(i \in [1, k]\)。这样的途径可以简写为 \(v_0 \to v_1 \to v_2 \to \cdots \to v_k\)。通常来说,边的数量 \(k\) 被称作这条途径的 长度(如果边是带权的,长度通常指途径上的边权之和,题目中也可能另有定义)。
迹 (trail):对于一条途径 \(w\),若 \(e_1, e_2, \ldots, e_k\) 两两互不相同,则称 \(w\) 是一条迹。
路径 (path)(又称 简单路径 (simple path)):对于一条迹 \(w\),若其连接的点的序列中点两两不同,则称 \(w\) 是一条路径。
回路 (circuit):对于一条迹 \(w\),若 \(v_0 = v_k\),则称 \(w\) 是一条回路。
环/圈 (cycle)(又称 简单回路/简单环 (simple circuit)):对于一条回路 \(w\),若 \(v_0 = v_k\) 是点序列中唯一重复出现的点对,则称 \(w\) 是一个环。
欧拉通路:通过无向图中所有边恰好一次且行遍所有顶点的通路。
欧拉回路:通过无向图中所有边恰好一次且行遍所有顶点的回路。
哈密顿通路:通过无向图中所有顶点一次且仅一次的通路。
哈密顿回路:通过无向图中所有顶点一次且仅一次的回路。
欧拉图:若无向图存在欧拉回路,则该无向图为欧拉图
注意欧拉图不一定联通因为它只要求经过所有边
例如四个节点的无向图,边为
(1,2),(2,3),(1,3)
,4
是个单点
关于路径的定义在不同地方可能有所不同,如,“路径”可能指本文中的“途径”,“环”可能指本文中的“回路”。如果在题目中看到类似的词汇,且没有“简单路径”/“非简单路径”(即本文中的“途径”)等特殊说明,最好询问一下具体指什么。
图的直径:记 \(d(u,v)\) 表示 \(u\) 到 \(v\) 的一条最短路径的长,则图的直径为 \(\max_{u\ne v} d(u,v)\) 。
子图
对一张图 \(G = (V, E)\),若存在另一张图 \(H = (V', E')\) 满足 \(V' \subseteq V\) 且 \(E' \subseteq E\),则称 \(H\) 是 \(G\) 的 子图 (subgraph),记作 \(H \subseteq G\)。
若对 \(H \subseteq G\),满足 \(\forall u, v \in V'\),只要 \((u, v) \in E\),均有 \((u, v) \in E'\),则称 \(H\) 是 \(G\) 的 导出子图/诱导子图 (induced subgraph)。
容易发现,一个图的导出子图仅由子图的点集决定,因此点集为 \(V'\)(\(V' \subseteq V\)) 的导出子图称为 \(V'\) 导出的子图,记作 \(G \left[ V' \right]\)。
若 \(H \subseteq G\) 满足 \(V' = V\),则称 \(H\) 为 \(G\) 的 生成子图/支撑子图 (spanning subgraph)。
显然,\(G\) 是自身的子图,支撑子图,导出子图;无边图 是 \(G\) 的支撑子图。原图 \(G\) 和无边图都是 \(G\) 的平凡子图。
如果一张无向图 \(G\) 的某个生成子图 \(F\) 为 \(k\)- 正则图,则称 \(F\) 为 \(G\) 的一个 \(k\)- 因子 (\(k\)-factor)。
如果有向图 \(G = (V, E)\) 的导出子图 \(H = G \left[ V^\ast \right]\) 满足 \(\forall v \in V^\ast, (v, u) \in E\),有 \(u \in V^\ast\),则称 \(H\) 为 \(G\) 的一个 闭合子图 (closed subgraph)。
若图 \(G=(V,E)\) 的点集 \(V\) 可以被分解为 \(k\) 个两两不交非空子集的并,并且没有任何一条边的两个端点都在同一个子集中,则称 \(G\) 为 \(k\) 部图 ,记作 \(G = (V_1,V_2,\cdots,V_k;E)\) 。当 \(k=2\) 时,我们通常称之为二分图或偶图,见下文。
若 \(k\) 部图 \(G = (V_1,V_2,\cdots,V_k;E)\) 中,任何两点 \(u \in V_i,v \in V_j, i \ne j\) 均有 \((i,j) \in E\) ,则称 \(G\) 为完全 \(k\) 部图
图的连通性
无向图
对于一张无向图 \(G = (V, E)\),对于 \(u, v \in V\),若存在一条途径使得 \(v_0 = u, v_k = v\),则称 \(u\) 和 \(v\) 是 连通的 (connected)。由定义,任意一个顶点和自身连通,任意一条边的两个端点连通。
若无向图 \(G = (V, E)\),满足其中任意两个顶点均连通,则称 \(G\) 是 连通图 (connected graph),\(G\) 的这一性质称作 连通性 (connectivity)。
若 \(H\) 是 \(G\) 的一个连通子图,且不存在 \(F\) 满足 \(H\subsetneq F \subseteq G\) 且 \(F\) 为连通图,则 \(H\) 是 \(G\) 的一个 连通块/连通分量 (connected component)(极大连通子图)。
有向图
对于一张有向图 \(G = (V, E)\),对于 \(u, v \in V\),若存在一条途径使得 \(v_0 = u, v_k = v\),则称 \(u\) 可达 \(v\)。由定义,任意一个顶点可达自身,任意一条边的起点可达终点。(无向图中的连通也可以视作双向可达。)
若一张有向图的节点两两互相可达,则称这张图是 强连通的 (strongly connected)。
若一张有向图的边替换为无向边后可以得到一张连通图,则称原来这张有向图是 弱连通的 (weakly connected)。
与连通分量类似,也有 弱连通分量 (weakly connected component)(极大弱连通子图)和 强连通分量 (strongly connected component)(极大强连通子图)。
割
在本部分中,有向图的“连通”一般指“强连通”。
对于连通图 \(G = (V, E)\),若 \(V'\subseteq V\) 且 \(G\left[V\setminus V'\right]\)(即从 \(G\) 中删去 \(V'\) 中的点)不是连通图,则 \(V'\) 是图 \(G\) 的一个 点割集 (vertex cut/separating set)。大小为一的点割集又被称作 割点 (cut vertex)。
对于连通图 \(G = (V, E)\) 和整数 \(k\),若 \(|V|\ge k+1\) 且 \(G\) 不存在大小为 \(k-1\) 的点割集,则称图 \(G\) 是 \(k\)- 点连通的 (\(k\)-vertex-connected),而使得上式成立的最大的 \(k\) 被称作图 \(G\) 的 点连通度 (vertex connectivity),记作 \(\kappa(G)\)。(对于非完全图,点连通度即为最小点割集的大小,而完全图 \(K_n\) 的点连通度为 \(n-1\)。)
对于图 \(G = (V, E)\) 以及 \(u, v\in V\) 满足 \(u\ne v\),\(u\) 和 \(v\) 不相邻,\(u\) 可达 \(v\),若 \(V'\subseteq V\),\(u, v\notin V'\),且在 \(G\left[V\setminus V'\right]\) 中 \(u\) 和 \(v\) 不连通,则 \(V'\) 被称作 \(u\) 到 \(v\) 的点割集。\(u\) 到 \(v\) 的最小点割集的大小被称作 \(u\) 到 \(v\) 的 局部点连通度 (local connectivity),记作 \(\kappa(u, v)\)。
还可以在边上作类似的定义:
对于连通图 \(G = (V, E)\),若 \(E'\subseteq E\) 且 \(G' = (V, E\setminus E')\)(即从 \(G\) 中删去 \(E'\) 中的边)不是连通图,则 \(E'\) 是图 \(G\) 的一个 边割集 (edge cut)。大小为一的边割集又被称作 桥 (bridge)。
对于连通图 \(G = (V, E)\) 和整数 \(k\),若 \(G\) 不存在大小为 \(k-1\) 的边割集,则称图 \(G\) 是 \(k\)- 边连通的 (\(k\)-edge-connected),而使得上式成立的最大的 \(k\) 被称作图 \(G\) 的 边连通度 (edge connectivity),记作 \(\lambda(G)\)。(对于任何图,边连通度即为最小边割集的大小。)
对于图 \(G = (V, E)\) 以及 \(u, v\in V\) 满足 \(u\ne v\),\(u\) 可达 \(v\),若 \(E'\subseteq E\),且在 \(G'=(V, E\setminus E')\) 中 \(u\) 和 \(v\) 不连通,则 \(E'\) 被称作 \(u\) 到 \(v\) 的边割集。\(u\) 到 \(v\) 的最小边割集的大小被称作 \(u\) 到 \(v\) 的 局部边连通度 (local edge-connectivity),记作 \(\lambda(u, v)\)。
点双连通 (biconnected) 几乎与 \(2\)- 点连通完全一致,除了一条边连接两个点构成的图,它是点双连通的,但不是 \(2\)- 点连通的。换句话说,没有割点的连通图是点双连通的。
边双连通 (\(2\)-edge-connected) 与 \(2\)- 边双连通完全一致。换句话说,没有桥的连通图是边双连通的。
与连通分量类似,也有 点双连通分量 (biconnected component)(极大点双连通子图)和 边双连通分量 (\(2\)-edge-connected component)(极大边双连通子图)。
Whitney 定理:对任意的图 \(G\),有 \(\kappa(G)\le \lambda(G)\le \delta(G)\)。(不等式中的三项分别为点连通度、边连通度、最小度。)
稀疏图/稠密图
若一张图的边数远小于其点数的平方,那么它是一张 稀疏图 (sparse graph)。
若一张图的边数接近其点数的平方,那么它是一张 稠密图 (dense graph)。
这两个概念并没有严格的定义,一般用于讨论时间复杂度为 \(\mathcal{O}(|V|^2)\) 的算法与 \(\mathcal{O}(|E|)\) 的算法的效率差异(在稠密图上这两种算法效率相当,而在稀疏图上 \(\mathcal{O}(|E|)\) 的算法效率明显更高)。
经典的例子:正权图单源最短路径算法 Dijkstra
朴素做法 \(\mathcal{O}(|E| + |V|^2)\) ,常见的优先队列优化 \(\mathcal{O}\left((|V|+|E|) \log |E| \right)\) ,详见 Dijkstra及其复杂度证明
补图
对于无向简单图 \(G = (V, E)\),它的 补图 (complement graph) 指的是这样的一张图:记作 \(\bar G\),满足 \(V ( \bar G ) = V \left( G \right)\),且对任意节点对 \((u, v)\),\((u, v) \in E ( \bar G )\) 当且仅当 \((u, v) \notin E \left( G \right)\)。
反图
对于有向图 \(G = (V, E)\),它的 反图 (transpose graph) 指的是点集不变,每条边反向得到的图,即:若 \(G\) 的反图为 \(G'=(V, E')\),则 \(E'=\{(v, u)|(u, v)\in E\}\)。
特殊的图
若无向简单图 \(G\) 满足任意不同两点间均有边,则称 \(G\) 为 完全图 (complete graph),\(n\) 阶完全图记作 \(K_n\)。若有向图 \(G\) 满足任意不同两点间都有两条方向不同的边,则称 \(G\) 为 有向完全图 (complete digraph)。
边集为空的图称为 无边图 (edgeless graph)、空图 (empty graph) 或 零图 (null graph),\(n\) 阶无边图记作 \(\overline{K}_n\) 或 \(N_n\)。\(N_n\) 与 \(K_n\) 互为补图。
注意,零图 (null graph) 也可指 零阶图 (order-zero graph) \(K_0\),即点集与边集均为空的图。
若有向简单图 \(G\) 满足任意不同两点间都有恰好一条边(单向),则称 \(G\) 为 竞赛图 (tournament graph)。
若无向简单图 \(G = \left( V, E \right)\) 的所有边恰好构成一个圈,则称 \(G\) 为 环图/圈图 (cycle graph),\(n\)(\(n \geq 3\)) 阶圈图记作 \(C_n\)。易知,一张图为圈图的充分必要条件是,它是 \(2\)- 正则连通图。
若无向简单图 \(G = \left( V, E \right)\) 满足,存在一个点 \(v\) 为支配点,其余点之间没有边相连,则称 \(G\) 为 星图/菊花图 (star graph),\(n + 1\)(\(n \geq 1\)) 阶星图记作 \(S_n\)。
若无向简单图 \(G = \left( V, E \right)\) 满足,存在一个点 \(v\) 为支配点,其它点之间构成一个圈,则称 \(G\) 为 轮图 (wheel graph),\(n + 1\)(\(n \geq 3\)) 阶轮图记作 \(W_n\)。
若无向简单图 \(G = \left( V, E \right)\) 的所有边恰好构成一条简单路径,则称 \(G\) 为 链 (chain/path graph),\(n\) 阶的链记作 \(P_n\)。易知,一条链由一个圈图删去一条边而得。
如果一张无向连通图不含环,则称它是一棵 树 (tree)。
如果一张无向连通图包含恰好一个环,则称它是一棵 基环树 (pseudotree)。
如果一张有向弱连通图每个点的入度都为 \(1\),则称它是一棵 基环外向树。
如果一张有向弱连通图每个点的出度都为 \(1\),则称它是一棵 基环内向树。
多棵树可以组成一个 森林 (forest),多棵基环树可以组成 基环森林 (pseudoforest),多棵基环外向树可以组成 基环外向树森林,多棵基环内向树可以组成 基环内向森林 (functional graph)。
如果一张无向连通图的每条边最多在一个环内,则称它是一棵 仙人掌 (cactus)。多棵仙人掌可以组成 沙漠。
这里的采用了边仙人掌的定义,点仙人掌的定义为:每个节点最多在一个环内。
基本上没啥区别,目前只在 洛谷P2478 [SDOI2010]城市规划 里碰到过点仙人掌。
如果一张图的点集可以被分为两部分,每一部分的内部都没有连边,那么这张图是一张 二分图 (bipartite graph)。如果二分图中任何两个不在同一部分的点之间都有连边,那么这张图是一张 完全二分图 (complete bipartite graph/biclique),一张两部分分别有 \(n\) 个点和 \(m\) 个点的完全二分图记作 \(K_{n, m}\)。
如果一张图可以画在一个平面上,且没有两条边在非端点处相交,那么这张图是一张 平面图 (planar graph)。一张图的任何子图都不是 \(K_5\) 或 \(K_{3, 3}\) 是其为一张平面图的充要条件。对于简单连通平面图 \(G=(V, E)\) 且 \(V\ge 3\),\(|E|\le 3|V|-6\)。
图的同构
两个图 \(G\) 和 \(H\),如果存在一个双射 \(f : V(G) \to V(H)\),且满足 \((u,v)\in E(G)\),当且仅当 \((f(u),f(v))\in E(H)\),则我们称 \(f\) 为 \(G\) 到 \(H\) 的一个 同构 (isomorphism),且图 \(G\) 与图 \(H\) 是 同构的 (isomorphic),记作 \(G \cong H\)。
从定义可知,若 \(G \cong H\),必须满足:
- \(|V(G)|=|V(H)|,|E(G)|=|E(H)|\)
- \(G\) 和 \(H\) 节点度的非增序列相同
- \(G\) 和 \(H\) 存在同构的导出子图
无向简单图的二元运算
对于无向简单图,我们可以定义如下二元运算:
交 (intersection):图 \(G = \left( V_1, E_1 \right), H = \left( V_2, E_2 \right)\) 的交定义成图 \(G \cap H = \left( V_1 \cap V_2, E_1 \cap E_2 \right)\)。
容易证明两个无向简单图的交还是无向简单图。
并 (union):图 \(G = \left( V_1, E_1 \right), H = \left( V_2, E_2 \right)\) 的并定义成图 \(G \cup H = \left( V_1 \cup V_2, E_1 \cup E_2 \right)\)。
和 (sum)/直和 (direct sum):对于 \(G = \left( V_1, E_1 \right), H = \left( V_2, E_2 \right)\),任意构造 \(H' \cong H\) 使得 \(V \left( H' \right) \cap V_1 = \varnothing\)(\(H'\) 可以等于 \(H\))。此时与 \(G \cup H'\) 同构的任何图称为 \(G\) 和 \(H\) 的和/直和/不交并,记作 \(G + H\) 或 \(G \oplus H\)。
若 \(G\) 与 \(H\) 的点集本身不相交,则 \(G \cup H = G + H\)。
比如,森林可以定义成若干棵树的和。
并与和的区别
可以理解为,“并”会让两张图中“名字相同”的点、边合并,而“和”则不会。
特殊的点集/边集
支配集
对于无向图 \(G=(V, E)\),若 \(V'\subseteq V\) 且 \(\forall v\in(V\setminus V')\) 存在边 \((u, v)\in E\) 满足 \(u\in V'\),则 \(V'\) 是图 \(G\) 的一个 支配集 (dominating set)。
无向图 \(G\) 最小的支配集的大小记作 \(\gamma(G)\)。求一张图的最小支配集是 NP 困难 的。
对于有向图 \(G=(V, E)\),若 \(V'\subseteq V\) 且 \(\forall v\in(V\setminus V')\) 存在边 \((u, v)\in E\) 满足 \(u\in V'\),则 \(V'\) 是图 \(G\) 的一个 出 - 支配集 (out-dominating set)。类似地,可以定义有向图的 入 - 支配集 (in-dominating set)。
有向图 \(G\) 最小的出 - 支配集大小记作 \(\gamma^+(G)\),最小的入 - 支配集大小记作 \(\gamma^-(G)\)。
边支配集
对于图 \(G=(V, E)\),若 \(E'\subseteq E\) 且 \(\forall e\in(E\setminus E')\) 存在 \(E'\) 中的边与其有公共点,则称 \(E'\) 是图 \(G\) 的一个 边支配集 (edge dominating set)。
求一张图的最小边支配集是 NP 困难 的。
独立集
对于图 \(G=(V, E)\),若 \(V'\subseteq V\) 且 \(V'\) 中任意两点都不相邻,则 \(V'\) 是图 \(G\) 的一个 独立集 (independent set)。
图 \(G\) 最大的独立集的大小记作 \(\alpha(G)\)。求一张图的最大独立集是 NP 困难 的。
匹配
对于图 \(G=(V, E)\),若 \(E'\in E\) 且 \(E'\) 中任意两条不同的边都没有公共的端点,且 \(E'\) 中任意一条边都不是自环,则 \(E'\) 是图 \(G\) 的一个 匹配 (matching),也可以叫作 边独立集 (independent edge set)。如果一个点是匹配中某条边的一个端点,则称这个点是 被匹配的 (matched)/饱和的 (saturated),否则称这个点是 不被匹配的 (unmatched)。
边数最多的匹配被称作一张图的 最大匹配 (maximum-cardinality matching)。图 \(G\) 的最大匹配的大小记作 \(\nu(G)\)。
如果边带权,那么权重之和最大的匹配被称作一张图的 最大权匹配 (maximum-weight matching)。
如果一个匹配在加入任何一条边后都不再是一个匹配,那么这个匹配是一个 极大匹配 (maximal matching)。最大的极大匹配就是最大匹配,任何最大匹配都是极大匹配。极大匹配一定是边支配集,但边支配集不一定是匹配。最小极大匹配和最小边支配集大小相等,但最小边支配集不一定是匹配。求最小极大匹配是 NP 困难的。
如果在一个匹配中所有点都是被匹配的,那么这个匹配是一个 完美匹配 (perfect matching)。如果在一个匹配中只有一个点不被匹配,那么这个匹配是一个 准完美匹配 (near-perfect matching)。
求一张普通图或二分图的匹配或完美匹配个数都是 P 完全 的。
对于一个匹配 \(M\),若一条路径以非匹配点为起点,每相邻两条边的其中一条在匹配中而另一条不在匹配中,则这条路径被称作一条 交替路径 (alternating path);一条在非匹配点终止的交替路径,被称作一条 增广路径 (augmenting path)。
托特定理:\(n\) 阶无向图 \(G\) 有完美匹配当且仅当对于任意的 \(V' \subset V(G)\),\(p_{\text{奇}}(G-V')\leq |V'|\),其中 \(p_{\text{奇}}\) 表示奇数阶连通分支数。
托特定理(推论):任何无桥 3 - 正则图都有完美匹配。
点覆盖
对于图 \(G=(V, E)\),若 \(V'\subseteq V\) 且 \(\forall e\in E\) 满足 \(e\) 的至少一个端点在 \(V'\) 中,则称 \(V'\) 是图 \(G\) 的一个 点覆盖 (vertex cover)。
点覆盖集必为支配集,但极小点覆盖集不一定是极小支配集。
一个点集是点覆盖的充要条件是其补集是独立集,因此最小点覆盖的补集是最大独立集。求一张图的最小点覆盖是 NP 困难 的。
一张图的任何一个匹配的大小都不超过其任何一个点覆盖的大小。完全二分图 \(K_{n, m}\) 的最大匹配和最小点覆盖大小都为 \(\min(n, m)\)。
边覆盖
对于图 \(G=(V, E)\),若 \(E'\subseteq E\) 且 \(\forall v\in V\) 满足 \(v\) 与 \(E'\) 中的至少一条边相邻,则称 \(E'\) 是图 \(G\) 的一个 边覆盖 (edge cover)。
最小边覆盖的大小记作 \(\rho(G)\),可以由最大匹配贪心扩展求得:对于所有非匹配点,将其一条邻边加入最大匹配中,即得到了一个最小边覆盖。
最大匹配也可以由最小边覆盖求得:对于最小边覆盖中每对有公共点的边删去其中一条。
一张图的最小边覆盖的大小加上最大匹配的大小等于图的点数,即 \(\rho(G)+\nu(G)=|V(G)|\)。
一张图的最大匹配的大小不超过最小边覆盖的大小,即 \(\nu(G)\le\rho(G)\)。特别地,完美匹配一定是一个最小边覆盖,这也是上式取到等号的唯一情况。
一张图的任何一个独立集的大小都不超过其任何一个边覆盖的大小。完全二分图 \(K_{n, m}\) 的最大独立集和最小边覆盖大小都为 \(\max(n, m)\)。
团
对于图 \(G=(V, E)\),若 \(V'\subseteq V\) 且 \(V'\) 中任意两个不同的顶点都相邻,则 \(V'\) 是图 \(G\) 的一个 团 (clique)。团的导出子图是完全图。
如果一个团在加入任何一个顶点后都不再是一个团,则这个团是一个 极大团 (maximal clique)。
一张图的最大团的大小记作 \(\omega(G)\),最大团的大小等于其补图最大独立集的大小,即 \(\omega(G)=\alpha(\bar{G})\)。求一张图的最大团是 NP 困难 的。
参考文献:
[1] https://oi-wiki.org/graph/concept/
[2] https://yhx-12243.github.io/OI-transit/memos/14.html
[3] https://blog.csdn.net/qq_42411214/article/details/111531904
[4] https://blog.csdn.net/qq_42270373/article/details/83758928