二分图，匹配和因子

[[ slider_text ]]

[[ item.c ]]

二分图，匹配和因子

发布时间 2024-12-31 作者：zhangminchen 来源：算法小站

流和匹配 图论

## 图论中一些基本概念
> 图$$G$$中，顶点的平均度为$$\dfrac{2e(G)}{n(G)}$$，从而$$\delta(G) \leqslant \dfrac{2e(G)}{n(G)} \leqslant \Delta(G)$$

> 任意的图，含有偶数个 deg 为奇数的点（至少一个 in，一个 out），阶为奇数的图，不会以奇数度称为正则图

> 含有$$n$$个顶点的$$k-$$正则图有$$nk / 2$$条边

### k 维超立方体的定义
记$$Q_k$$是一个简单图，其顶点是分量取自$$\\{0, 1\\}$$的所有$$k$$元组，边连接的两个顶点
**恰好在一个位置**取不同值，剩下位置的值是相同的

> 对于$$Q_k$$，顶点的奇偶性，由顶点表示的元组**包含 1 的个数的奇偶性**决定
另外，$$Q_k$$连接的每一条边，会有一个位标不同，一端是`0`，另一端是`1`，从而每条边有一个偶端点和奇端点
偶顶点构成一个独立集，奇顶点构成一个独立集，$$Q_k$$是二分图

> k-元组的每个分量，可以取$$\\{0, 1\\}$$两个值，顶点数$$n(Q_k) = 2^k$$，选一个位置改成不同的值，其他位置不变
就得到了它的相邻顶点，$$Q_k$$是$$k$$正则的，$$e(Q_k) = k2^{k} / 2 = k2^{k-1}$$

### k 维超立方体的同构
对于一个$$k$$维超立方体，想得到一个$$j$$维的子立方体，可以考虑固定$$k-j$$个位置值不变
剩余的位置取$$2^j$$个$$j$$元组，有$$\displaystyle\binom{k}{j}$$种方法确定$$j$$个位置，同时$$k-j$$个位置可以任意取$$\\{0, 1\\}$$
一共可以有$$\displaystyle \binom{k}{j}\cdot 2^{k-j}$$个子立方体

## 匹配和覆盖中一些问题
### k 维超立方体
记$$Q_k$$是$$k$$维度超立方体
> 对$$Q_k$$的任意完美匹配$$M$$和任意位标$$i \in [k]$$，$$M$$有偶数条边的端点，在第$$i$$个位标是不同的

图有完美匹配，那么它有**偶数个顶点**，具体来说，下图矩阵，在 X 位标处值**相同**，? 位标处值**不同**
注意到，$$Q_k$$顶点储存位标信息，每个顶点值为$$\\{0, 1\\}$$
```math
\begin{pmatrix}
x \ x \ x \ ? \\
x \ x \ x \ ?
\end{pmatrix}
```
具有这样特点的顶点，两两连边，因为$$x$$处，可以填$$\\{0, 1\\}$$两种取值，$$\binom{2}{1}$$种
一共可以构造出$$\binom{2}{1}\cdot k$$种满足条件的组，其中$$k$$表示矩阵中$$x$$的列数
这些$$\binom{2}{1} k$$条边，在第$$i$$个位标是不同的，其他位标处都相同

> 对于$$k \geqslant 2$$，证明$$Q_k$$至少有$$2^{2^{k-2}}$$个完美匹配，可以先考虑$$Q_3$$有$$9$$个完美匹配

对于$$Q_3$$，不难发现
![](/media/content_img/matches01.png)
方案数是$$\displaystyle \binom{3}{1} \cdot \binom{3}{1} = 9$$种完美匹配

那么对于$$Q_k$$的情况，能不能划分成若干个$$Q_2$$
只考虑$$Q_2$$的匹配边，下面用$$?$$表示位标的值不同，$$? = \\{0 \textbf{ or } 1\\}$$
```math
\begin{pmatrix}
? \ 1 \\
? \ 1
\end{pmatrix}
\begin{pmatrix}
? \ 0 \\
? \ 0
\end{pmatrix}
```
可知$$Q_2$$的匹配边有$$2$$种选择，那么原问题就很容易计算了
先考虑$$k$$维超立方体能拆分成几个$$Q_2$$，不难发现，$$k-2$$个位标**必须相同**，同时可以取$$\\{0, 1\\}$$两种选择
所以能够有$$2^{k-2}$$种$$Q_2$$，那么每一种$$Q_2$$有$$2$$种构造，所以答案是$$2^{2^{k-2}}$$种不同的匹配

