基于二分图最大匹配的有向图转“良图”最小修改算法设计

问题定义 #

给定有向图G=(V,E)，满足以下条件的图被称为良图：

• 存在且仅存在一个中心顶点v：v与其余所有顶点u同时存在双向边（uv和vu）
• 除中心外的所有顶点，入度与出度均为2

目标是通过最少的边修改（添加或删除有向边）将G转化为良图，要求算法时间复杂度为O(nT(n))，其中T(n)为二分图最大匹配的时间复杂度。

核心思路 #

良图必须有且仅有一个中心，因此我们可以枚举每个顶点作为候选中心，分别计算以该顶点为中心时的最小修改次数，最终取所有候选中的最小值——这就是需要调用n次最大匹配算法的原因。

针对每个候选中心v，我们将问题拆分为两个独立部分计算修改成本：

1. 中心与其他顶点的双向边调整 #

对于每个非中心顶点u，必须保证uv和vu同时存在：

• 若两条边都存在：无修改成本
• 若仅存在一条边：需添加缺失的那条边，成本+1
• 若两条边都不存在：需添加两条边，成本+2

遍历所有u≠v即可计算出这部分的修改成本，记为C(v)。

2. 非中心顶点的入度/出度约束满足 #

设非中心顶点集合为U = V \ {v}，大小为m = n-1。由于中心v已为每个u∈U贡献1个入度和1个出度，因此u在U内部的子图中需要满足：入度=1，出度=1（总入度/出度才能达到2）。

这等价于将U的子图转化为若干有向环的集合，我们可以通过二分图最大匹配来最小化修改次数：

• 构建二分图：左部节点代表U中顶点的出度需求，右部节点代表U中顶点的入度需求
• 对于U中任意a≠b，若原图存在边ab，则在二分图中添加一条左a→右b的边（匹配这条边意味着保留原边，无需修改）

设该二分图的最大匹配数为M，U内部原边数为E_U，则这部分的最小修改成本为：

D(v) = E_U + m - 2*M

推导逻辑：

• 需要删除的边数：原边中未被匹配的数量E_U - M
• 需要添加的边数：满足入度/出度需求共需m条边，减去已保留的M条，即m - M
• 总修改成本为两者之和，化简后得到上述公式

总修改成本 #

对于候选中心v，总修改成本为C(v) + D(v)。

算法步骤 #

1. 初始化最小修改次数为无穷大
2. 遍历每个顶点v∈V：
   a. 计算C(v)：统计v与所有u≠v之间缺失的双向边数量
   b. 提取非中心顶点集合U，统计U内部的原边数E_U
   c. 构建对应的二分匹配图
   d. 调用二分图最大匹配算法得到匹配数M
   e. 计算D(v) = E_U + (n-1) - 2*M
   f. 计算总成本C(v)+D(v)，若小于当前最小值则更新
3. 返回最终的最小修改次数

时间复杂度验证 #

• 枚举n个候选中心：n次循环
• 每次循环中：
  • 计算C(v)：O(n)时间
  • 构建二分图：O(n²)时间（最多n²条边）
  • 最大匹配计算：T(n)时间（二分图节点数为O(n)）
• 若T(n)≥n²（例如Hopcroft-Karp算法的时间复杂度为O(n²√n)），则总时间复杂度为O(nT(n))，符合要求。

内容的提问来源于stack exchange，提问作者Stephen Stone