2026-08-01-Note

Latex 入门类

Ref: Latex.pdf

没啥好听的，我全都会，放一个前几天写的格式库。Raisetsu41/Latex-Notes-Template: Latex-Notes-Template。

Mathlab 基础

Ref: Matlab.pdf

我记得我是 numpy & pandas 用户来着

图论

Ref: 只发了后半部分讲义。

第一次听数学系的讲图论。我第一次听图论课应该是 2020-07-08，「Note」图论学习笔记1 | Raisetsu41’s Blog（Too young too simple, sometimes naive）。

图

图 (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\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$ 中既有 有向边，又有 无向边．

若 $G$ 的每条边 $e_k=(u_k,v_k)$ 都被赋予一个数作为该边的 权，则称 $G$ 为 赋权图．如果这些权都是正实数，就称 $G$ 为 正权图．

图 $G$ 的点数 $\left|V(G)\right|$ 也被称作图 $G$ 的 阶 (order)．

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

相邻

在无向图 $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)$$

简单图

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

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

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

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

度数

与一个顶点 $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 是 可简单图化 的．

路径

途径 (walk)：途径是连接一连串顶点的边的序列，可以为有限或无限长度．形式化地说，一条有限途径 $w$ 是一个边的序列 $e_1,e_2,\dots ,e_k$，使得存在一个顶点序列 $v_0,v_1,\dots ,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,\dots ,e_k$ 两两互不相同，则称 $w$ 是一条迹．

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

回路 (circuit)：对于一条迹 $w$，若 $v_0=v_k$，则称 $w$ 是一条回路．

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

子图

对一张图 $G=(V,E)$，若存在另一张图 $H=(V^{\prime },E^{\prime })$ 满足 $V^{\prime }\subseteq V$ 且 $E^{\prime }\subseteq E$，则称 $H$ 是 $G$ 的 子图 (subgraph)，记作 $H\subseteq G$．

若对 $H\subseteq G$，满足 $\forall u,v\in V^{\prime }$，只要 $(u,v)\in E$，均有 $(u,v)\in E^{\prime }$，则称 $H$ 是 $G$ 的 导出子图/诱导子图 (induced subgraph)．

容易发现，一个图的导出子图仅由子图的点集决定，因此点集为 $V^{\prime }$($V^{\prime }\subseteq V$) 的导出子图称为 $V^{\prime }$ 导出的子图，记作 $G\left[V^{\prime }\right]$．

若 $H\subseteq G$ 满足 $V^{\prime }=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)$，对于 $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⊊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^{\prime }\subseteq V$ 且 $G\left[V\setminus V^{\prime }\right]$（即从 $G$ 中删去 $V^{\prime }$ 中的点）不是连通图，则 $V^{\prime }$ 是图 $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^{\prime }\subseteq V$，$u,v\notin V^{\prime }$，且在 $G\left[V\setminus V^{\prime }\right]$ 中 $u$ 和 $v$ 不连通，则 $V^{\prime }$ 被称作 $u$ 到 $v$ 的点割集．$u$ 到 $v$ 的最小点割集的大小被称作 $u$ 到 $v$ 的 局部点连通度 (local connectivity)，记作 $\kappa (u,v)$．

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

对于连通图 $G=(V,E)$，若 $E^{\prime }\subseteq E$ 且 $G^{\prime }=(V,E\setminus E^{\prime })$（即从 $G$ 中删去 $E^{\prime }$ 中的边）不是连通图，则 $E^{\prime }$ 是图 $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^{\prime }\subseteq E$，且在 $G^{\prime }=(V,E\setminus E^{\prime })$ 中 $u$ 和 $v$ 不连通，则 $E^{\prime }$ 被称作 $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)．

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

补图

对于无向简单图 $G=(V,E)$，它的 补图 (complement graph) 指的是这样的一张图：记作 $\bar{G}$，满足 $V\left(\bar{G}\right)=V\left(G\right)$，且对任意节点对 $(u,v)$，$(u,v)\in E\left(\bar{G}\right)$ 当且仅当 $(u,v)\notin E\left(G\right)$．

反图