接下来用**数学归纳法**来验证
用$$m_k$$表示$$Q_k$$完美匹配数量，根据上面计算$$Q_3$$的算法，想想看$$Q_3$$是怎么算的？
先考虑$$Q_2$$，在$$Q_2(?, ?)$$，第一维先选出一条浸润边，构成$$(x, ?)$$，然后第二维再选一条浸润边，构成$$(x, x)$$

那么同样的方法，可以考虑从$$Q\_{k-1}$$构造$$Q\_k$$，$$Q\_{k-1}$$有$$m\_{k-1}$$种完美匹配
对于$$Q\_{k}$$，可以看作两个$$Q\_{k-1}$$组合而成，第二个$$Q\_{k-1}$$也有$$m\_{k-1}$$种完美匹配
这两者是**独立的**
（直观理解，可以看作两个$$k-1$$维的立方体，**在对岸隔着相望**）
（并且它们$$k-1$$维的位标都相同，但是组成$$k$$维超立方体的时候，第$$k$$维的位标是不同的）
当两边的$$k-1$$维匹配边确定下来的时候，剩下的**连接桥梁边**，该选哪条作为浸润边，这也就唯一确定了

所以有$$m\_k = m\_{k-1}^2$$，归纳法即可证明

> 在$$Q_k$$中，每个顶点给一个权值，是标签中`1`的个数，证明，在$$Q_k$$的每个**完美匹配**中
当$$0 \leqslant i \leqslant k-1$$时，从权值是$$i$$的顶点，到权值$$i+1$$顶点，匹配边共有$$\displaystyle \binom{k-1}{i}$$条

方法一，根据之前的讨论，$$Q\_k$$的情况，考虑两个$$Q\_{k-1}$$**隔着相望**
只需要在$$Q\_{k-1}$$中，选出$$i$$个**值为 1 的二进制位**，令它们成为浸润边即可
因为浸润边，它们的权值仅相差`1`，并且确定了$$Q\_{k-1}$$之后，剩下的**桥梁浸润边**是唯一确定的
所以答案是$$\displaystyle \binom{k-1}{i}$$

方法二，一共有$$\displaystyle \binom{k}{i}$$个顶点，其权值恰好是$$i$$，这些顶点中，要么$$i-1 \to i$$，要么$$i \to i+1$$
对$$i$$归纳，发现$$\displaystyle \binom{k}{i} - \binom{k-1}{i-1} = \binom{k-1}{i}$$，归纳成立

### 能转化成匹配模型的问题
> 两个人轮流游戏，选择不同的顶点，Alice 先手，可以选择任意一个顶点，后续 Bob / Alice 轮流
但是每次选择的点必须和上一次选择的邻接，选最后一个顶点的人获胜
证明，如果图$$G$$有完美匹配，那么第二个人有必胜策略，否则第一个人有必胜策略

证明如下
1.如果图有完美匹配的话，后手选的那个人，总可以沿着匹配边选，当选到第$$n = 2k$$个顶点的时候
必然所有的顶点都被选完了（因为是完美匹配，剩下的非匹配边是不允许选进来的）
2.考虑第一个人，选某个最大匹配**未浸润的点**，此时的点数为奇数，当 Alice 选走最大匹配未浸润的点时
剩下的就是**完美匹配**，并且转化为 Bob 先手，Alice 后手，根据第一部分的结论，此时后手 Alice 必胜

> 令$$A = \\{A_1, A_2\cdots, A_m\\}$$是集合$$Y$$的子集族，$$A$$的**相异代表系**（SDR）是$$Y$$中
满足$$a_i \in A_i$$的不同元素$$a_1, a_2, \cdots, a_m$$构成的集合

> 证明，$$A$$有一个 SDR 当且仅当$$|\bigcup\_{i \in S} A_i| \geqslant |S|$$对任意$$S \subseteq \\{1, 2, \cdots, m\\}$$成立

