algorithm - 顶点最大入度的有向图

Question

当我遇到这个问题时，我正在尝试查看网络流量的一些应用:

我们从一个有向图开始，G = (V,E)。我们需要向图中添加更多边，以便我们有 \forall u,v\in V, e = (u -> v) 或 e = (v -> u) 但不是两者。即，我们想向图中添加更多边，以便图中的每一对顶点都相互连接(具有传出边或传入边，但不能同时具有两者)。因此，我们总共将有 |V||V-1|/2 条边。当我们构建这个图时，我们需要确保给定顶点的入度，比如 w 是图的所有顶点中的最大值(如果可能的话，给定原始图)。请注意，我们无法更改原始图中边的方向。

我正在尝试通过构建一个没有顶点 w 的网络(以及带有 2 source、s 和 sink、t 的新顶点)的网络来解决它。但是我不确定如何在新图中表示容量和流向，以便将问题简化为网络流，以便在图中找到边缘方向。也许我做的是错的，但我只是写了如果有人可能从中得到提示。

Answer 1

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