图论遗留问题，最短路，二分图

[[ slider_text ]]

[[ item.c ]]

图论遗留问题，最短路，二分图

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

二分图 最短路

## 最短路和最短路树
**[AtCoder Beginner Contest 252  E - Road Reduction](https://atcoder.jp/contests/abc252/tasks/abc252_e)**
**问题描述**
给定$$n$$个点$$m$$条边的无向图，点之间有距离，现在只需要$$n-1$$条道路，要使得人们从$$1$$这个起点出发
到所有的编号为$$[2\cdots n]$$的点，距离之和最小，即最小化$$d_2 + \cdots + d_n$$
问要保留哪些边？

**算法分析**
注意到$$n$$个点，$$n-1$$条边，也就是说，最终的形态一定是原图的一个生成树
同时又要求从起点出发，到各个点的路径最短，那么只需要求原图的**最短路径生成树**即可

> 编程技巧

1）在 dijkstra 的时候，可以不用`vis`数组判断点是否需要扩展，我们知道
当且仅当$$d(y) = d(x) + w$$的时候，$$(x \to y)$$是树边，在 dijkstra 进堆的时候也是如此
令`[expected, x] = heap.top()`，当且仅当`dis[x] == expected`的时候，`x`才是最短路径上的点
才需要继续扩展，进堆，否则`dis[x] != expected`，这个点不会在最短路径上，忽略它

这样，也可以避免出现环，为什么呢？因为假设$$(x_1 \to y), (x_2 \to y)$$，那么$$y$$先被`x1`更新
然后被`x2`更新，当且仅当$$x_2 \to y$$**更小**
这样我们可能会出现两种情况`(dist_old[y], y), (dist[y], y)`，可能都会被放入候选堆中
但我们只考虑`expected == dist[y]`的点，也就是说，只有`(dist[y], y)`会被满足
之前$$x_1$$处的`dist_old`值，会被忽略，这样一个点只有在满足$$d_y = d_x + w$$的时候
它才会考虑继续做 dijkstra，继续往下遍历，每个点只会被考虑一次，不会死循环

2）求最短路树，可以在都做完 dijkstra 的时候，遍历所有的边，只考虑`dist[from] + cap == dist[to]`的边
（当然，`dist[from] > dist[to] 的时候，swap(from, to)`）
用`has[to]`标记一下，这个点是否已经在`res`中了，**一个点只能考虑一次**（因为是树）
如果`has[to] == false`，那么`res.push_back(eid), has[to] = true`

### 算法实现
```bash
template <typename T>
class Graph {
public:
    struct _Edge {
        int from;
        int to;
        T cap;
    };
    int _n;
    vector<_Edge> e;
    vector<vector<int> > g;
    vector<T> dis;

Graph() {}
    Graph(int n) {
        init(n);
    }

void init(int n) {
        this->_n = n;
        e.clear();
        g.assign(n+5, {});
        dis.assign(n+5, inf<T>);
    }

int addEdge(int from, int to, T cap = 1) {
        int id = (int) e.size();
        g[from].push_back(id), g[to].push_back(id);
        e.push_back({from, to, cap});
        return id;
    }

void dijkstra(int s) {
        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>> > heap;
        dis[s] = 0;
        heap.push({dis[s], s});

while (heap.size()) {
            T expected = heap.top().first;
            int x = heap.top().second;
            heap.pop();
            // if and only if, when dis[x] == exactly shortest path!
            if (dis[x] != expected) continue;

for (auto id : g[x]) {
                auto [from, to, cap] = e[id];
                int y = x ^ from ^ to;
                if (dis[y] > dis[x] + cap) {
                    dis[y] = dis[x] + cap;
                    heap.push({dis[y], y});
                }
            }
        }
        return;
    }

vector<int> getEdge() {
        vector<int> has(_n, 0);
        vector<int> res;

for (int eid = 0; eid < (int) e.size(); eid++) {
            auto [from, to, cap] = e[eid];
            if (dis[from] > dis[to]) swap(from, to);

if (dis[from] + cap == dis[to]) {
                if (!has[to]) {
                    has[to] = 1, res.push_back(eid);
                }
            }
        }
        return res;
    }
};

void solve() {
    int n, m;
    cin >> n >> m;

Graph<i64> G(n+1);
    for (int i = 0; i < m; i++) {
        int x, y;
        i64 cap;
        cin >> x >> y >> cap;

G.addEdge(x, y, cap);
    }
    G.dijkstra(1);
    auto res = G.getEdge();

for (auto x : res) cout << x+1 << " ";
    cout << "\n";
}
```

## 匹配和因子
### 二分图的基本判定
**定理**
> 无向图是二分图，当且仅当图中不存在奇环

反证法，假设存在奇环，$$(V\_{2k-1}, V\_1)$$有边，那么有
```math
\begin{cases}
V_1 \in X, V_2 \in Y \\
V_3 \in X, V_4 \in Y \\
\vdots \\
V_{2k-1} \in X, V_{1} \in Y
\end{cases}
```
很显然，$$V_1 \in Y，V_1 \in X$$矛盾

### 完全二分图中的完美匹配
记$$K_n$$为$$n$$个点的完全二分图的匹配方案数，完美匹配定义为$$X\\{1,\cdots n\\}, Y\\{1\cdots n\\}$$的双射
依次为$$x_1 \cdots x_n$$，在$$Y$$中找配对顶点，有$$n!$$的方案

1）如果$$K\_{2n+1}$$是奇数阶，那么没有完美匹配
2）否则，$$K\_{2n}$$的完美匹配个数$$f\_n$$为，**将不同的$$2n$$个人匹配的方案数**
假设当前考虑随机的一个人，为他找匹配有$$\binom{2n-1}{1}$$种选择，接下来只需要考虑剩下的$$n-1$$对的方案
所以有$$f\_n = (2n-1) \cdot f\_{n - 1}$$

另外，$$(2n)$$个人的全排列，有$$(2n)!$$种，假设匹配方案有$$f_n$$种（不考虑顺序）
那么将这$$n$$种匹配（每一个匹配中的两个数捆绑在一起）全排列，有$$n!$$种
每个匹配内部$$2$$个数，$$2$$个数的全排列有$$2!$$种，恰好构成了$$(2n)!$$排列的所有情形

所以$$f_n \cdot (2!)^n \cdot n! = (2n)!$$，从而$$f_n = \dfrac{(2n)!}{2^n n!}$$

### 极大匹配和最大匹配
**极大匹配**
图$$G$$的极大匹配，是由一组没有公共端点的，不是环的边构成的集合
再添加匹配边就有公共端点了，或者成环了
与匹配相关联的边，我们称为**M-浸润**

**最大匹配**
最大匹配是图$$G$$的所有匹配中，边数达到最大值的匹配，每个最大匹配都是一个极大匹配，但反过来不一定成立

**交错路径和增广路径**
对于某个匹配$$M$$，一条路径上的边交错地，出现或者不出现在$$M$$中，构成 **M-交错路径**
两个端点均不被 **M-浸润**的 M-交错路径，是** M-增广路径**

> 观察，增广路径有奇数条边

注意到，M-增广路径，一般有奇数条边，因为要满足两个端点未浸润，并且边的浸润状态是交错的
以`(浸润，非浸润)`为一组，往右边恰好有$$2k$$组边，而最左边的端点还要有一个未浸润边，所以是$$2k+1$$条

**匹配的对称差**
对于一个匹配$$M$$，每个顶点，最多关联一条边
定义$$M\Delta M'$$，为顶点集$$V$$的一个图，边集仅由出现在$$M$$或是$$M'$$**其中一个**的边构成
形式化地，$$M \Delta M' = (M - M') \cup (M' - M)$$

> 如果$$F = M \Delta M'$$，那么$$F$$的顶点最多关联到两条边，$$\Delta(F) \leqslant 2$$

为什么呢？根据匹配的定义，匹配中的点最多关联一条边，这里给你 2 个匹配，最多只能关联 2 条边

> 在$$F = M \Delta M'$$中，任何分量或者是一条路径，或者是一个偶环

根据上面的证明，$$\Delta(F) \leqslant 2$$，所以要么是路径，要么是环，并且路径或者环的边
交替着出现$$M-M'$$和$$M'-M$$，即$$F$$中的边，**交替着**来自$$M$$和$$M^{\prime}$$
（不可能关联两条$$\in M$$的边，否则的话$$F$$中的该顶点，是公共端点，不符合匹配的定义）

> 图$$G$$的一个匹配$$M$$是最大匹配，当且仅当$$G$$中没有 M-增广路径

注意到$$F$$由偶环和路径构成，并且有相同数量的边来自$$|M|, |M'|$$，那么$$F$$必然有一个分量
使得$$|M'| > |M|$$，来自$$M'$$的边更多，$$|M'|$$是$$|M|$$的增广路径

## Hall 匹配条件
### 一些定义
**团**，图中两两互补相邻的顶点构成的集合
**独立集**，图中两两互补相邻的顶点组成的集合
**二部剖分**，图有两个互不相交的独立集，并且独立集的并是$$V(G)$$
![](/media/content_img/bigraph01.png)

> Hall 匹配条件，$$X-Y$$二分图中有一个浸润$$X$$的匹配，当且仅当$$\forall S \subseteq X$$，有$$|N(S)| \geqslant |S|$$

1）必要性，考虑和$$|S|$$相连的匹配边，根据独立集的定义，和$$|S|$$匹配的顶点，必然在$$|N(S)|$$中

2）充分性
尝试构造一个$$|S|$$，在$$|S|$$未被浸润的情况下，有$$|N(S)| < |S|$$
如图所示，定义**浸润边**和**普通边**，存在 M-增广路径，它的第一条边是普通边，最后一条边也是普通边

我们构造这样的两条路径，满足$$S, T$$均由交错路径得到，但是$$\exists u \in S$$，但是$$u$$未被浸润
而$$|T|$$中的任意点均被浸润
另外，因为是交错路，所以$$\\{S - u\\}$$中的每一个顶点，都可以从$$T$$的一个顶点，通过匹配$$M$$的一条边到达
并且$$M$$无增广路

对于$$S \subseteq X, N(S) \subseteq Y$$，$$u$$是未浸润的点，$$u$$出发沿交错路走，$$u \to \\{N(s) \text{ 中的点}\\}$$
我们不妨就假设$$X$$中的顶点构成$$S$$，$$Y$$中的顶点构成$$T$$

> 进一步观察

1.我们至少有$$T \in N(S)$$，另一方面，由于$$M$$没有增广路径，所以$$\\{S - u\\} \to \\{T\\}$$交错路中
首尾都是**浸润边**，而$$u$$为未浸润点，假设$$u \to T$$连边，连向$$T$$中的某个点$$u_t$$，那么$$(u, u_t)$$是普通边

2.下面我们证明$$|T| = |N(S)|$$，可以用反证法，若$$\exists y \in \\{Y - T\\}$$
对于$$y$$来说，要么它连向某个点$$v \in S, v \neq u$$，要么它连向$$u$$
而连向$$u$$是不可能的，因为是交错路，$$u$$走向的点一定在$$T$$中，$$y$$又不在$$T$$中，所以$$y$$不可能连$$u$$
（画图看看，不难发现，如果$$(y, u)$$有边，会出现增广路）

3.形式化地说，$$v$$这个点是通过**M-交错路**和$$T$$匹配的，$$y$$又不在$$T$$中，所以$$(y, v)$$是普通边，非浸润边
普通边加入到$$M$$中，会形成增广路，与假设矛盾，所以$$|N(S)| = |T|$$

综上所述，$$|N(S)| = |T| = |S| - 1 < |S|$$

> 形象理解 Hall 判定条件
![](/media/content_img/bigraph02.png)

## 几个特殊图
**k-正则的图**
记图$$G$$中的点的度数为$$d_v$$（如果是环，$$n \to 1$$和$$1 \to 2$$算 2 次）
最大的顶点度数为$$\Delta(G)$$，最小为$$\delta(G)$$，正则的图，那么有$$\delta(G) = \Delta(G)$$
所有的顶点度数都是$$K$$，那么$$G$$是 K-正则的

> 每个顶点出发，都有$$k$$条边

> k-正则的二分图，有一个完美匹配，并且匹配划分的两部分，顶点数相同

证明很简单，单独看$$X, Y$$两部分，并进行边计数，我们有$$e(G) = k|X|, e(G) = k|Y|$$
从而$$|X|= |Y|$$

**星形图**
有的地方称为菊花图，最多一个点$$\text{deg} \geqslant 2$$，其他点均是叶子，$$\text{deg} = 1$$

## 最小-最大定理（Konig）
考虑图$$G$$的一个顶点覆盖，选一些顶点$$Q\subseteq V(G)$$，$$Q$$包含原图每一条边上至少一个端点
并且$$Q$$的所有顶点能覆盖边集$$E(G)$$，$$Q$$称为图$$G$$的一个**顶点覆盖**

> 图中任意一个顶点，不可能覆盖匹配$$M$$中的两条边（因为匹配交错路），$$|\text{点覆盖}| \geqslant |\text{匹配}|$$

**Konig 定理**
最大匹配 = 最小点覆盖

证明，根据上面的分析，只需要证明等号总是可以取到的，于是转为下面的问题
给定一个$$G$$的最小点覆盖，构造一个大小为$$|Q|$$的匹配

对任意$$X-Y$$匹配，构造$$R = Q \cap X, T = Q \cap Y$$，看之前的图，不难发现，图$$G$$被切割成两部分
其中$$H = R \cup (Y-T), \quad H^{\prime} = T \cup (X-R)$$，其中$$H$$和$$H^{\prime}$$不相交
那么$$H$$和$$H^{\prime}$$构成的匹配，可以作为$$|Q|$$的匹配

下面只需要证明满足 Hall 条件即可
因为$$R \cup T$$是**顶点覆盖**，所以不存在$$(Y-T) \leftrightarrow (X-R)$$的边
先看$$H$$，对于$$S \subseteq R$$，有$$N_H(S) \subseteq (Y-T)$$

若$$|N_H(S)| < |S|$$，那么用$$N_H(S)$$替换$$S$$可以有一个更小的点覆盖，与$$Q$$是最小点覆盖矛盾
所以有$$|N_H(S)| \geqslant |S|$$，满足 Hall 条件
对$$H^{\prime}$$同理

## 独立集和覆盖，对偶问题
没有一个点能覆盖匹配中的两条边，对应的
没有一条边能覆盖（连接）独立集中的两个顶点

那么我们可以考虑**边覆盖**，若干条边构成的集合$$L$$，使得$$G$$中，每一个顶点$$\forall v \in G$$，$$v$$与$$L$$中的一条边相关联

有以下一些问题

**独立集大小的最大值**，$$\alpha(G)$$
**匹配大小的最大值**，$$\alpha'(G)$$
**顶点覆盖大小的最小值**，$$\beta(G)$$
**边覆盖大小的最小值**，$$\beta'(G)$$

这是一系列对偶问题，记匹配为$$\alpha$$，覆盖为$$\beta$$，一般地，最大匹配 = 最小覆盖
1.匹配记为$$\alpha$$，点匹配记为独立集$$\alpha(G)$$（因为相邻点，用一个点即可代表）
同样，边匹配就是我们通常说的匹配，交错地浸润和不浸润，相邻两条边，选一条浸润即可代表一对
记为$$\alpha'(G)$$

2.覆盖记为$$\beta$$，点覆盖记为$$\beta(G)$$，选一些点来覆盖边，与匹配相关
同理，边覆盖记为$$\beta'(G)$$

### Konig 定理
对于二分图$$G$$，有$$\alpha^{\prime}(G) = \beta(G)$$
对于没有孤立顶点的二分图，有$$\alpha(G) = \beta^{\prime}(G)$$

证明，没有一条边能覆盖独立集中的所有点，所以$$\beta^{\prime}(G) \geqslant \alpha(G)$$

> 记$$S \subseteq V(G)$$是一个独立集，当且仅当$$\bar{S}$$是一个顶点覆盖，$$\alpha(G) + \beta(G) = n(G)$$
其中，$$\bar{S} = V(G) - S$$

证明
必要性，如果$$S$$是独立集，那么从$$S$$出发的边，一定连到$$\bar{S}$$中的点
充分性，如果$$\bar{S}$$是一个顶点覆盖，也就是它覆盖了所有的边，这些边就不再需要$$S$$中的点了
那么不存在连接$$S$$中两个顶点的边

### Gallai 定理
若$$G$$是一个没有孤立顶点的图，$$\alpha^{\prime}(G) + \beta^{\prime}(G) = n(G)$$

> 证明思路，还是构造

由一个最大匹配$$M$$，构造一个大小是$$n(G) - |M|$$的边覆盖，$$|\text{最小边覆盖}| \leqslant |\text{构造的边覆盖}|$$
也就是说，$$\beta^{\prime}(G) \leqslant n(G) - \alpha^{\prime}(G)$$

由一个最小边覆盖$$L$$，构造一个$$n(G)-|L|$$的匹配，最大匹配$$\alpha^{\prime})(G) \geqslant n(G) - |L|$$
从而$$\alpha^{\prime}(G) \geqslant n(G)-\beta^{\prime}(G)$$

