图的分数匹配 在匹配问题中，我们通常要求每条边要么完全被选入匹配，要么完全不选（即每条边的权重为0或1）。分数匹配是匹配问题的一种推广，它允许每条边被“部分”选择，即每条边可以被赋予一个介于0和1之间的权重。 1. 分数匹配的定义 给定一个图 \( G = (V, E) \)，一个分数匹配是一个函数 \( f: E \to [ 0, 1 ] \)，使得对于每个顶点 \( v \in V \)，所有与 \( v \) 关联的边的权重之和不超过1。即： \[ \sum_ {e \in E: v \in e} f(e) \leq 1 \quad \text{对所有 } v \in V \] 分数匹配的大小定义为所有边权重的总和： \[ |f| = \sum_ {e \in E} f(e) \] 2. 分数匹配与整数匹配的关系 整数匹配是分数匹配的特例，其中每条边的权重只能取0或1。 分数匹配的大小总是至少等于最大整数匹配的大小，因为任何整数匹配都可以视为一个分数匹配。 在某些图中，分数匹配可以严格大于最大整数匹配。例如，在奇圈（如三角形）中，最大整数匹配的大小为1，但分数匹配的大小可以达到1.5（通过给每条边分配0.5的权重）。 3. 分数匹配的线性规划表示 分数匹配问题可以表示为一个线性规划： 变量：对每条边 \( e \in E \)，引入变量 \( x_ e \in [ 0, 1 ] \)。 目标：最大化 \( \sum_ {e \in E} x_ e \)。 约束：对每个顶点 \( v \in V \)，有 \( \sum_ {e \in E: v \in e} x_ e \leq 1 \)。 这个线性规划的对偶问题是最小顶点覆盖问题，其中每个顶点被赋予一个权重，使得每条边至少有一个端点被覆盖。 4. 分数匹配的算法 分数匹配可以通过线性规划算法（如单纯形法或内点法）求解。但在二分图中，分数匹配有更简单的性质： 在二分图中，分数匹配的最大大小等于整数匹配的最大大小（由Birkhoff-von Neumann定理推广）。 因此，在二分图中，可以使用整数匹配算法（如匈牙利算法）来找到最大分数匹配。 5. 分数匹配的应用 调度问题：在任务分配中，分数匹配允许任务被部分分配给多个资源。 经济模型：在拍卖和市场中，分数匹配可以表示商品的部分分配。 网络流：分数匹配是网络流问题的特例，可以通过最大流算法求解。 分数匹配通过放宽整数约束，提供了比整数匹配更灵活的解，并在理论和应用中具有重要价值。