具有顶点最大indegree的有向图

Question

当我遇到这个问题时,我试图查看网络流量的一些应用程序:

我们从有向图开始G = (V,E).我们需要为图形添加更多边缘\forall u,v \in V, e = (u -> v) or e = (v -> u) but not both.即我们想要在图形中添加更多边缘,以便图形中的每对顶点相互连接(与出口边缘或入边缘相连,但不能同时连接两者).所以,总的来说我们会有|V||V-1|/2优势.在我们构建此图时,我们需要确保给定顶点的indegree,比如w图中所有顶点中的最大值(如果可能的话,给定原始图).请注意,我们无法更改原始图形中边的方向.

我试图通过构建一个没有顶点的网络w(以及2源,s和接收器的新顶点,t)使用网络流来解决它.但我不确定如何在新图中表示容量和流向,以便将问题简化为网络流,以便在图中找到边缘方向.也许我正在做的事情是错的,但我写道,如果有人可能从中得到一个暗示.

Answer 1

在解决这类问题时，我倾向于写下一个数学程序，然后对其进行按摩。显然，我们应该将所有涉及 w 的缺失边定向为 w。设 d 为 w 的入度。对于所有不同的 i、j，x_{ij}如果解中出现 arc i->j，则 let = 1；x_{ij}如果 arc j->i 出现，则 let = 0。

forall j. sum_i x_{ij} <= k
forall i <> j. x_{ij} = 1 - x_{ji}
forall i <> j. x_{ij} in {0, 1}

重写为仅当 i < j 时使用x_{ij}。

(*) forall j. sum_{i<j} x_{ij} + sum_{i>j} (1-x_{ji}) <= k
forall i < j. x_{ij} in {0, 1}

现在（*）开始类似于守恒约束，因为每个变量出现一次为负，一次为正。让我们把不等式改为等式。

(*) forall j. x_{si} + sum_{i<j} x_{ij} + sum_{i>j} (1-x_{ji}) = k
              ^^^^^^                                           ^
forall i < j. x_{ij} in {0, 1}
forall i. x_{si} >= 0
^^^^^^^^^^^^^^^^^^^^^

我们几乎已经完成了流程 LP——我们只需要清除常量1和k。剩下的事情我会让你处理（涉及到介绍 t）。