Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。”

@TOC

前言

Hello！小伙伴！
非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～
 
自我介绍 ଘ(੭ˊᵕˋ)੭
昵称：海轰
标签：程序猿｜C++选手｜学生
简介：因C语言结识编程，随后转入计算机专业，有幸拿过一些国奖、省奖…已保研。目前正在学习C++/Linux/Python
学习经验：扎实基础 + 多做笔记 + 多敲代码 + 多思考 + 学好英语！
 
机器学习小白阶段
文章仅作为自己的学习笔记 用于知识体系建立以及复习
知其然 知其所以然！

往期文章

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（1）：集合与映射

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（2）：线性空间定义及其性质

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（3）：线性空间的基与坐标

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（4）：基变换与坐标变换

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（5）：线性子空间

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（6）：子空间的交与和

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（7）：欧氏空间

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（8）：标准正交基与Gram-Schmidt过程

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（9）：正交补与投影定理

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（10）：线性变换定义

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（11）：线性变换的矩阵表示

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（12）：相似形理论

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（13）：Hamliton-Cayley定理、最小多项式

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（14）：向量范数及其性质

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（15）：矩阵的范数

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（16）：向量和矩阵的极限

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（17）：函数矩阵的微分和积分

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（18）：方阵的幂级数

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（19）：不定积分（补充知识）

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（20）：方阵函数

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（21）：常用方阵函数的一些性质

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（22）：方阵函数在微分方程组中的应用

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（23）：常数项级数的概念和性质（补充知识）

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（24）：常数项级数的审敛法（补充知识））

【机器学习｜数学基础】Mathematics for Machine Learning系列之矩阵理论（25）：幂级数（补充知识）

5.2 匹配基本定理

对称差

$A \Delta B = (A \cup B) – (A \cap B)$

记忆：先去掉$A、B$都有的元素，然后再合并$A、B$的其他元素

5.2.1 Berge定理

定理 5.1

$M$是$G$的最大匹配的充要条件是$G$不含$M$可增长路径

证明

证必要性：$M$是$G$的最大匹配 $\Rightarrow$ $G$不含$M$可增长路径

使用反证法

假设$G$中含有$M$可增长路径$P = v_0v_1v_2 … v_{2m+1}$

令 $M^{‘} = M \Delta E(P)$

显然$M^{‘}$是$G$的一个匹配，且

$|M|^{‘} = |M| + 1$

与$M$是最大匹配相矛盾 ，故假设不成立

说明$G$不含$M$可增长路径

证充分性：$G$不含$M$可增长路径 $\Rightarrow$ $M$是$G$的最大匹配

使用反证法

假设 $G$不含$M$可增长路径，但$M$不是最大匹配

设$M^{‘}$是$G$的一个最大匹配，则有$|M|^{‘} > |M|$

令$H = G[M \Delta M^{‘}]$

可以得到 $H$中每个顶点在$H$中的次数只能是$1或2$

---

为了理解上述：$H$中每个顶点在$H$中的次数只能是$1或2$

可以举一个例子帮助理解

定义一个最大匹配$M^{‘}$如下

再定义一个匹配$M$，其中满足$|M| < |M^{‘}|$

得到$M \Delta M^{‘}$为

$M\Delta M^{‘}$可以简单理解为：去掉两者重复的，保留两者没有重复的

再令$H = G[M \Delta M^{‘}]$

这里$H$是$G$的边子图（只要$G$含有$[M \Delta M^{‘}]$边的部分）
事先假设$G$中都存在这些边

可以发现$H$中每一个连通分支有两种可能

• 一条边在$M$和$M^{‘}$中交错的偶圈（上图左半部分）
• 一条边在$M$和$M^{‘}$中交错的路径（上图右半部分）

所有可以得到 $H$中每个顶点在$H$中的次数只能是$1或2$

---

因为$|M^{‘}| > |M|$

所以一定有一个连通片中含有一条路径$P$，始边和终边都属于$M^{‘}$

且$P$的两个端点是$M$非渗透点（上图右半部分含有这样的两个端点）

从而得出 $P$是$M$可增长路径

与假设$G$中无增长路径矛盾

故假设不成立，$M$是$G$的最大匹配

5.2.2 Hall定理

定义 5.4

设$S \subseteq V(G)$，$V(G)$中与$S$的顶点相邻的所有顶点构成之集合称为$S$的领域，记为$N_G(S)$

---

定理 5.2

设$G$是二部图，其划分为$(X,Y)$，则$G$有渗透$X$每个顶点的匹配的充要条件是：$\forall S \subseteq X$，恒有

$|N_G(S)| \geq |S|$

证明

证必要性：$G$有渗透$X$每个顶点的匹配 $\Rightarrow$ $\forall S \subseteq X$，恒有$|N_G(S)| \geq |S|$

因为$G$有渗透$X$每个顶点的匹配

所以对于$\forall S \subseteq X$，可以得到$S$中每一个顶点在$Y$中都可以找到对应的匹配点

故有

$|N_G(S)| \geq |S|$

证充分性：$\forall S \subseteq X$，恒有|N_G(S)| \geq |S|$$\Rightarrow $G$有渗透$X$每个顶点的匹配

假设$G$中没有渗透$X$每个顶点的匹配

令$M^{*}$为$G$的一个最大匹配，则$M^{*}$不能渗透$X$

取$X$中$M^{*}$非渗透点$u$

令$Z$是由$u$出发可由$M^{*}$交错路径到达的顶点集

因$M^{*}$是最大匹配，由$Berge$定理，得

$u$是$Z$中仅有的未被$M^{*}$配对的顶点

如果还存在$u$之外的一个顶点在$Z$中，那么就存在一条$M$交错路径的起点和终点都是非渗透点
则$M$为可增长路径
但由$Berge$定理知：最大匹配无可增长路径
故只能存在一个非渗透点，即$u$是$Z$中仅有的未被$M^{*}$配对的顶点

我们取

$S= Z \cap X, T = Z \cap Y$

显然，$S- \{u\}$中的顶点在$M^{*}$中与$T$中的顶点配对

除了$u$外，$S$与$T$中的顶点都存在匹配关系

有

$|T| = |S| – 1 ， N(S) = T$

得到

$|S| = |T| + 1 = |N(S)| + 1$

与$|N(S)| \geq |S|$相矛盾

故假设不成立

推论5.2.1

若$G$是$k-$正则二部图$(k > 0)$，则$G$有一个理想匹配

证明

设$G$的二部图划分为$(X, Y)$，则有

$k|X| = k|Y|$

从$X$引出的边的数量 等于 从$Y$引出的边的数量 （利用边的恒等性）

得到

$|X| = |Y|$

也就是$|X|$和$|Y|$中的顶点个数相同

令

• $S$是$X$中任意一个非空子集

• $E_1$是与$S$中顶点相关联的边集

• $E_2$是与$N(S)$中顶点相关联的边集

则有

$E_1 \subseteq E_2 \quad或 \quad|E_1| \leq |E_2|$

$E_1$是与$S$中顶点相关联的边集，且$E_1$两个端点中另一个端点一定是在$N(S)$中
所以$E_1$是$E_2$的一个子集

又因为