Question

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.

Answer 1

First, divide the vertex weights into a maximum number of portions that each sum to 0 and handle them separately.

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.

So the answer is the number of vertices minus the maximum number of parts the weights can be divided into such that each part sums to 0.