> 证明如下

1.设$$M$$是一个最大匹配，将未浸润点加入$$M$$中，每一个未浸润点对应一条普通边
不妨把这样的点集（未浸润的），记为$$|X|$$，而每个$$|M|$$连接$$2$$个匹配点
所以有$$1|X|+2|M| = n(G)$$
那么边覆盖 = $$|X|+|M| = n(G) - |M|$$

2.设$$L$$为最小边覆盖，**从 deg 角度来考虑**
如果有一条边，两个端点都关联到$$L$$中的边，那么$$e \notin L$$，因为删掉$$e$$，仍然构成一个覆盖

对于$$L$$中的每一个连通分量，构造一个**星形图**，只有一个点$$deg \geqslant 2$$，其余点$$deg = 1$$
对于每个星形图而言，不算中心点，$$|L|$$条边对应$$|L|$$个叶子
再加上有$$k$$个分量，每个分量一个中心点，$$|L| + k = n(G)$$

**每一个星形连通分量，选择中心点往外的一条边，就构成一个匹配**
一个连通分量对应一条匹配边，共有$$k = n(G) - |L|$$个匹配

**推论**
如果$$G$$是一个没有孤立顶点的二分图，那么$$\alpha(G) = \beta^{\prime}(G)$$

证明就很简单了，因为$$\alpha(G) + \beta(G) = \alpha^{\prime}(G) + \beta^{\prime}(G)$$
已知$$\alpha^{\prime}(G) = \beta(G)$$，自然有$$\alpha(G) = \beta^{\prime}(G)$$

