一、中国邮递员问题

中国邮递员问题（Chinese Postman Problem, CPP）是图论中的一个著名问题，它是在1960年由我国学者管梅谷首先提出并研究的。简单来说，就是问：一个邮递员从邮局出发，把一个城市的所有街道都至少走一遍，最后回到邮局，问怎样使他走的总路程最小？这个问题有许多现实的应用，比如一个除雪车从城市的某一位置出发，把城市里所有街道的雪都清扫了，再回到出发点，问怎么走路程最少。我们可以把城市看作一个连通的、简单的带权无向图，节点代表街道的交叉，边代表街道，其权重是街道的长度。一个回路（circuit）是从某一点出发回到这一点的路径，并且可以将一条边经过多次。所以，中国邮递员问题就是求无向图上权重最小（即最短）的回路。

 

1. 与欧拉回路的关系

说到回路，我们肯定会想起欧拉回路（Eulerian circuit），它是在一个无向图中能够访问所有边恰好一次的回路（即“一笔画”）。显然，一个图如果含有欧拉回路，那欧拉回路就是邮递员的最佳路径了（因为他只用把每条边访问一次）。一个连通图有欧拉回路当且仅当所有节点的度数都为偶数。如果这个条件不满足，那么图中就没有欧拉回路，这时邮递员就必须把某些边访问两次及以上。也就是说，我们要在图中找到一些边，把它们复制，使得得到的多重图有欧拉回路，并且这些被复制的边的权重之和最小。

 

2. Edmonds-Johnson算法

管梅谷解决这个问题的方法是“奇偶点图上作业法”，但是复杂度太高，我们这里介绍复杂度更优的Edmonds-Johnson算法。首先，会“坏事儿”的节点就是图上具有奇度数的节点（称为奇节点，度数为偶数的叫偶节点），我们必须给每个奇节点复制一条（从它开始的）边。当图上所有节点都是偶节点时，才有欧拉回路。其次，我们可以看出，每条边至多被复制一次（也就是被邮递员经过两次），因为如果复制两次及以上，邮递员相当于要从这头走到那头又回来，白走了很多路程。或者说，至多复制一次就可以让一个奇节点变成偶节点，所以没必要复制更多次。

 

我们还可以观察到，一个无向图中奇节点的个数一定是偶数。为什么呢？握手引理（Handshaking Lemma）说的是：无向图中所有节点的度数之和等于边数乘2，那么度数之和和一定是偶数。而只有偶数个奇数之和才能是偶数，所以奇节点一定有偶数个。好了，现在我们假设图中有2 m 个奇节点，它们组成的集合为S = { v ₁ , v ₂ , ⋯   , v _{2 m} } 。我们考虑把v 1变成偶节点，那么需要把一条从v 1出发的边复制一份。假设这条边为( v ₁ , u )，u本来是偶节点，把它复制一份，v ₁ 确实变成了偶节点，但u又变成奇节点了。接着又得把u 再变成偶节点，假设我们把( u , h ) 复制一份，u 变偶，h 变奇，再把( h , l ) 复制一份，h 变偶，l 变奇，……什么时候才能结束呢？直到遇到另一个S 中的节点v x（即本来度数为奇数的节点），使得v _x从奇变偶了，才能结束。（如果v ₁本来就和某个奇节点v x相邻，那么只需要把( v ₁ , v _x )复制一份即可。）其实我们发现，我们把v ₁到v _x的路径都复制了一份，使得v ₁ 、v _x的度数+1，中间节点的度数+2，那么这条路径上的所有节点都变成偶节点了。注意，我们想要增加的边的权重之和最小，那我们复制的一定是从v ₁到v _x的最短路，而不是其他更长的路径。

 

 

好了，我们现在知道，把两个奇节点v _i 和v _j 之间的路径复制一份，可以把v _i和v _j 都变成偶节点，花费的代价是v _i和v _j 之间的最短距离（即最短路长度）。我们定义：如果把v _i 到v _j 的最短路径复制了一份，则称v _i 和v _j配对。一个奇节点只能和另外的一个奇节点配对，因为如果和两个奇节点配对的话，那它的度数加2，它还是奇节点。（如果和三个奇节点配对，设这三个奇节点为v _x , v _y , v _z ，那么可以视为它和v _x 配对，v _y 通过它和v _z配对。以此类推。）于是，这个问题就变成了一个最小权匹配问题。至此，Edmonds-Johnson算法也就逐渐浮出水面了。

 

Edmonds-Johnson算法的步骤是：

