TAOCP 2.3.4.1 Exercise 8
Let a reduced flow chart be obtained from an original flow chart by combining a set of vertices into a supervertex and summing the corresponding edge flows.
Exercise 8. [**] $$M25$$ When applying Kirchhoff's first law to program flow charts, we usually are interested only in the vertex flows (the number of times each box of the flow chart is performed), not the edge flows analyzed in the text. For example, in the graph of exercise 7, the vertex flows are $A=E_2+E_4$, $B=E_5$, $C=E_3+E_7+E_8$, $D=E_6+E_9$.
If we group some vertices together, treating them as one "supervertex," we can combine edge flows that correspond to the same vertex flow. For example, edges $e_2$ and $e_4$ can be combined in the flow chart above if we also put $B$ with $D$:
(Here $e_0$ has also been added from Stop to Start, as in the text.) Continuing this procedure, we can combine $e_3+e_7$, then $(e_3+e_7)+e_8$, then $e_6+e_9$, until we obtain the reduced flow chart having edges $s=e_1$, $a=e_2+e_4$, $b=e_5$, $c=e_3+e_7+e_8$, $d=e_6+e_9$, $t=e_0$, precisely one edge for each vertex in the original flow chart:
By construction, Kirchhoff's law holds in this reduced flow chart. The new edge flows are the vertex flows of the original; hence the analysis in the text, applied to the reduced flow chart, shows how the original vertex flows depend on each other.
Prove that this reduction process can be reversed, in the sense that any set of flows ${a,b,\ldots}$ satisfying Kirchhoff's law in the reduced flow chart can be "split up" into a set of edge flows ${e_0,e_1,\ldots}$ in the original flow chart. These flows $e_j$ satisfy Kirchhoff's law and combine to yield the given flows ${a,b,\ldots}$; some of them might, however, be negative. (Although the reduction procedure has been illustrated here for only one particular flow chart, your proof should be valid in general.)
Verified: no
Solve time: 25s
Let a reduced flow chart be obtained from an original flow chart by combining a set of vertices into a supervertex and summing the corresponding edge flows. Denote the edges of the reduced chart by $a,b,\ldots$ and the constituent edges of the original chart that were combined into $a$ by $e_{i_1},\ldots,e_{i_k}$. If a set of flows ${a,b,\ldots}$ satisfies Kirchhoff's law in the reduced chart, we may assign flows to the original edges recursively along a free subtree of the subgraph induced by the combined vertices. Specifically, choose a spanning tree of the subgraph formed by the vertices combined into the supervertex. Assign the flow along one leaf edge of this tree to be equal to the corresponding supervertex flow minus the sum of flows already assigned to other incident edges; then proceed along the tree, assigning each remaining edge flow in terms of already assigned edges so that Kirchhoff's law holds at every vertex. Since the subtree spans all vertices of the combined set and has $n-1$ edges if there are $n$ vertices, this procedure determines all edge flows uniquely except that some flows may be negative. Repeating this procedure for each supervertex in the reduction yields a set of original edge flows ${e_0,e_1,\ldots}$ that satisfy Kirchhoff's law and combine to give the prescribed reduced flows ${a,b,\ldots}$. This completes the proof.
∎