## 支配集
在**顶点覆盖**问题中，考虑用较少的**星形**来覆盖边集，用最少的星形来覆盖点集
![](/media/content_img/bigraph03.png)

支配集，简单一点说，就是每一个不在$$S$$中的点，都与$$S$$相邻
形式化的定义如下，在图$$G$$中，每一个不在集合$$S \subseteq V(G)$$中的顶点
都有一个位于$$S$$中的相邻顶点，那么$$S \subseteq V(G)$$是一个支配集
支配数$$\gamma(G)$$是$$G$$中支配集大小的**最小值**

**补充定义**
图的阶$$|G|$$，记为$$n(G)$$，为$$G$$中的顶点数
最小顶点的度数，记为$$\delta(G)$$

完全图，任意两个顶点都是邻接的，记为$$K\_n$$
二部图，两个顶点是邻接的，当且仅当它们在不同的部集中，记为$$K\_{r, s}$$
星形图是一个简单的二部图，可以记为$$K\_{1, n-1}$$

**重要的几点**
> 覆盖顶点集所需要的星形个数，可以少于覆盖边集所需要的星形个数

比如以完全图为例，$$K_n = \\{v_1, v_2, \cdots, v_n\\}$$，只需要在顶点$$1$$处放一个星形
就可以覆盖到$$(v_1\cdots v_n)$$所有顶点