对于有向图 $G=(V,E)$，它的 反图 (transpose graph) 指的是点集不变，每条边反向得到的图，即：若 $G$ 的反图为 $G^{\prime }=(V,E^{\prime })$，则 $E^{\prime }=\{(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$ 互为补图．

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

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

若无向简单图 $G=\left(V,E\right)$ 满足，存在一个点 $v$ 为支配点，其余点之间没有边相连，则称 $G$ 为 星图/菊花图 (star graph)，$n+1$($n\ge 1$) 阶星图记作 $S_n$．

若无向简单图 $G=\left(V,E\right)$ 满足，存在一个点 $v$ 为支配点，其它点之间构成一个圈，则称 $G$ 为 轮图 (wheel graph)，$n+1$($n\ge 3$) 阶轮图记作 $W_n$．

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

如果一张无向连通图不含环，则称它是一棵 树 (tree)． 多棵树可以组成一个 森林 (forest)。

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

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

如果一张图可以画在一个平面上，且没有两条边在非端点处相交，那么这张图是一张 平面图 (planar graph)．对于简单连通平面图 $G=(V,E)$ 且 $V\ge 3$，$|E|\le 3|V|-6$．
Kuratowski 定理：一张图是平面图当且仅当其不存在与 $K_5$ 或 $K_{3,3}$ 同胚 (homeomorphism) 的子图．其中图 $G$ 和图 $G^{\prime }$ 同胚指的是两图均可通过在边上新增若干度为 $2$ 的顶点[

同构

两个图 $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^{\prime }\cong H$ 使得 $V\left(H^{\prime }\right)\cap V_1=\varnothing$($H^{\prime }$ 可以等于 $H$)．此时与 $G\cup H^{\prime }$ 同构的任何图称为 $G$ 和 $H$ 的和/直和/不交并，记作 $G+H$ 或 $G\oplus H$．

若 $G$ 与 $H$ 的点集本身不相交，则 $G\cup H=G+H$．

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

特殊的点集/边集

支配集

对于无向图 $G=(V,E)$，若 $V^{\prime }\subseteq V$ 且 $\forall v\in (V\setminus V^{\prime })$ 存在边 $(u,v)\in E$ 满足 $u\in V^{\prime }$，则 $V^{\prime }$ 是图 $G$ 的一个 支配集 (dominating set)．

无向图 $G$ 最小的支配集的大小记作 $\gamma (G)$．求一张图的最小支配集是NP 困难

对于有向图 $G=(V,E)$，若 $V^{\prime }\subseteq V$ 且 $\forall v\in (V\setminus V^{\prime })$ 存在边 $(u,v)\in E$ 满足 $u\in V^{\prime }$，则 $V^{\prime }$ 是图 $G$ 的一个 出 - 支配集 (out-dominating set)．类似地，可以定义有向图的 入 - 支配集 (in-dominating set)．

有向图 $G$ 最小的出 - 支配集大小记作 ${\gamma }^{+}(G)$，最小的入 - 支配集大小记作 ${\gamma }^{-}(G)$．

边支配集

对于图 $G=(V,E)$，若 $E^{\prime }\subseteq E$ 且 $\forall e\in (E\setminus E^{\prime })$ 存在 $E^{\prime }$ 中的边与其有公共点，则称 $E^{\prime }$ 是图 $G$ 的一个 边支配集 (edge dominating set)．

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

独立集

对于图 $G=(V,E)$，若 $V^{\prime }\subseteq V$ 且 $V^{\prime }$ 中任意两点都不相邻，则 $V^{\prime }$ 是图 $G$ 的一个 独立集 (independent set)．

图 $G$ 最大的独立集的大小记作 $\alpha (G)$．求一张图的最大独立集是 NP 困难 的．

匹配

对于图 $G=(V,E)$，若 $E^{\prime }\subseteq E$ 且 $E^{\prime }$ 中任意两条不同的边都没有公共的端点，且 $E^{\prime }$ 中任意一条边都不是自环，则 $E^{\prime }$ 是图 $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)．

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

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

托特定理：$n$ 阶无向图 $G$ 有完美匹配当且仅当对于任意的 $V^{\prime }\subset V(G)$，$p_{\text{odd}}(G-V^{\prime })\le |V^{\prime }|$，其中 $p_{\text{odd}}$ 表示奇数阶连通分支数．

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

点覆盖

对于图 $G=(V,E)$，若 $V^{\prime }\subseteq V$ 且 $\forall e\in E$ 满足 $e$ 的至少一个端点在 $V^{\prime }$ 中，则称 $V^{\prime }$ 是图 $G$ 的一个 点覆盖 (vertex cover)．

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

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

一张图的任何一个匹配的大小都不超过其任何一个点覆盖的大小．完全二分图 $K_{n,m}$ 的最大匹配和最小点覆盖大小都为 $\min (n,m)$．

边覆盖

对于图 $G=(V,E)$，若 $E^{\prime }\subseteq E$ 且 $\forall v\in V$ 满足 $v$ 与 $E^{\prime }$ 中的至少一条边相邻，则称 $E^{\prime }$ 是图 $G$ 的一个 边覆盖 (edge cover)．

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

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

一张图的最小边覆盖的大小加上最大匹配的大小等于图的点数，即 $\rho (G)+\nu (G)=|V(G)|$．

一张图的最大匹配的大小不超过最小边覆盖的大小，即 $\nu (G)\le \rho (G)$．特别地，完美匹配一定是一个最小边覆盖，这也是上式取到等号的唯一情况．

一张图的任何一个独立集的大小都不超过其任何一个边覆盖的大小．完全二分图 $K_{n,m}$ 的最大独立集和最小边覆盖大小都为 $\max (n,m)$．