2 maoxunxing maoxunxing 于 2014.12.14 17:27 提问

已知每个顶点的入度和出度,用最大流的方式求边

比如已知出度是(2, 1, 1, 1),入度是(1, 2, 1, 1).

如下是解法图解:

解法图解

根据英文解释和图解,它的做法是,先弄出起点X和终点Y,根据每个顶点的出度,得到X_A的容量是2,X_B、X_C、X_D的容量是1;然后从A、B、C、D引出边到其他顶点,因为顶点之间只可能有一条边,所以这些边的容量是1。假定最大流是边的个数,也就是出度或者入度的和,这里计算得到是5。

我的疑惑是:它怎么根据最大流得到中间那些红色边的呢??

附英文:
Let's take this problem for instance: "You are given the in and out degrees of the vertices of a directed graph. Your task is to find the edges (assuming that no edge can appear more than once)." First, notice that we can perform this simple test at the beginning. We can compute the number M of edges by summing the out-degrees or the in-degrees of the vertices. If these numbers are not equal, clearly there is no graph that could be built. This doesn't solve our problem, though. There are some greedy approaches that come to mind, but none of them work. We will combine the tricks discussed above to give a max-flow algorithm that solves this problem. First, build a network that has 2 (in/out) vertices for each initial vertex. Now draw an edge from every out vertex to every in vertex. Next, add a super-source and draw an edge from it to every out-vertex. Add a super-sink and draw an edge from every in vertex to it. We now need some capacities for this to be a flow network. It should be pretty obvious what the intent with this approach is, so we will assign the following capacities: for each edge drawn from the super-source we assign a capacity equal to the out-degree of the vertex it points to. As there may be only one arc from a vertex to another, we assign a 1 capacity to each of the edges that go from the outs to the ins. As you can guess, the capacities of the edges that enter the super-sink will be equal to the in-degrees of the vertices. If the maximum flow in this network equals M - the number of edges, we have a solution, and for each edge between the out and in vertices that has a flow along it (which is maximum 1, as the capacity is 1) we can draw an edge between corresponding vertices in our graph. Note that both x-y and y-x edges may appear in the solution. This is very similar to the maximum matching in a bipartite graph that we will discuss later. An example is given below where the out-degrees are (2, 1, 1, 1) and the in-degrees (1, 2, 1, 1).

问题来源:
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow2

1个回答

devmiao
devmiao   Ds   Rxr 2014.12.14 19:06
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!