而对于边呢？在$$v_1$$放一个星形，只能关联到$$(v_1, v_2), (v_1, v_3), \cdots, (v_1, v_n)$$这些边
对于$$(v_2, v_3)\cdots$$这些边是关联不到的

对于$$K_n$$，存在边集覆盖如下
```math
\begin{cases}
v_1 : (v_1, v_2), &(v_1, v_3), \cdots &(v_1, v_n) \\
v_2 : &(v_2, v_3), \cdots &(v_2, v_n) \\
\vdots \\

v_{n-1}: & &(v_{n-1}, v_n)
\end{cases}
```
覆盖边集所需的星形数，$$n-1$$

> 图$$G$$没有孤立顶点，每个顶点覆盖就是一个支配集，$$\gamma(G) < \beta(G)$$
($$\beta(G)$$是顶点覆盖，找一些点来覆盖掉边，要多少个点？)
但注意，二者的差可能很大

比如上面的例子，$$\gamma(K_n) = 1, \beta(K_n) = n-1$$

### 特殊图的支配集
> 对于 K-正则图来说，一个度数为$$K$$的点，支配它本身和与它相邻的$$K$$个点
那么支配集的大小，我们有$$\gamma(G) \cdot (K+1) \geqslant n(G)$$
从而$$\gamma(G) \geqslant \dfrac{n(G)}{K+1}$$