转化成二分图，记$$X = \\{1, 2, \cdots, m\\}$$，$$Y = \\{y_1, y_2, \cdots, y_n\\}$$
连边$$(i, y_i)$$当且仅当$$y_i \in A_i$$，这样记$$i \in |S|$$, $$|A_i| \in |N_G(S)|$$
根据 Hall 匹配条件，$$|N(S)| \geqslant |S|$$

> Hall 定理的归纳法证明，考虑 X-Y-二分图$$G$$，假设它对任意$$S \subseteq X$$有$$|N(S)| \geqslant |S|$$
对$$|X|$$用归纳法证明，$$G$$有一个浸润$$X$$的匹配

首先，考虑$$S \subset X$$，找到任意一个$$x \in X$$，以及它的邻居$$y \in Y$$，那么很显然$$y \in N(S)$$
将$$x, y$$剔除，那么$$|S|, |N(S)|$$最多减少`1`，同时$$S' = X-\\{x\\} \subset X$$仍然满足
归纳假设，我们有$$|N(S) - \\{y\\}| > |S - \\{x\\}|$$成立，可以推出$$|N(S)| > |S|$$

如果归纳假设$$|N(S)| > |S|$$不满足怎么办？
考虑满足$$S \subset X, |N(S)|=|S|$$的情况
我们已知，对于整个图$$G$$来说，有$$|N(S)| \geqslant |S|$$，那么我们构造$$G_1 = |S \cup N(S)|$$
令$$G_2 = G - G_1$$，那么对于$$G_1$$来说，很显然有$$|N(S)| \geqslant |S|$$
对于$$G_2$$呢，我们扣除了$$|N(S)| = |S|$$的情况，剩下$$|N(S)| > |S|$$的情况了
取$$T \subset X - S$$，那么$$|N_G(T \cup S)| \geqslant |T \cup S|$$，我们有
```math
N_{G_2}(T) = N_G(T \cup S) - N_G(S) \geqslant |T \cup S| - |S| = |T|
```
仍然是满足的
![](/media/content_img/matches02.png)

> 令$$G$$是一个X-Y二部图，其中只要$$\empty \neq S \subset X$$，就有$$|N(S)| > |S|$$，证明，$$G$$的每条边均属于某个浸润$$X$$的匹配

考虑$$x \in X, y \in Y$$，并且$$y$$是$$x$$的邻居，令$$G' = G - x - y$$，不难发现
```math
\displaystyle
|N_{G'}(S)| \geqslant |N_G(S)| - 1 > |S| - 1 \geqslant |S|
```
可以发现$$G'$$满足 hall 条件，所以$$X - \\{x\\}$$是浸润的，然后再并上$$(x, y)$$，从而$$X$$也是浸润的

> 二分图$$G$$有一个完美匹配，当且仅当$$|N(S)| \geqslant |S|$$对任意$$S \subseteq V(G)$$成立
还需要给出一族无穷的反例，证明这一结论并不是对所有图都成立

必要性，如果对任意$$S \subseteq V(G)$$，都有$$|N(S)| \geqslant |S|$$成立，根据 Hall 条件
任意$$S$$都是浸润的，所以是完全匹配

充分性，根据 Hall 条件，$$G$$中有一个匹配浸润$$X$$，如果未浸润所有顶点，不妨设$$|Y| \geqslant |X|$$
然而，根据 Hall 条件，$$|N(Y)| \geqslant |Y|$$，$$|N(Y)|$$即$$|X|$$，从而$$|X| \geqslant |Y|$$
综上所述，$$|X| = |Y|$$，所以是完全浸润，完美匹配

## 匹配的一些应用
> 置换矩阵$$P$$定义为$$0, 1$$矩阵，并且每行，每列仅有`1`个`1`
证明，具有非负整数的方阵，可以表示成$$k$$个置换矩阵的和，当且仅当各行元素之和，各列元素之和均为$$k$$

考虑转换成匹配问题
对于矩阵$$A$$，考虑$$(i, j)$$连一条权值为$$a\_{i, j}$$的边，考虑为每一个$$i \in I$$，找一个$$j \in J$$的匹配
注意到问题给定$$A$$是一个方阵，所以构成二分图
那么我们找到它的最大匹配，如果$$(i, j)$$是浸润边，我们令$$b\_{i, j} = 1$$，否则$$b\_{i, j} = 0$$
这样构造了矩阵$$B$$，满足$$B$$的**每一行，每一列仅有一个`1`**，然后递归地，对剩下$$k-1$$维子矩阵归纳
问题即可证明

