Creating network of max flow with 10 nodes, 18 directed edges

Question

I'm given the following network:

I'm attempting to build a network with maximum flow using weights 1-18 such that the loss of an individual node (not the source or sink) causes the least disruption to the flow.

I know that the max-flow min-cut theorem states that in any network, the value of any maximum flow is equal to the capacity of any minimum cut. With the out-degree of the source and in-degree of the sink to be maximized, I believe I'd want some combination of 18,13,14 coming out of $a$ and 12,17,16 into $j$, showing a capacity of 45.

However, from there I'm not sure. Any thoughts/directions?

Answer 1

There are four stages in this network, progressing from $A$, to $BCD$, to $EF$, to $GHI$, to $J$.

Among the 18 edges, you have a total of $\sum_{i=1}^{18}i=171$ units of flow to distribute around the network. Therefore it is not possible for each of the four stages to support a flow of 43, since $4*43=172$. So let's aim for a flow of 42.

Playing around with the numbers, it is not too hard to achieve this maximum, for example arranging the flows as follows:

(I hope the diagram is understandable...)

      18 (b)  16                   14  (g) 17
               2                    3
                   (30 through e)
(a)   13 (c)   9                    7  (h) 15   (j)
               4                    8
                   (12 through f)
      11 (d)   5                    9  (i) 10
               6                    1

Notice that 9 appears twice in that diagram, and 12 does not appear. You can set either of the edges with flow 9 to a weight of 12 (it won't help the flow, but it means you are using each number from 1 to 18 exactly once).