### 支配集的一些推论
**定义**
定义$$v$$的闭邻域为$$N[v] = N(v) \cup \\{v\\}$$
一般地，$$N(v)$$表示和$$v$$相邻的顶点构成的集合，$$N[v]$$表示由$$v$$支配的顶点构成的集合

**定理**
最小度为$$k$$的$$n-$$顶点的图，有一个大小$$\leqslant n \dfrac{1 + \ln(k+1)}{k+1}$$的支配集

> 先证明一个断言，若$$S \subseteq V(G)$$，定义$$U$$是未被$$S$$中的顶点支配的点集
对于$$S$$之外的某个点$$y$$，它至少支配$$U$$中$$\geqslant |U|\dfrac{k+1}{n}$$个顶点

证明，`for U 中的每一个顶点`，它都有$$\geqslant k$$个相邻的顶点，并且它们位于$$S$$中
```math
\displaystyle
\sum_{v \in U}|N[v]| \geqslant |U|(k+1)
```
等式右边很好理解，每一个点都至少有$$k$$个相邻顶点，一个团的顶点数至少为$$k+1$$，
那么$$|U|$$个团，顶点数至少是$$|U|(k+1)$$

考虑等式左边，$$\sum|N[v]|$$的计数，被重复算了几次？

注意到$$G$$中的每个顶点，最多有$$n$$个邻居，那么对于$$U$$中的某个点$$y$$（如图所示）
我们计算它的$$n$$个邻居的时候，$$y$$都会被统计了一次，有几个这样的$$y$$呢？记为$$|y|$$
```math
\displaystyle
|y|\cdot n \geqslant \sum_{v \in U} |N[v]| \geqslant |U|(k+1)
```
从而$$|y| \geqslant \dfrac{|U|(k+1)}{n}$$，必然有一个点，会支配$$\geqslant \dfrac{|U|(k+1)}{n}$$个$$U$$中的点