> 双重随机矩阵$$Q$$是一个非负实数矩阵，其中每行每列的元素之和都是$$1$$，证明，$$Q$$能表示成$$Q = c_1P_1 + \cdots + c_mP_m$$

观察，因为$$Q$$每行，每列的元素之和都是`1`，就意味着，如果$$Q$$恰好有$$n$$个非`0`元素的话
它一定是置换矩阵的`c`倍，形如
```math
\begin{pmatrix}
c \ 0 \ 0 \\
0 \ 0 \ c \\
0 \ c \ 0
\end{pmatrix}
```
而注意到，随机矩阵每一行，每一列的元素和都是`1`，可以对非`0`元素归纳，一次拆出一个非`0`元素
写成一个分量$$\epsilon_i P_i$$，最后考虑$$\sum_i \epsilon_i P_i$$
![](/media/content_img/matches03.png)

如上图所示，这样的构造是可行的，对$$n$$归纳，子问题$$n \times n \to (n-1) \times (n-1)$$

> 考虑$$m\times n$$的牌，有$$n$$种花色，每种花色有$$m$$张不同面值的牌，这些牌构成一个$$n \times m$$的矩阵
a）证明，有$$m$$张面值不同的牌分别位于矩阵的每一列中
b）利用前面结论，证明通过若干次操作，每次操作将面值相同的牌互换位置，最终可以使得这些牌每一列均由$$n$$张不同花色牌构成

考虑每种面值出现了几次（被用了几次），用匹配来解决
a）考虑面值集合$$i \in \\{1, 2, \cdots, m\\}$$，如果面值$$i$$在花色$$j$$中出现，就考虑连边$$(i, j)$$
最终可能同一种面值，有多种花色$$(i, j_1), (i, j_2), \cdots, (i, j_n)$$
另一方面，矩阵的行数为$$n$$，这恰好构成了$$deg = n$$的 n-正则图，根据 Hall 条件，它有完美匹配

b）考虑面值相同的牌交换位置，不难发现，最后会有$$\lfloor \dfrac{m}{n} \rfloor$$种，面值不同，但是花色相同的牌
这些牌如果位于同一列，需要被换掉

仅仅考虑需要换掉的行$$i$$
对于面值为$$x$$的牌，从$$1 \sim n-1$$行去找到同样面值为$$x$$的牌，交换即可（必然存在不同花色的），代价是$$n-1$$
接着对于行$$i+1$$，只需要从$$1 \sim n-2$$中去找，代价是$$n-2$$，以此类推
最坏代价是$$\displaystyle \lfloor \dfrac{m}{n} \rfloor n(n-1) / 2$$

> 推广的井字棋， 一个占位对策游戏由位置集合$$X = \\{x_1, x_2, \cdots, x_n\\}$$和一族胜利位置$$W_1, \cdots, W_m$$组成
每个胜利位置集$$W_i$$是一个由一些位置构成的集合，两者轮流选位置，先选取一个胜利位置集的人获胜
假定每个胜利位置集至少有$$a$$个位置，每个位置最多出现在$$b$$个胜利位置集中
证明，$$a \geqslant 2b$$，后手总存在一个平局策略

考虑匹配模型，对于所有位置 X，考虑$$s$$向$$x_i$$连一条流量上限是$$b$$的边
然后每个胜利位置集合向汇点连一条流量上限是$$a$$的边，如果位置$$i$$出现在胜利位置集$$W_j$$中
那么$$(i, j)$$连一条流量上限是`1`的边

这样的图构成了`X-Y`二分图
![](/media/content_img/matches04.png)
由图可见，$$|N(W)| \geqslant |W|$$，可以发现 Hall 条件满足，存在浸润$$W$$的匹配
考虑怎么后手策略

比如先手取了$$W_j$$中的某一个位置$$x(k_1)$$，那么后手只需要在$$W_j$$集合中，取另一个位置$$x(k_2)$$即可
这样只要先手在$$W_j$$中取，他就不可能完整地取完一整个集合

## König-Egerváry定理应用
**注意**，König-Egerváry 的对偶，仅仅在**二分图**成立，即$$\alpha(G) = \beta^{\prime}(G)$$

