向图，顶点的最大入度 [英] Directed graph with max indegree of a vertex

问题描述

我是想看看网络流量的一些应用程序，当我遇到这个问题：

I was trying to look at few applications of network flow when I came across this problem:

我们开始有向图， G =（V，E）。我们需要更多的边添加到图表，使得我们有 \ FORALL U，V \在V，E =（U - ＆GT; v）或E =（V - ＆GT; U），但不能同时。即，我们希望更多的边添加到图表，使得每对顶点中的图形被连接到彼此（或者与一个传出边缘或呼入边缘但不是两者）。因此，我们总共将有 | V || V-1 | / 2 边缘。虽然我们建立这个图中，我们需要确保一个给定的顶点的入度，说是W 是图的所有顶点之间的最大值（如果可能的话，给原始图）。需要注意的是，我们不能改变的边缘的方向在原来的曲线图。

We begin with a directed graph, G = (V,E). We need to add more edges to the graph such that we have \forall u,v \in V, e = (u -> v) or e = (v -> u) but not both. i.e. we want to add more edges to the graph so that every pair of vertices in the graph are connected to each other (either with an outgoing edge or incoming edge but not both). So, in total we will have |V||V-1|/2 edges. While we build this graph, we need to ensure that the indegree of a given vertex, say w is the maximum among all the vertices of the graph (if it is possible, given the original graph). Note that we cannot change the orientation of the edges in the original graph.

我想解决它使用的网络流量通过建立一个网络，而顶点是W （和 2 新顶点源，S和水槽，T）。但我不知道如何重新present的能力，并在新图中流动的方向，从而简化，以便找到图中的边缘取向的问题，网络流量。也许我在做什么是错的，但我只是写了，如​​果有人可能会得到一个提示它。

I am trying to solve it using network flow by building a network without vertex w (and with 2 new vertices for source, s and sink, t). But I'm not sure how to represent the capacities and flow direction in the new graph so as to simplify the problem to network flow in order to find the edge orientations in the graph. Maybe what I'm doing is wrong, but I just wrote if someone might get a hint from it.

推荐答案

在攻击这样的问题，我倾向于写下的数学程序，然后按摩它。很显然，我们应该定位都缺少边涉及W¯¯走向瓦特令d是造成度W上。对于所有不同的I，J，让 X_ {IJ} = 1，如果弧I->出现J.在溶液中，并让 X_ {IJ} = 0，如果弧J->我出现。

When attacking this kind of problem, I tend to write down a mathematical program and then massage it. Clearly, we should orient all missing edges involving w toward w. Let d be the resulting in-degree of w. For all distinct i, j, let x_{ij} = 1 if arc i->j appears in the solution and let x_{ij} = 0 if arc j->i appears.

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

重写使用 X_ {IJ} 仅在I＆LT;学家

Rewrite to use x_{ij} only if i < j.

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

现在（*）开始像保护的限制，因为每个变量出现一次消极和积极的一次。让我们改变不平等到平等的。

Now (*) begins to resemble conservation constraints, as each variable appears once negatively and once positively. Let's change the inequality to an equality.

(*) 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）。

We're almost all the way to a flow LP -- we just need to clean out the constants 1 and k. I'll let you handle the rest (it involves introducing t).

这篇关于向图，顶点的最大入度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！