> 接着尝试证明结论

在未支配集$$U$$中考虑
如果未支配的点有$$r$$个，那么再选一个支配点后，还有$$r - r\cdot \dfrac{k+1}{n}$$个未支配点
未支配集变化，$$r \to r\left(1 - \dfrac{k+1}{n} \right)$$

考虑$$1-x < e^{-x}$$，取$$n \dfrac{\ln(k+1)}{k+1}$$步
```math
n\left(1-\dfrac{k+1}{n}\right)^{\dfrac{n\ln(k+1)}{k+1}} < ne^{-\ln(k+1)} = \dfrac{n}{k+1}
```

未支配点的个数$$\leqslant \dfrac{n}{k+1}$$，另外上面的步骤，我们还选了$$n \dfrac{\ln(k+1)}{k+1}$$个点
支配集$$\leqslant n\left(\dfrac{1}{k+1} + \dfrac{\ln(k+1)}{k+1} \right) = n\dfrac{1+\ln(k+1)}{k+1}$$

> 每一个无爪形的图，有一个大小为$$\gamma(G)$$的独立支配集
其中，$$\gamma(G)$$是支配集大小的**最小值**

1.令$$S$$是$$G$$的一个最小支配集，$$S^{\prime}$$是$$S$$的一个极大独立子集
记$$R$$表示$$S^{\prime}$$支配的顶点集合，记为$$N[S^{\prime}] \cup S^{\prime}$$
记$$T = V(G) - R$$，即不归$$S^{\prime}$$管的顶点，再记$$T^{\prime}$$是$$T$$的**极大独立子集**

2.因为$$T^{\prime}$$不包含$$S^{\prime}$$中的点，所以$$S^{\prime} \cup T^{\prime}$$可以单独考虑
注意到$$S'$$是$$S$$的极大独立集，说明$$S$$中的每个顶点，邻居都在$$S'$$中
我们说$$S'$$控制$$S$$，记为$$S' \hookrightarrow S$$，同理$$T' \hookrightarrow T$$
从而$$S' \cup T'$$是支配集

