具有顶点最大入度的有向图

Question

当我研究网络流的几个应用时，遇到了这个问题：

我们从一个有向图开始，G = (V，E)。我们需要添加更多的边到图中，以便于我们有 \forall u,v \in V, e = (u -> v) or e = (v -> u) but not both。换句话说，我们想要添加更多的边到图中，以便于图中的每一对顶点都彼此连接（可以是出边或入边，但不是同时拥有）。因此，总共我们将会有|V||V-1|/2 条边。而在构建这个图的同时，我们需要确保给定顶点w的入度是整个图中最大的（如果可能的话，根据原始图）。请注意，我们不能改变原始图中的边的方向。

我正在尝试使用网络流通过构建一个没有顶点w的网络（并且具有源s和汇t的两个新节点）来解决它。但是我不确定如何表示新图中的容量和流向，以简化问题，以便寻找图中的边的方向。也许我正在做的是错误的，但我只是写下来以防有人能够得到提示。

- user760955

Answer 1

攻击这种问题时，我倾向于写下一个数学程序然后对它进行调整。显然，我们应该将涉及w的所有缺失边定向为w。让d成为w的入度。对于所有不同的i、j，如果弧i→j出现在解决方案中，则x_{ij}=1；如果弧j→i出现，则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）。

- Per