无向图边标记优化问题：求解满足约束的最小标记总和

核心思路 #

要最小化标记总和，优先级为：尽量用0（代价0）> 其次用1（代价1）> 最后用2（代价2）。但标0的边必须有至少一条相邻边标2，所以关键是找到最少的2标记边，让尽可能多的边能合法标0，剩余无法标0的边标1。

问题转化 #

将原问题转化为线图上的约束优化问题：

1. 构建原图的线图L(G)：
   • 线图的每个顶点对应原图的一条边。
   • 线图中两个顶点相邻，当且仅当原图中对应的两条边共享一个顶点（即相邻）。
2. 原问题的约束等价于：线图中标0的顶点（对应原图标0的边）必须与至少一个标2的顶点（对应原图标2的边）相邻；标1的顶点无约束。

我们的目标是给线图的顶点分配0/1/2标记，最小化总代价（0×0 +1×1 +2×2）。

具体解法：最小割建模 #

可以将问题转化为流网络的最小割问题，用最大流算法求解：

1. 构建流网络 #

• 设置源点s和汇点t。
• 对线图的每个顶点v（对应原图边e）：
  • 从s到v连一条容量为1的边：代表若给e标1，需付出1的代价。
  • 从v到t连一条容量为2的边：代表若给e标2，需付出2的代价。
• 对线图中每一对相邻顶点u和v（对应原图中相邻的两条边）：
  • 分别从u到v、v到u连一条容量为无穷大的边：强制约束“若v标0（不割s-v和v-t），则至少有一个邻居u标2（割掉u-t）”——因为无穷大的边无法被割，若v标0但所有邻居都不标2，会存在s->u->v->t的路径，不构成合法割集。

2. 计算最小割 #

用Dinic等高效最大流算法计算s到t的最大流，根据最大流最小割定理，最大流的数值等于最小割的容量，这个容量就是满足约束的最小标记总和。

特殊场景验证 #

• 孤立边：无相邻边，无法标0，只能标1（代价1，比标2更优）。
• 两条相邻边：要么一条标2、一条标0（总和2），要么两条都标1（总和2），两种方案等价。
• 三角形（三条两两相邻的边）：选一条边标2，另外两条标0，总和2（比三条都标1的总和3更优）。

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