I have a four node, cyclic, undirected graph. Each edge can support up to 8 capacity. Given a set of connections between all vertices, I want to know if the connection is possible, and if so how.
I'll denote the vertices with a,b,c,d where a is connected to d and b, b connected to a and c... The edges will be denoted 1,2,3,4 where 1 is between a and b, 2 is between b and c... The diagonal vertices are not connected. i.e. G=((a,b,c,d), ((a,b),(b,c),(c,d),(d,a))
Example a: if a wants to send 16 cars to c it must send 8 via edge 1&2, and the other 8 via 3&4. This means no more traffic can be supported.
Example b: if a wants to send 3 to c, and c wants to send 5 to a, and b wants to send 8 to d, then the flow is again full, because a will occupy 1&2 with 4, and 3&4 with 1 car. C will occupy 3&4 with his 3 cars, leaving capacity of 4 on all edges, which will be used by b going to d.
I think I can reduce the problem to this: Given the set of connections, first calculate the diagonal connections (i.e. between a,c or b,d). Spread them as ceil of their mean (i.e. if a wants to send 6 and c wants to send 1 to each other, consider this as both of them sending 4, each 4 is on different route). Then solve the problem with decreased capacity (new capacity = old capacity - diagonal traffic)
Solving the new problem is much easier and can be solved by a greedy algorithm, I think.
My question is this: how to prove my hypothesis, and is my assumption (using ceil of mean on the diagonal connections) is correct.
Much appreciated