> 证明任意二分图有一个大小至少为$$e(G) / \Delta(G)$$的匹配

考虑**中心点**出发，最多可能有$$\Delta(G)$$条边，考虑将这样的星形图分为一组，一共有$$e(G)/\Delta(G)$$组
注意到这样的组，把中心点选进来，就可以代表这一组所有点，所以最小点覆盖$$\geqslant e(G) / \Delta(G)$$
最小点覆盖等于最大匹配，所以$$\alpha^{\prime}(G) = e(G) / \Delta(G)$$

> 确定简单二分图的最大边数，使得它既没有$$k$$条边的匹配，也没有具有$$l$$条边的星形

根据上面的结论，立马得到$$e \leqslant (k-1) \cdot (l-1)$$

> 用 König-Egerváry 定理证明 Hall 定理

充分性，记$$Q$$是一个点覆盖，取$$R = Q\cap X, T = Q \cap Y$$，这样$$X-R, Y-T$$之间一定没有边相连
另外，我们有$$N(X-R) \subseteq T$$，我们有$$|N(X-R)| \leqslant |T|$$
注意到$$|R|, |T|$$构成点覆盖部分，从而$$|R| + |T| \leqslant |Q|$$，综上所述
```math
|N(X-R)| \leqslant |T| \leqslant |Q|-|R| < |X| - |R|
```
因为$$(X-R)$$没有匹配边，所以应该要满足 Hall 条件，而上述子图与 Hall 条件矛盾
所以 Hall 条件是充分的

必要性，反证法，如果$$|N(S)| < |S|$$，意味着什么呢？取大小为$$N(S)$$的点覆盖
它是无法浸润$$S$$中的所有点的，必要性成立

> 在 X-Y-二分图中，集合$$S$$的缺失，定义为$$def(S) = |S| - |N(S)|$$，特别地，$$def(\empty) = 0$$

> 证明，$$\alpha^{\prime}(G) = |X| - maxdef\_{S \subseteq X} (S)$$，其中$$\alpha^{\prime}$$指最大匹配

首先，至少有$$def(S)$$个点是未浸润的，所以$$\alpha'(G) \leqslant |X| - def(S)$$
记$$d = \max(|S| - |N(S)|)$$，考虑将$$d$$加入到$$Y$$中，构造出的新图$$G^{\prime}$$满足 Hall 条件
它有一个浸润$$X$$的匹配，将$$d$$从$$G^{\prime}$$中删去，最多损失$$d$$条**浸润边**
所以还剩下的**浸润边数量**是$$\geqslant |X| - d$$，从而$$\alpha^{\prime}(G) = |X| - d$$

> 根据以上，证明 König-Egerváry 定理

可以得到一个最大匹配，令$$d = |S| - |N(S)|$$，那么$$|X| - d = |X| - |S| + N(S)$$，符合 Hall 条件，可以全部浸润
根据这个匹配，构造一个顶点覆盖$$Q = (X-S) \cup N(S)$$，那么还剩下的补集$$R = S \cup (Y - N(S))$$
根据$$S, N(S)$$的定义，补集中没有边，所以$$Q$$就构成一个最小顶点覆盖

> 设$$G$$是一个没有孤立顶点的 X-Y-二分图，如上定义缺失，证明，Hall 条件在浸润$$X$$的一个匹配上得以满足
当且仅当$$Y$$的任意子集$$S$$，缺失至多为$$|Y|-|X|$$

换句话说，证明 Hall 条件浸润$$X$$，当且仅当对任意$$S \subseteq X$$，有$$|N(S)| \geqslant |S|$$
并且$$|T| - |N(T)| \leqslant |Y| - |X|$$对任意$$T \subseteq Y$$

同样考虑补集，分别是$$X-N(T), Y-T$$，那么$$|Y|-|T| - (|X|-|N(T)|) \geqslant 0$$，从而对于任意补集都符合 Hall 条件

> 设$$G$$是一个 X-Y-二分图，它有一个浸润$$X$$的匹配，令$$m = |X|$$，证明，$$G$$最多有$$\binom{m}{2}$$条边
不属于任何大小为$$m$$的匹配，这个上界对于任意的$$m$$最优

浸润$$X$$，但是却有不属于大小为$$m$$的匹配，说明存在**增广路径**
增广路径，最多在首和尾有非浸润边，那么重排$$m$$个顶点之后
选择两个点分别作为$$1$$和$$n$$，这样的方案数恰是$$\displaystyle \binom{m}{2}$$

