最后更新: 2025-01-22 10:12 查看: 67 次反馈能力测评会员8.2元/月赞助

二分图的匹配

我们将在本章节介绍无向图中特殊的关系—匹配，然后将匹配和二分图两者结合起
来，介绍二分图的最大匹配和最佳匹配的有效算法
匹配的基本概念
我们来看一个实例：飞行大队有若干个来自各国的飞行员，专门驾驶一种型号的飞机，这种飞机每架要有两个飞行员驾驶。由于种种原因，例如语言不通或训练上的问题，有些飞行员不能在同一架飞机上飞行，问如何搭配飞行员，才能使出航的飞机最多。为简单起见，假设有 10 个飞行员，图 11.4 中的 $v_1, v_2, \cdots, v_{10}$ 就代表这 10 个飞行员。

如果两个人可以同机飞行，就在代表他们两个之间连一条线；两个人不能同机飞行就不连。例如 $v_1$ 和 $v_2$ 可以同机飞行，而 $v_1$ 和 $v_3$ 就不行。画了这个图后，就可以研究搭配飞行员的问题了。上图中画的三条粗线 $\left(v_2, v_3\right), ~\left(v_5, v_7\right)$ 和 $\left(v_6, ~ v_{10}\right)$ 就代表了一种搭配方案。由于一个飞行员不能同时派往两架飞机，因此任何两条粗线不能有公共的端点，我们把一个图中没有公共端点的一组边叫做一个＂匹配＂。这样，上面问题就成为：如何找一个包含最多条粗线的匹配？这个问题叫做图的最大匹配问题。请大家试试看，能不能从上图中找出一个包含四条边的匹配，再试试能不能找到包含五条边的匹配。

定义 11.11 （匹配）设图 $G(V, E), M \subseteq E$ ，如果 $M$ 中的任意两条边都没有公共点，则称 $M$ 是 $G$ 的一个匹配。

例如图 11.5 （a）（b）中的粗线组成的边集合 $M_1$ 与 $M_2$ 分别是图 $G_1$ 与 $G_2$ 的匹配。
 ![图片](/uploads/2025-01/addba2.jpg)
 
 上述的飞行员匹配问题的数学模型是从给定的图 $G$ 的所有匹配中，找出包含边数最多的匹配。这种匹配即所谓的最大匹配问题。

根据图的类型不同，匹配问题可分为两种：任意图的最大匹配和二分图的最大匹配。
在上述的飞行员匹配问题中，如果把飞行员划分成两个部分：正驾驶员和副驾驶员。这样问题转换为如何搭配正副驾驶员才能使出航飞机最多的问题，这一问题也可以归结为一个二分图上的最大匹配问题。

判别二分图
二分图的邻接矩阵一般可以具有如下形式

$$
A={ }_Y^X\left(\begin{array}{c:c}
0 & A_{12} \\
\hdashline A_{21} & A_Y \\
X
\end{array}\right)
$$

对于较简单的图，可以直观地判断其是否为二分图。然而，对于一个较复杂的图来说，根据定义或用图示方法，相邻矩阵判定其是否为二分图，既不方便亦不可靠，因此有必要制定一个行之有效的判定规则。

定理11

免费注册看余下 70%

非VIP会员每天5篇文章，开通VIP 无限制查看

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

高等数学测评 函数与极限一元函数微分学一元函数积分学微分方程空间向量与代数多元微分学多元积分学无穷级数

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

线性代数测评 行列式矩阵向量空间

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

概率统计测评 事件与概率一维随机变量与事件多维随机变量与事件随机变量的数字特征大数定律与中心极限定理统计量与抽样分布参数估计假设检验

上一篇：最大流最小割定理

下一篇： Hall定理

本文对您是否有用？有用 (0) 无用 (0)