对于连通的无向简单图G = ( V , E ) （邮局在哪里其实没有关系），设S = { v ₁ , v ₂ , ⋯   , v _{2 m} }是其中度数为奇数的节点。对于S SS中任意的节点对( v i , v j ) ，计算它们的最短路径长度l _{i j}。这一步可以由Floyd全源最短路算法完成。

建立一个带权无向完全图K _{2 m} ，其节点集是S，每对节点v _i , v _j 之间都有边，边权是G 中v _i , v _j 的最短路径l _{i j}。接着，我们需要找到K _{2 m}的最小权完美匹配M ，M是由m条边组成的集合，其中任两条边之间没有公共端点。（“完美”匹配指的是每个奇节点都有与之配对的节点。）寻找最小权完美匹配的过程可以由Edmonds算法在O ( n ³ )的时间内完成（n 为G 中节点个数）。

在G 中，把M 内每条边对应的路径复制一份，得到多重图G ′。

求出G ′的欧拉回路（可以采用Fleury算法），这就是邮递员的最优路径。最终，邮递员所要走的路程是G中边权之和（记为w ( G ) ）+M中边权之和（记为w ( M )）。

因为Floyd全源最短路算法的复杂度为O ( n ³ ) ，求K 2 m最小权完美匹配的复杂度为O ( n ³ )，所以Edmonds-Johnson算法总的复杂度为O ( n ³ ) 。

 

3. 一个例子

假设城市的地图如下：

 

 

可以看到，奇节点组成的集合S = { v ₁ , v ₃ , v ₄ , v ₇ } ，它们的度数分别为3 , 5 , 3 , 3 。m = 2。

 

它们之间的最短路径及最短距离如下：

 

 

据此构造完全图K _{2 m}：

 

 

求出其最小权完美匹配M = { ( v ₁ , v ₄ ) , ( v ₃ , v ₇ ) }

 

 

也就是说，对于v ₁与v ₄之间的最短路径（v ₁ → v ₅ → v ₄ ）、v ₃ 与v ₇ 之间的最短路径（v ₃→v ₇），邮递员要走两次。将这些路径复制后得到的多重图G ′ 如下：

 

 

最后，我们构建G ′的一个欧拉回路：R = v ₁ → v ₂ → v ₃ → v ₄ → v ₁ → v ₅ → v ₂ → v ₇ → v ₃ → v ₇ → v ₆ → v ₃ → v ₅ → v ₄ → v ₅ → v ₁，其权重为w ( G ) + w ( M ) = 27 + 4 = 31。

 

二、平面图上的最大割问题

1. 割

给定无向图G = ( V , E ) ，现在把点集V 分成两个集合S , T 使得S ∪ T = V 且S ∩ T = ∅，这样的一种分割方式G 的一个割（cut），边集C = { ( u , v ) ∣ u ∈ S , v ∈ T }称为由该割决定的割集（cut set），把割集从G中删除后S 和T两部分就不连通了。割集中的每条边都是横跨S 和T两个集合的。

 

2. 最大割及其N P完全性

G 的最大割（maximum cut）是使得割集中含有边数最多的割，也就是使S 和T内部的边最少的割。求一般图的最大割是N P难问题（对应的判定问题，即判断一个图G GG中是否有边数至少为k kk的割是N P完全问题）。接下来我们通过将最大独立集（maximum independent set, MIS）归约到最大割。

 