3.下面证明$$|S' \cup T'| \leqslant \gamma(G)$$
注意到$$x \in (S - S')$$中的每个顶点，因为$$S$$是一个支配集，所以这样的$$x$$在$$S$$中存在邻居
但是在$$T^{\prime}$$中，最多也只能有一个相邻顶点（因为是无爪形图）
另外，$$T'$$中的每个点，在$$S - S'$$中，可以有多个邻居

所以我们有$$|T^{\prime}| \leqslant |S - S^{\prime}|$$
```math
|S' \cup T'| \leqslant |S| + |S - S'| = |S| = \gamma(G)
```

## 一些问题
### 第一部分
> 对于环$$C_n$$，极大匹配边数的最小值

先考虑$$n = 3, n = 4$$的简单情况，不难发现答案是$$\lceil \dfrac{n}{3} \rceil$$
然后直观来看，`(浸润-未浸润)`邻接边包含 3 个顶点，每一组 3 个顶点，这样分组之后，好像答案确实是$$\lceil n/3 \rceil$$

下面证明，假设有$$k$$条浸润边，对应$$2k$$个匹配点，那么剩余$$n - 2k$$个未匹配的点，需要额外的浸润边$$n - 2k$$个
1.如果$$n - 2k \geqslant k + 1$$，那么$$k \leqslant \lfloor\dfrac{n-1}{3} \rfloor = \lceil \dfrac{n+1}{3} \rceil$$

2.如果$$0 \leqslant n - 2k \leqslant k$$，那么要满足$$k \leqslant \lfloor \dfrac{n}{2} \rfloor$$，同时$$k \geqslant \lceil\dfrac{n}{3} \rceil$$

> 对参数$$\alpha, \alpha', \beta, \beta'$$，考虑各参数为$$1$$的简单图的特征

1.如果最大独立集大小$$\alpha = 1$$，说明整个图只需要`1`个点来代表，这个图是完全图
2.如果最大匹配大小$$\alpha^{\prime} = 1$$，说明一条边就可以代表这个图了，其他边都和这个边邻接
或者图是孤立点 + 三角形，或者图是星形图
3.顶点覆盖的最小值$$\beta = 1$$，我们知道$$\alpha + \beta = n$$，或者$$\beta$$的对偶问题是$$\alpha^{\prime}$$
那么这个图是星形图，可能还有一些孤立点
4.边覆盖的最小值$$\beta^{\prime} = 1$$，一条边就可以覆盖所有点了，那么这个图是$$K_2$$
即大小为$$2$$的完全图

> 证明$$\displaystyle \alpha(G) \geqslant \dfrac{n(G)}{\Delta(G) + 1}$$，其中$$\Delta(G)$$是图度数最大值

考虑到独立集中的每个点，可以代表所有它的邻居，那么独立集中的每个点，代表的点最多是$$(\Delta(G) + 1)$$
独立集的大小是$$\alpha(G)$$，从而有$$\alpha(G) \cdot (\Delta(G) + 1) \geqslant n(G)$$

> 证明，图$$G$$是二部图，当且仅当对$$G$$的任意的，不含孤立顶点的子图$$H$$，有$$\alpha(H) = \beta^{\prime}(H)$$

反证法，如果$$G$$并不是二部图，那么它存在**奇环**
不妨设最大独立集大小是$$\alpha = k$$，那么$$n = 2k + 1$$，这种情况下，会存在一条边未浸润
并且其两个端点都**未匹配**

那么你要想把这两个端点都覆盖掉，至少要添加一条边
所以$$\beta^{\prime} = \alpha + 1$$，每个独立集为端点，引一条边，再额外添加一条边

### 第二部分
> 证明或否定，每棵树最多有一个完美匹配

考虑特殊化，如果这棵树是一条链，那么要想有完美匹配，必须有$$2k$$个顶点
并且完美匹配是唯一的，$$1, n$$首尾两个点都要覆盖到

如果只有叶子结点呢？实际上，`deg(u) <= 2`的情况，都可以看成一条链，完美匹配是唯一的
对于$$deg_u > 2$$的情况，考虑如果$$u$$的子树$$\forall v$$如果都是**一条长链**，什么时候有完美匹配呢？
观察可以发现，链长为偶数的分支，首尾都浸润，此时$$(u, v)$$不需要浸润
而链长为奇数的分支，$$v$$没有被浸润，那么$$(u, v)$$为浸润边，恰好能浸润到$$u$$
链长为奇数的分支有且仅有一个，剩下的分支链长必须为偶数，此时才有完美匹配
否则的话就没有完美匹配

> 证明，图$$G$$的每个极大匹配，至少有$$\alpha^{\prime}(G) / 2$$条边

假设极大匹配是$$|M|$$，那么意味着有$$|M|$$条浸润边，最坏情况下，每条浸润边的邻边，一定是普通边
也就是说，极大匹配同时还贡献了$$|M|$$条普通边，那么$$|2M|$$可以涵盖图中，**和最大匹配相关**的所有边集了
也就是说$$2|M| \geqslant \alpha^{\prime}(G)$$，从而$$|M| \geqslant \alpha^{\prime}(G) / 2$$

> 设$$M, N$$是图$$G$$的两个匹配，$$|M| > |N|$$，证明，存在匹配$$M', N'$$，使得$$|M'| = |M|-1$$，$$|N'| = |N|+1$$
并且$$M'$$和$$N'$$的并集和交集（作为边集），等于$$M$$和$$N$$的并集和交集

图论的证明，很重要的思想**对称差**，取对称差后，往往可以从一个点的度数$$deg \leqslant 2$$来入手
把问题简化成环或者是链

考虑对称差$$M \Delta N$$，与$$u$$相连的边，要么来自$$M$$，要么来自$$N$$，这样一个点的$$deg \leqslant 2$$
这样的话，这个**对称差导出的子图**，就是有**奇数条边的路径**
因为$$|M| > |N|$$，所以路径的首尾两条边$$\in M$$，剩下的边$$\in N$$，并且$$|M|-|N| = 1$$
交换$$M, N$$，就得到了匹配$$|M'|, |N'|$$满足题意

> 令$$C$$和$$C'$$是图中的两个环，证明$$C \Delta C'$$可以分解成若干环

首先，**任意偶图均可以分解成若干个环**
很容易证明，每一个偶图均有环（这里不考虑只有一个孤立点的图），并且删除一个环之后，仍然是一个偶图
对边数归纳，命题成立

那么考虑$$C, C'$$构成的连通块，也一定是环，$$C \Delta C'$$也是一个偶图
实际上，$$|C\Delta C'| = |C| + |C'| - 2|C\cup C'|$$，不影响每个顶点`deg`的奇偶性

> 令$$G$$是围长为$$k$$的图（围长，最小环的长度），$$C$$和$$C'$$是长度为$$k$$的两个环
证明，$$C \Delta C'$$是一个环当且仅当$$C \cap C'$$是一条非平凡路径

证明
必要性很好证，$$C \cap C'$$是一条路径，相当于$$C$$和$$C'$$共用一条**公共边**
那么$$C \Delta C'$$相当于抹掉这条公共边，剩下部分保留，仍然是一个环

充分性，考虑$$C \cap C' = \empty$$，那么$$C \Delta C'$$是两个相离的环，不符合题意
![](/media/content_img/bigraph04.png)
如果有多于一条边，那么会产生更小的环，矛盾

> 设$$M, M'$$是 X-Y-二分图中的两个匹配，假设$$M$$浸润$$S \subseteq X$$，$$M'$$浸润$$T \subseteq Y$$
证明，$$G$$中有一个匹配浸润$$S \cup T$$

问题描述如上所示
不难发现，对于$$M \Delta M'$$，$$\forall u$$的点满足$$deg_u \leqslant 2$$
并且对于$$deg = 2$$的点，一定是一条边来自$$M$$，另一条边来自$$M'$$

我们可以如下构造满足条件的匹配
对于$$deg = 1$$的点，即路径的首尾，根据这个点关联$$M$$还是$$M'$$中的边，来确定选哪种边
而关于$$deg = 2$$的点，根据**交错路径的限制**（即不能有来自同一匹配的边，关联同一个顶点）
来选择取$$M$$中的边，还是$$M'$$中的边，维护交错路径即可

具体如图所示

上一篇：2024年12月一些算法比赛（二）下一篇：二分图，匹配和因子

看完文章有啥想法