# Minimum number of edges - directed graph with given sums of weights

Let's consider a directed graph with positive edge weights. For every vertex we determine the difference

D = (summary weight of edges directed FROM this vertex)-(summary weight of edges directed INTO this vertex).

We are given the difference D for every vertex. Sum of all the D's is always 0. What is the best algorithm of finding a graph connecting those vertexes, with minimum number of edges.

If this is not clear, there's an example: we have three vertexes and differences for them: D_A = 5, D_B = -20, D_C = 15 (total = 0).

Solution (the best graph connecting those vertexes) would consist of two edges: A--(5)-->B, C--(15)-->B, and it satisfies all the conditions. This example is trivial, but I believe that solution to this problem in general is not simple at all.

• There is some requirement you are not stating. You don't just want the minimum number of edges, but you want --- what? --- the maximum sum of weights on the edges (consistent with the $D$-values)? – Gerry Myerson Mar 1 '13 at 11:35

For each set of vertices whose weights sum to 0, you can can implement them as a path with edges forward or backward. Just arrange them in arbitrary order and decide one edge at a time. For example for $a=2, b=-3, c=-4, d=6, e=-1$, use order $a-b-c-d-e$, then you can set $a\to b$ weight 2, $c\to b$ weight 1, $d\to c$ weight 5, $d\to e$ weight 1. There is no way to go wrong.