> 设$$G$$是一个 X-Y-二分图，有一个浸润$$X$$的匹配
a) 令$$S$$和$$T$$是$$X$$的子集，并且有$$|N(S)| = |S|, |N(T)| = |T|$$，证明，$$|N(S \cap T)| = |S \cap T|$$
b) 证明，$$X$$中有某个顶点$$x$$，使得任意关联到$$x$$的边，均属于某个最大匹配
（考虑满足$$|N(S)| = |S|$$的极小非空子集$$S \subseteq X$$）

先考虑a），我们有$$|S \cap T| + |S \cup T| = |S| + |T|$$
又因为$$X$$是浸润的，所以$$|S \cap T| \leqslant |N(S \cap T)|$$
由此$$|S \cap T| + |S \cup T| \leqslant |N(S \cap T)| + |N(S \cup T)| \leqslant |N(S) \cap N(T)| + |N(S) \cup N(T)| = |N(S)| + |N(T)| = |S| + |T|$$
等号是恒成立的，所以$$|N(S \cap T)| = |S \cap T|$$

b) 尝试证明无增广路，也就是说$$(S, N(S))$$首尾都没有浸润边
考虑$$|S| = |N(S)|$$的极小非空子集$$S \subseteq X$$，考虑其补集$$R$$，由$$(X-S, N(X) - N(S))$$构成
因为匹配浸润$$X$$，所以$$|N(X)| \geqslant |X|$$，从而$$R$$也满足 Hall 条件
考虑$$R \cup S$$，因为$$|S| = |N(S)|$$，所以$$|S|$$无增广路径，并且**首尾都是浸润边**
同时$$X-S$$也是被浸润的，$$R \cup S$$最多只有一条位于$$R$$尾部的**非浸润边**
所以$$R \cup S$$无增广路径，所以存在关联到$$x$$的边，都属于最大匹配

> 面积为$$n$$的小岛，有$$n$$对已婚的猎人/农民夫妇。狩猎管理局把小岛分成$$n$$个大小相等的狩猎区域
农业管理局把小岛分成$$n$$个大小相等的农业区域，婚姻管理局要求每对夫妇接受两块有重叠的区域，这总是可以实现的
证明，如果$$n$$是奇数，则适当安排可以保证每对夫妇的两块区域的重叠部分面积至少是$$\dfrac{4}{(n+1)^2}$$

> 如果$$n$$是偶数，则重叠面积至少为$$\dfrac{4}{[n(n+2)]}$$
另外，不论怎么安排，更大的公共区域无法对每对夫妇保证

类似之前**双重随机矩阵**$$Q$$的分析方法，考虑匹配
令$$X$$作为 Hunter 集合，列$$N(X)$$作为 Farmer 集合，尝试找出浸润$$X$$的匹配
每对夫妇接受两块有重叠的区域，就意味着$$2 \cdot |X| = n$$，那么$$|X| = \lceil \dfrac{n}{2} \rceil$$
![](/media/content_img/matches05.png)
对$$n$$分奇偶讨论，可以求出$$\epsilon$$的值

> 令$$G$$是一个二分图，$$\alpha(G) = n(G) / 2$$当且仅当$$G$$有一个完美匹配

根据 König-Egerváry 定理，不难发现$$\alpha(G) + \beta(G) = n(G)$$，从而$$\beta(G) = n(G) / 2$$
说明有$$n(G) / 2$$个点覆盖，用$$n(G) / 2$$个点恰好覆盖所有的边，所以$$|X|$$浸润，$$|N(x)|$$也浸润
图$$G$$有一个完美匹配

> 一个$$n$$个点的连通图恰有一个环，当且仅当它恰好有$$n$$条边，令$$G$$是一个恰好有一个环$$C$$的非二分图
证明，$$\alpha(G) \geqslant \lfloor (n(G) - 1) / 2 \rfloor$$，等号成立当且仅当$$G-V(C)$$有一个完美匹配