给定图G = ( V , E ) ，我们要求它的最大独立集。下面我们说明，如果我们判定了另一个图G ′ = ( V ′ , E ′ )的最大割问题，就可以判定G 的最大独立集问题。把G变成G ′ 的过程如下：在G 中新添加一个节点x （可理解为“超级源点”），并让它与V 中所有节点相连（即∀ u ∈ V ，添加边( x , u )。接下来，对于E中的每条边e = ( u , v ) ，添加两个节点u _e , v _e ，并向E ′中添加五条边( u , u _e ) , ( v , v _e ) , ( x , u _e ) , ( x , v _e ) , ( u _e , v _e ) （注意E ′ 并不含有E EE中的边）。我们令G e = ( { u , v , u _e , v _e , x } , { ( u , u _e ) , ( v , v _e ) , ( x , u _e ) , ( x , v _e ) , ( u _e , v _e } )

为边e对应的附件图（gadget），它就是下图中标粗的部分：

 

 

现在，∣ V ′ ∣ = ∣ V ∣ + 1 + 2 ∣ E，∣ E ′ ∣ = ∣ E ∣ + ∣ V ∣ + 5 ∣ E ∣ = 6 ∣ E ∣ + ∣ V ∣ 。我们接下来证明：G 包含一个大小至少为k的独立集I    ⟺    G ′ 中存在一种分割V ′的方法：V ′ = S ∪ T ，使得割集C 的大小∣ C ∣ ≥ k + 4 ∣ E ∣。

 

 ⟹：对于给定的独立集I ，我们构造一个点集S。一开始S = I 。然后对于E EE中的每条边e = ( u , v ) ，做以下几件事：

 

若u ∈ I且v ∉ I，则将v e加入S 。相似地，若v ∈ I 且u ∉ I ，则将u e 加入S 。此时，在e ee对应的附件图G _e 中，有两个节点属于S ，三个节点不属于S，五条边中有四条边（除了x与u或v 相连的那条）都是割边。若u , v ∉ I ，则将u e和v e都加入S 。这下G _e 中仍然有四条边是割边（除了( u _e , v _e ) 不是）。

注意u , v 不可能都属于I，因为I是一个独立集。此外，x不在S中，因此I中节点与x 相连的边都是割边。每个附件图G e 中都有四条边为割边，因此∣ C ∣ = ∣ I ∣ + 4 ∣ E ∣ = k + 4 ∣ E ∣ 。

⟸：现在我们有一个大小至少为k + 4 ∣ E ∣ 的割集C ，它把V ′ 分割成S 和T，接下来要构造一个独立集I II使得∣ I ∣ ≥ k。首先，我们假设x ∈ S ，因为如果x ∉ S，我们把S 和T 互换即可。其次，我们找到S 中属于V 的节点，组成集合I 。对于E 中的任意边e = ( u , v ) ，若u , v ∈ S ，则G e 中至多有三条割边；若u uu和v vv至少有一个不属于S ，则G e 中至多有四条割边。设第一种情况发生的次数为m ( I ) ，或者说m ( I ) = ∣ { ( u , v ) ∈ E ∣ u , v ∈ I } ∣ （即I II内部的边），那么第二种情况发生的次数为∣ E ∣ − m ( I )。所以，割边的个数满足

 

 

即∣ I ∣ ≥ m ( I ) − 4 ∣ E ∣ + ∣ C ∣ ；由∣ C ∣ ≥ k + 4 ∣ E ∣得∣ I ∣ ≥ m ( I ) + k。现在I可能还不是独立集，因为I内部还有边。不过，I内部的边只有m ( I )条，现在我们从I 中移除一些节点，如果( u , v ) ∈ E且u , v ∈ I ，那么我们移除u，则I内部的边至少减少1条，所以我们至多移除m ( I ) 个节点就可以使I 变为独立集了，此时∣ I ∣ ≥ k 。至此，我们就将最大独立集问题归约到了最大割。

 

虽然最大割是N P难的，最小割却可以在多项式时间内求解。根据最大流最小割定理，求最小割相当于求任两个节点间最大流的最大值，这可以用Ford-Fulkson方法或Dinic算法求解。

 

3. 平面图上的最大割问题

一个N P完全问题的某些特殊情况可以在多项式时间内求解。作为一个例子，最大割问题在平面图（planar graph）上就可以在多项式时间内求解。本文介绍的算法是F. Hadlock首先提出的（论文：Hadlock, F.O. (1975). Finding a Maximum Cut of a Planar Graph in Polynomial Time. SIAM J. Comput., 4, 221-225.）。

 

首先，我们最希望的情况就是图G 是二分图（bipartite graph）。如果G 是二分图，那么其节点集可以被分为两个集合S ∪ T，使得每条边都横跨S 和T。此时，每条边都是割边，最大割的大小就是边数。一个图是二分图当且仅当它没有奇圈。平面图的一个平面嵌入可以被分成很多面，每个面被一个圈包围，圈的长度（边数）称为这个面的次数。如果所有面的次数都为偶数，那么这个平面图是二分图，就万事大吉了；但如果这个面的次数是奇数，那就会出现问题——肯定有边不是割边。因此，我们要处理的“刺头”就是奇回路（如果一个面的次数为奇数，则其边界为奇圈，奇回路中一定有奇圈）。

 

 

4. 奇回路覆盖

由于奇回路会坏事儿，我们希望移除一些边使得剩下的图是二分图（即不含有奇回路）。并且，我们希望移除的边越少越好，因为剩下的边一定是割边。如果移除边集D可以使图G 变成二分图（即不含寄回路），则称D 是奇回路覆盖（odd-circuit cover）。我们的目标就是求最小奇回路覆盖（minimum odd-circuit cover），即含有边最少的奇回路覆盖。

 

5. 转化为一般图最大匹配

我们将会看到，处理平面图上最大割问题的方式与处理中国邮递员问题的方式有异曲同工之妙。如果一个面的次数为奇数，我们称这个面为奇面（相应地有偶面）。一条边是同时充当两个面的边界的，所以面的次数之和等于边数的两倍，也就是说面的次数之和为偶数，因此奇面一定有偶数个。对于奇面A，我们需要移除其一条边，使奇回路被破坏。而这条边同时也是另一个面（设为B ）的边界，所以移除这条边之后面B 也少了一条边，那这两个面就被打通了，形成了一个新的大面。

 

 

如果B 是偶面，如上图所示，则形成的大面B ′ 是奇面（注意蓝色的边要算两次），这意味着它还有奇回路。那么就把B ′ 的一条边删除，使它和另一个偶面C 打通，形成更大的奇面C ′ 。……如此循环往复，直到大面可以和某个本来就是奇面的面Z打通，而奇面和奇面打通形成的面是偶面，这样我们就消除了原图中奇面A AA和奇面Z中的奇圈。我们可以理解为，面A 和Z 配对，为了打通A 和Z，需要把沿路的偶面B、C、……、Y也打通。

 

 

当然，把两个面打通需要删除一条边，我们需要让删除的边数最少。因此，我们需要找到面A AA和面Z ZZ的“最短路径”。如果我们把每个面看成一个顶点，那么处理起来会十分方便。正好，对偶图（dual graph）可以帮助到我们。

 

 

对于一个平面图G ，其对偶图G ^∗可能是一个多重图（含有自环和重边），每个节点对应G 中的一个面，如果G 中两个面被一条边分开则对偶图中两个面所对应的两个顶点有一条横跨该边的边。可以看到，如果G 中有奇面A ，则A 在对偶图中对应的节点a 就是奇节点。在G 中将面A , B打通，相当于在G ∗ 中移除a , b 之间的一条边。将G中的面A 变成偶面，就是把G ^∗ 中的点a 变为偶节点。是不是和中国邮递员问题很像了？只不过，我们把节点变成偶节点的方式是删边，而不是复制边。尽管如此，我们的目标是相似的：被删/复制的边的权重之和最小（这里每条边的权重都是1 ，因此就是令被删的边数最少）。办法我们已经介绍过了：找出G ^∗ 中的所有奇节点，构造以他们为节点的完全图，边( v _{i ，}v _j ) 的权重是v _i和v _j 在G ^∗中的最短距离，然后找出完全图的最小权完美匹配。如果v _i 和v _j匹配，那就是从v _i 对应的面出发，一路删边到v _j对应的面，且保证经过的面最少。（最后v _i对应的面和v _j对应的面以及路上经过的所有面都被打通成一个面了。）在对每个奇节点对进行删边操作后，剩下的图就是二分图，其中的每条边都是割边，我们也就求得了最大割中割边的个数。

 

6. 一个例子

考虑下列平面图G ：

 

 

其对偶图G ^∗ 为：

 

 

其中标红的节点为奇节点（S = { a , c , d , g , h , i } 。

在求得S 中节点两两之间的最短路径后，我们构造完全图K ₆ ：

 

 

求得其最小权完美匹配M = { ( a , d ) , ( c , g ) , ( h , i ) } ，并删掉对应的边：

 

 

三、顶点图上最大割问题的NP 完全性

顶点图（apex graph）指的是移除一个节点就可以把它变成平面图的图。移除的那个节点叫做顶点（apex）。一个顶点图可以有多个顶点，如K 5的所有点都是顶点，因为不论移除那个节点最后剩下的图都是平面图K ₄ 。我们将要证明，虽然最大割在平面图上可以在多项式时间内求解，但是只多了一个节点——顶点，问题就变成NP完全的了。

 

首先，平面图上的最大独立集问题是N P完全的，证明见Mohar, B. (2001). Face Covers and the Genus Problem for Apex Graphs. J. Comb. Theory, Ser. B, 82, 102-117.（方法是把平面3-SAT归约到平面图上的独立集问题）。然后，我们把平面图上的独立集归约到顶点图上的最大割问题。回顾“二、2”节的方法，假设G是平面图，现在构造顶点图G ′ 。我们先不加入节点x ，只是为每条边e = ( u , v ) ∈ E 添加节点u _e , v _e，那也就相当于把边u − v 换成了链u − u _e − v _e − v，如果我们把u _e和v _e 放在边u − v 的连线上，那得到的图仍然是平面图。现在加入节点x ，它与目前图中的每个节点都相连。加入x 后，G ′就不一定是平面图了，但从G ′ 中移除x 后剩下的图是平面图。因此x是G ′的一个顶点，G ′ 是顶点图。这样我们就证明了顶点图上的最大割问题是NP完全的。

 

————————————————

本文转自CSDN平台博主：seh_sjlj

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/qaqwqaqwq/article/details/129919124

 

一、中国邮递员问题

中国邮递员问题（Chinese Postman Problem, CPP）是图论中的一个著名问题，它是在1960年由我国学者管梅谷首先提出并研究的。简单来说，就是问：一个邮递员从邮局出发，把一个城市的所有街道都至少走一遍，最后回到邮局，问怎样使他走的总路程最小？这个问题有许多现实的应用，比如一个除雪车从城市的某一位置出发，把城市里所有街道的雪都清扫了，再回到出发点，问怎么走路程最少。我们可以把城市看作一个连通的、简单的带权无向图，节点代表街道的交叉，边代表街道，其权重是街道的长度。一个回路（circuit）是从某一点出发回到这一点的路径，并且可以将一条边经过多次。所以，中国邮递员问题就是求无向图上权重最小（即最短）的回路。

 

1. 与欧拉回路的关系

说到回路，我们肯定会想起欧拉回路（Eulerian circuit），它是在一个无向图中能够访问所有边恰好一次的回路（即“一笔画”）。显然，一个图如果含有欧拉回路，那欧拉回路就是邮递员的最佳路径了（因为他只用把每条边访问一次）。一个连通图有欧拉回路当且仅当所有节点的度数都为偶数。如果这个条件不满足，那么图中就没有欧拉回路，这时邮递员就必须把某些边访问两次及以上。也就是说，我们要在图中找到一些边，把它们复制，使得得到的多重图有欧拉回路，并且这些被复制的边的权重之和最小。

 

2. Edmonds-Johnson算法

管梅谷解决这个问题的方法是“奇偶点图上作业法”，但是复杂度太高，我们这里介绍复杂度更优的Edmonds-Johnson算法。首先，会“坏事儿”的节点就是图上具有奇度数的节点（称为奇节点，度数为偶数的叫偶节点），我们必须给每个奇节点复制一条（从它开始的）边。当图上所有节点都是偶节点时，才有欧拉回路。其次，我们可以看出，每条边至多被复制一次（也就是被邮递员经过两次），因为如果复制两次及以上，邮递员相当于要从这头走到那头又回来，白走了很多路程。或者说，至多复制一次就可以让一个奇节点变成偶节点，所以没必要复制更多次。

 

我们还可以观察到，一个无向图中奇节点的个数一定是偶数。为什么呢？握手引理（Handshaking Lemma）说的是：无向图中所有节点的度数之和等于边数乘2，那么度数之和和一定是偶数。而只有偶数个奇数之和才能是偶数，所以奇节点一定有偶数个。好了，现在我们假设图中有2 m 个奇节点，它们组成的集合为S = { v ₁ , v ₂ , ⋯   , v _{2 m} } 。我们考虑把v 1变成偶节点，那么需要把一条从v 1出发的边复制一份。假设这条边为( v ₁ , u )，u本来是偶节点，把它复制一份，v ₁ 确实变成了偶节点，但u又变成奇节点了。接着又得把u 再变成偶节点，假设我们把( u , h ) 复制一份，u 变偶，h 变奇，再把( h , l ) 复制一份，h 变偶，l 变奇，……什么时候才能结束呢？直到遇到另一个S 中的节点v x（即本来度数为奇数的节点），使得v _x从奇变偶了，才能结束。（如果v ₁本来就和某个奇节点v x相邻，那么只需要把( v ₁ , v _x )复制一份即可。）其实我们发现，我们把v ₁到v _x的路径都复制了一份，使得v ₁ 、v _x的度数+1，中间节点的度数+2，那么这条路径上的所有节点都变成偶节点了。注意，我们想要增加的边的权重之和最小，那我们复制的一定是从v ₁到v _x的最短路，而不是其他更长的路径。

 

 

好了，我们现在知道，把两个奇节点v _i 和v _j 之间的路径复制一份，可以把v _i和v _j 都变成偶节点，花费的代价是v _i和v _j 之间的最短距离（即最短路长度）。我们定义：如果把v _i 到v _j 的最短路径复制了一份，则称v _i 和v _j配对。一个奇节点只能和另外的一个奇节点配对，因为如果和两个奇节点配对的话，那它的度数加2，它还是奇节点。（如果和三个奇节点配对，设这三个奇节点为v _x , v _y , v _z ，那么可以视为它和v _x 配对，v _y 通过它和v _z配对。以此类推。）于是，这个问题就变成了一个最小权匹配问题。至此，Edmonds-Johnson算法也就逐渐浮出水面了。

 

Edmonds-Johnson算法的步骤是：

对于连通的无向简单图G = ( V , E ) （邮局在哪里其实没有关系），设S = { v ₁ , v ₂ , ⋯   , v _{2 m} }是其中度数为奇数的节点。对于S SS中任意的节点对( v i , v j ) ，计算它们的最短路径长度l _{i j}。这一步可以由Floyd全源最短路算法完成。

建立一个带权无向完全图K _{2 m} ，其节点集是S，每对节点v _i , v _j 之间都有边，边权是G 中v _i , v _j 的最短路径l _{i j}。接着，我们需要找到K _{2 m}的最小权完美匹配M ，M是由m条边组成的集合，其中任两条边之间没有公共端点。（“完美”匹配指的是每个奇节点都有与之配对的节点。）寻找最小权完美匹配的过程可以由Edmonds算法在O ( n ³ )的时间内完成（n 为G 中节点个数）。

在G 中，把M 内每条边对应的路径复制一份，得到多重图G ′。

求出G ′的欧拉回路（可以采用Fleury算法），这就是邮递员的最优路径。最终，邮递员所要走的路程是G中边权之和（记为w ( G ) ）+M中边权之和（记为w ( M )）。

因为Floyd全源最短路算法的复杂度为O ( n ³ ) ，求K 2 m最小权完美匹配的复杂度为O ( n ³ )，所以Edmonds-Johnson算法总的复杂度为O ( n ³ ) 。

 

3. 一个例子

假设城市的地图如下：

 

 

可以看到，奇节点组成的集合S = { v ₁ , v ₃ , v ₄ , v ₇ } ，它们的度数分别为3 , 5 , 3 , 3 。m = 2。

 

它们之间的最短路径及最短距离如下：

 

 

据此构造完全图K _{2 m}：

 

 

求出其最小权完美匹配M = { ( v ₁ , v ₄ ) , ( v ₃ , v ₇ ) }

 

 

也就是说，对于v ₁与v ₄之间的最短路径（v ₁ → v ₅ → v ₄ ）、v ₃ 与v ₇ 之间的最短路径（v ₃→v ₇），邮递员要走两次。将这些路径复制后得到的多重图G ′ 如下：

 

 

最后，我们构建G ′的一个欧拉回路：R = v ₁ → v ₂ → v ₃ → v ₄ → v ₁ → v ₅ → v ₂ → v ₇ → v ₃ → v ₇ → v ₆ → v ₃ → v ₅ → v ₄ → v ₅ → v ₁，其权重为w ( G ) + w ( M ) = 27 + 4 = 31。

 

二、平面图上的最大割问题

1. 割

给定无向图G = ( V , E ) ，现在把点集V 分成两个集合S , T 使得S ∪ T = V 且S ∩ T = ∅，这样的一种分割方式G 的一个割（cut），边集C = { ( u , v ) ∣ u ∈ S , v ∈ T }称为由该割决定的割集（cut set），把割集从G中删除后S 和T两部分就不连通了。割集中的每条边都是横跨S 和T两个集合的。

 

2. 最大割及其N P完全性

G 的最大割（maximum cut）是使得割集中含有边数最多的割，也就是使S 和T内部的边最少的割。求一般图的最大割是N P难问题（对应的判定问题，即判断一个图G GG中是否有边数至少为k kk的割是N P完全问题）。接下来我们通过将最大独立集（maximum independent set, MIS）归约到最大割。

 

给定图G = ( V , E ) ，我们要求它的最大独立集。下面我们说明，如果我们判定了另一个图G ′ = ( V ′ , E ′ )的最大割问题，就可以判定G 的最大独立集问题。把G变成G ′ 的过程如下：在G 中新添加一个节点x （可理解为“超级源点”），并让它与V 中所有节点相连（即∀ u ∈ V ，添加边( x , u )。接下来，对于E中的每条边e = ( u , v ) ，添加两个节点u _e , v _e ，并向E ′中添加五条边( u , u _e ) , ( v , v _e ) , ( x , u _e ) , ( x , v _e ) , ( u _e , v _e ) （注意E ′ 并不含有E EE中的边）。我们令G e = ( { u , v , u _e , v _e , x } , { ( u , u _e ) , ( v , v _e ) , ( x , u _e ) , ( x , v _e ) , ( u _e , v _e } )

为边e对应的附件图（gadget），它就是下图中标粗的部分：

 

 

现在，∣ V ′ ∣ = ∣ V ∣ + 1 + 2 ∣ E，∣ E ′ ∣ = ∣ E ∣ + ∣ V ∣ + 5 ∣ E ∣ = 6 ∣ E ∣ + ∣ V ∣ 。我们接下来证明：G 包含一个大小至少为k的独立集I    ⟺    G ′ 中存在一种分割V ′的方法：V ′ = S ∪ T ，使得割集C 的大小∣ C ∣ ≥ k + 4 ∣ E ∣。

 

 ⟹：对于给定的独立集I ，我们构造一个点集S。一开始S = I 。然后对于E EE中的每条边e = ( u , v ) ，做以下几件事：

 

若u ∈ I且v ∉ I，则将v e加入S 。相似地，若v ∈ I 且u ∉ I ，则将u e 加入S 。此时，在e ee对应的附件图G _e 中，有两个节点属于S ，三个节点不属于S，五条边中有四条边（除了x与u或v 相连的那条）都是割边。若u , v ∉ I ，则将u e和v e都加入S 。这下G _e 中仍然有四条边是割边（除了( u _e , v _e ) 不是）。

注意u , v 不可能都属于I，因为I是一个独立集。此外，x不在S中，因此I中节点与x 相连的边都是割边。每个附件图G e 中都有四条边为割边，因此∣ C ∣ = ∣ I ∣ + 4 ∣ E ∣ = k + 4 ∣ E ∣ 。

⟸：现在我们有一个大小至少为k + 4 ∣ E ∣ 的割集C ，它把V ′ 分割成S 和T，接下来要构造一个独立集I II使得∣ I ∣ ≥ k。首先，我们假设x ∈ S ，因为如果x ∉ S，我们把S 和T 互换即可。其次，我们找到S 中属于V 的节点，组成集合I 。对于E 中的任意边e = ( u , v ) ，若u , v ∈ S ，则G e 中至多有三条割边；若u uu和v vv至少有一个不属于S ，则G e 中至多有四条割边。设第一种情况发生的次数为m ( I ) ，或者说m ( I ) = ∣ { ( u , v ) ∈ E ∣ u , v ∈ I } ∣ （即I II内部的边），那么第二种情况发生的次数为∣ E ∣ − m ( I )。所以，割边的个数满足

 

 

即∣ I ∣ ≥ m ( I ) − 4 ∣ E ∣ + ∣ C ∣ ；由∣ C ∣ ≥ k + 4 ∣ E ∣得∣ I ∣ ≥ m ( I ) + k。现在I可能还不是独立集，因为I内部还有边。不过，I内部的边只有m ( I )条，现在我们从I 中移除一些节点，如果( u , v ) ∈ E且u , v ∈ I ，那么我们移除u，则I内部的边至少减少1条，所以我们至多移除m ( I ) 个节点就可以使I 变为独立集了，此时∣ I ∣ ≥ k 。至此，我们就将最大独立集问题归约到了最大割。

 

虽然最大割是N P难的，最小割却可以在多项式时间内求解。根据最大流最小割定理，求最小割相当于求任两个节点间最大流的最大值，这可以用Ford-Fulkson方法或Dinic算法求解。

 

3. 平面图上的最大割问题

一个N P完全问题的某些特殊情况可以在多项式时间内求解。作为一个例子，最大割问题在平面图（planar graph）上就可以在多项式时间内求解。本文介绍的算法是F. Hadlock首先提出的（论文：Hadlock, F.O. (1975). Finding a Maximum Cut of a Planar Graph in Polynomial Time. SIAM J. Comput., 4, 221-225.）。

 

首先，我们最希望的情况就是图G 是二分图（bipartite graph）。如果G 是二分图，那么其节点集可以被分为两个集合S ∪ T，使得每条边都横跨S 和T。此时，每条边都是割边，最大割的大小就是边数。一个图是二分图当且仅当它没有奇圈。平面图的一个平面嵌入可以被分成很多面，每个面被一个圈包围，圈的长度（边数）称为这个面的次数。如果所有面的次数都为偶数，那么这个平面图是二分图，就万事大吉了；但如果这个面的次数是奇数，那就会出现问题——肯定有边不是割边。因此，我们要处理的“刺头”就是奇回路（如果一个面的次数为奇数，则其边界为奇圈，奇回路中一定有奇圈）。

 

 

4. 奇回路覆盖

由于奇回路会坏事儿，我们希望移除一些边使得剩下的图是二分图（即不含有奇回路）。并且，我们希望移除的边越少越好，因为剩下的边一定是割边。如果移除边集D可以使图G 变成二分图（即不含寄回路），则称D 是奇回路覆盖（odd-circuit cover）。我们的目标就是求最小奇回路覆盖（minimum odd-circuit cover），即含有边最少的奇回路覆盖。

 

5. 转化为一般图最大匹配

我们将会看到，处理平面图上最大割问题的方式与处理中国邮递员问题的方式有异曲同工之妙。如果一个面的次数为奇数，我们称这个面为奇面（相应地有偶面）。一条边是同时充当两个面的边界的，所以面的次数之和等于边数的两倍，也就是说面的次数之和为偶数，因此奇面一定有偶数个。对于奇面A，我们需要移除其一条边，使奇回路被破坏。而这条边同时也是另一个面（设为B ）的边界，所以移除这条边之后面B 也少了一条边，那这两个面就被打通了，形成了一个新的大面。

 

 

如果B 是偶面，如上图所示，则形成的大面B ′ 是奇面（注意蓝色的边要算两次），这意味着它还有奇回路。那么就把B ′ 的一条边删除，使它和另一个偶面C 打通，形成更大的奇面C ′ 。……如此循环往复，直到大面可以和某个本来就是奇面的面Z打通，而奇面和奇面打通形成的面是偶面，这样我们就消除了原图中奇面A AA和奇面Z中的奇圈。我们可以理解为，面A 和Z 配对，为了打通A 和Z，需要把沿路的偶面B、C、……、Y也打通。

 

 

当然，把两个面打通需要删除一条边，我们需要让删除的边数最少。因此，我们需要找到面A AA和面Z ZZ的“最短路径”。如果我们把每个面看成一个顶点，那么处理起来会十分方便。正好，对偶图（dual graph）可以帮助到我们。

 

 

对于一个平面图G ，其对偶图G ^∗可能是一个多重图（含有自环和重边），每个节点对应G 中的一个面，如果G 中两个面被一条边分开则对偶图中两个面所对应的两个顶点有一条横跨该边的边。可以看到，如果G 中有奇面A ，则A 在对偶图中对应的节点a 就是奇节点。在G 中将面A , B打通，相当于在G ∗ 中移除a , b 之间的一条边。将G中的面A 变成偶面，就是把G ^∗ 中的点a 变为偶节点。是不是和中国邮递员问题很像了？只不过，我们把节点变成偶节点的方式是删边，而不是复制边。尽管如此，我们的目标是相似的：被删/复制的边的权重之和最小（这里每条边的权重都是1 ，因此就是令被删的边数最少）。办法我们已经介绍过了：找出G ^∗ 中的所有奇节点，构造以他们为节点的完全图，边( v _{i ，}v _j ) 的权重是v _i和v _j 在G ^∗中的最短距离，然后找出完全图的最小权完美匹配。如果v _i 和v _j匹配，那就是从v _i 对应的面出发，一路删边到v _j对应的面，且保证经过的面最少。（最后v _i对应的面和v _j对应的面以及路上经过的所有面都被打通成一个面了。）在对每个奇节点对进行删边操作后，剩下的图就是二分图，其中的每条边都是割边，我们也就求得了最大割中割边的个数。

 

6. 一个例子

考虑下列平面图G ：

 

 

其对偶图G ^∗ 为：

 

 

其中标红的节点为奇节点（S = { a , c , d , g , h , i } 。

在求得S 中节点两两之间的最短路径后，我们构造完全图K ₆ ：

 

 

求得其最小权完美匹配M = { ( a , d ) , ( c , g ) , ( h , i ) } ，并删掉对应的边：

 

 

三、顶点图上最大割问题的NP 完全性

顶点图（apex graph）指的是移除一个节点就可以把它变成平面图的图。移除的那个节点叫做顶点（apex）。一个顶点图可以有多个顶点，如K 5的所有点都是顶点，因为不论移除那个节点最后剩下的图都是平面图K ₄ 。我们将要证明，虽然最大割在平面图上可以在多项式时间内求解，但是只多了一个节点——顶点，问题就变成NP完全的了。

 

首先，平面图上的最大独立集问题是N P完全的，证明见Mohar, B. (2001). Face Covers and the Genus Problem for Apex Graphs. J. Comb. Theory, Ser. B, 82, 102-117.（方法是把平面3-SAT归约到平面图上的独立集问题）。然后，我们把平面图上的独立集归约到顶点图上的最大割问题。回顾“二、2”节的方法，假设G是平面图，现在构造顶点图G ′ 。我们先不加入节点x ，只是为每条边e = ( u , v ) ∈ E 添加节点u _e , v _e，那也就相当于把边u − v 换成了链u − u _e − v _e − v，如果我们把u _e和v _e 放在边u − v 的连线上，那得到的图仍然是平面图。现在加入节点x ，它与目前图中的每个节点都相连。加入x 后，G ′就不一定是平面图了，但从G ′ 中移除x 后剩下的图是平面图。因此x是G ′的一个顶点，G ′ 是顶点图。这样我们就证明了顶点图上的最大割问题是NP完全的。

 

————————————————

本文转自CSDN平台博主：seh_sjlj

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/qaqwqaqwq/article/details/129919124