**第一个结论**很显然，$$n$$个点$$n-1$$条边的连通图是树
这可以用归纳法，对$$n$$归纳，由$$n$$个顶点的树$$G$$，删除一片叶子$$v$$之后，可以得到$$n-1$$个顶点的树$$G^{\prime}$$
由于仅一条边关联到$$v$$，那么$$e(G^{\prime}) = n - 2$$，且$$n(G^{\prime}) = n - 1$$，归纳成立
在树上任意连接一条边，有且仅有一个简单环

**第二个结论**，因为**树一定是二分图**（二分图的充要条件是没有奇环），可以将环和树分开来考虑
先考虑环$$C$$，因为是**奇环**，所以环的独立集大小$$\alpha(C) = \lfloor \dfrac{n(C)}{2} \rfloor = \dfrac{n(C) - 1}{2}$$

然后考虑$$G' = G-C$$，我们要求$$\alpha(G')$$，因为树一定是二分图，根据对偶$$\alpha(G') = \beta'(G')$$
可以考虑先求$$\beta'(G') = n(G') - \alpha'(G')$$，$$\alpha^{\prime}(G')$$即表示$$G'$$的**最大匹配**

对于一棵树，怎么样能让**最大匹配尽可能大呢**？观察发现，**一条链**的时候，此时最大匹配取最大值
否则的话，可能某个节点有多个子树，需要将**浸润边合并**，匹配数只会更小，不可能变大

那么对于长度为$$n(G')$$的链，$$\alpha'(G') \leqslant \lfloor \dfrac{n(G')}{2} \rfloor$$

从而$$\alpha(G') \geqslant n(G') - \lfloor \dfrac{n(G')}{2} \rfloor \geqslant \lfloor \dfrac{n(G')}{2} \rfloor$$

接下来合并独立集$$\\{C \cup G'\\}$$，$$\alpha(G) \geqslant \lfloor \dfrac{n(G')}{2} \rfloor + \dfrac{n(C) - 1}{2}$$

即满足$$\alpha(G) \geqslant \lfloor (n(G) - 1) / 2 \rfloor$$

**第三个结论**，即等号成立的充要条件
非二分图，说明$$C$$是一个**奇环**
先证必要性，当$$G - V(C)$$有一个完美匹配时，会不会存在$$\alpha(G) \geqslant \lfloor (n(G) - 1) / 2 \rfloor$$
有完美匹配，说明$$n(G - V(C))$$为偶数，同时$$C$$是一个奇环，从而$$n(G)$$为奇数

我们有$$\alpha(G-V(C)) = \dfrac{n(G-V(C))}{2}$$，同时，$$\alpha(V(C)) \geqslant \lfloor \dfrac{n(V(C) - 1)}{2} \rfloor$$

考虑合并$$\\{G-V(C)\\} \cup \\{V(C)\\}$$，从而$$\alpha(G) \geqslant \lfloor \dfrac{n(G) - 1}{2} \rfloor$$

充分性，考虑$$\alpha(G) \geqslant \lfloor (n(G)-1)/2 \rfloor$$，$$G-V(C)$$是否有完美匹配呢？
反证法，假设$$G' = G-V(C)$$没有完美匹配，$$G'$$中的点的个数是$$r$$，它满足什么特点呢？

它的匹配边数量$$\alpha'(G-V(C)) \leqslant \dfrac{r}{2} - 1$$，同时有$$\beta(G') \leqslant \dfrac{r}{2} - 1$$

那么根据$$\alpha + \beta = n$$，可以推出$$\alpha(G') \geqslant r - \dfrac{r}{2} + 1 = \dfrac{r}{2} + 1$$

也就是说，$$G'$$的独立集大小$$\geqslant \dfrac{r}{2} + 1$$，同时$$G'$$是一棵树或者是森林

下面考虑环，因为是一个奇环，所以环上独立集的大小是$$\lfloor \dfrac{V(C)}{2} \rfloor$$
最后将$$\\{C \cup G'\\} = G$$，合并起来，不难发现独立集的大小是**树独立集大小 + 环独立集大小**

从而$$\alpha(G) \geqslant \dfrac{V(C) - 1}{2} + \dfrac{r}{2} + 1= \dfrac{n(G) - 1}{2} + 1$$

这样我们就证明了等号成立的条件，当且仅当$$G - V(C)$$有一个完美匹配

**上述命题证毕**

> 考虑贪心算法，得到较大的独立集$$S$$，每次迭代从剩下的图中，选择度数较小的那个顶点，加到$$S$$中，并且把相邻的顶点删除
证明，在简单图中，算法产生的独立集大小至少是$$\sum\_{v \in V(G)}\dfrac{1}{d\_{G}(v) + 1}$$

要想选择尽可能大的独立集，选出来的点**关联的边**应该尽可能少，也就是贪心选`deg`较小的点
接下来考虑每一次的选择，假设当前选进来度数是$$deg$$的点，看作中心点，中心点和它关联的点组成一个团
这个团有$$deg + 1$$个点，而整个图可以分成若干个这样的团，有几个这样的团呢？$$\dfrac{n}{deg\_{G}(v) + 1}$$

每一个团的最小贡献是$$\dfrac{1}{deg\_{G}(v) + 1}$$，所以独立集大小$$\displaystyle \geqslant \sum\_{v \in V(G)}\dfrac{1}{deg\_{G}(v) + 1}$$

> 在一个没有孤立顶点的图中，设$$M$$是一个极大匹配，而$$L$$是一个极小边覆盖，证明以下结论
a) $$M$$是一个最大匹配，当且仅当$$M$$含于某个最小边覆盖中
b) $$L$$是一个最小边覆盖，当且仅当$$L$$包含一个最大匹配

分析，从定义和 König-Egerváry 来考虑
对于a），因为$$|M|$$是一个最大匹配，那么至少有$$2|M|$$个点是被浸润的，这些点不需要重复被覆盖
剩下$$(n - 2|M|)$$个点是需要另外加边覆盖的，所以$$|L| = |M| + (n - 2|M|) = n - |M|$$
从而有$$|L| + |M| = n$$，$$|M|$$是一个最大匹配，当且仅当$$|L|$$是一个最小边覆盖

对于b），直接用$$\alpha^{\prime} + \beta^{\prime} = n$$即可，最大匹配$$|M| = n - |L|$$
因为$$2|L| \geqslant n$$，从而$$|L| - |M| \geqslant 0$$，证明完毕

> 设$$G$$是一个简单图，其中任意$$k$$个顶点的度之和小于$$n - k$$，证明，图$$G$$的任意极大独立集的顶点数$$> k$$

考虑选择中心点$$u$$，因为$$deg < n - k$$，所以只需要$$< n - k$$个点就可以覆盖所有的边了
（最坏情况是星形图），由此$$\beta(G') < n(G') - k$$
那么$$\beta + \alpha = n(G')$$，从而$$\alpha(G') > k$$，证毕

> 图$$G$$的一条边$$e$$是$$\alpha-$$**临界的**，如果$$\alpha(G-e) > \alpha(G)$$，设$$xy$$和$$xz$$是$$G$$的两条$$\alpha-$$临界边
证明，$$G$$有一个诱导子图是包括$$xy, xz$$的一个奇环

证明思路，可以从**对称差**考虑
令$$Y, Z$$分别是$$G - xy$$和$$G-xz$$的最大独立集，令$$H = [Y \Delta Z]$$，只需要证明$$H$$的每个分支
都有相同数目的点分别来自$$Y, Z$$，这样$$(y, z, x)$$就构成了奇环

考虑**最大独立集**，端点是否浸润
![](/media/content_img/matches06.png)
![](/media/content_img/matches07.png)

证明如上图所示
如果存在两条临界边，可以在`LCA`处考虑，断开临界边，会产生`2`个端点，从**非浸润点变成浸润点**
这样，形成两个连通块$$Y, Z$$，考虑把$$Y, Z$$接回原图，那么**浸润端点又会变回非浸润的**
同时`LCA`变成浸润的，换句话说，$$Y, Z$$的浸润状态**转移到`LCA`处了**

这样，$$\alpha(G) = (\alpha(Y) - 1) + (\alpha(Z) - 1) + \alpha(\\{x\\}) + \alpha\left( \text{剩下的点} \right) = \alpha(G) - 1$$，矛盾

所以，同时断开$$(x, y), (x, z)$$两条临界边，$$\alpha(Y), \alpha(Z)$$**只能有一个连通分量的$$\alpha$$增加`1`**
要么是$$Y + 1$$，要么是$$Z + 1$$，也就是说存在$$(x, y, z)$$的简单环

上一篇：图论遗留问题，最短路，二分图下一篇：支配集，支配集常见的结论

看完文章有啥想法