Question 4.97

67. The accompanying tableau arose by applying the Northwest Corner Rule.

image

The accompanying graph was constructed so that there is one edge for each circled vertex in the tableau above.

image
  1. Verify that the graph is a tree.
  2. Show that for each empty cell in the tableau, adding to the graph the unique edge that corresponds to the empty cell creates one circuit.
  3. Show that this circuit corresponds to the one that is used to find the indicator value of the empty cell.

67.

(a) Connected and has no circuit

(b) Add edge joining vertex I to vertex 2; add edge from vertex I to vertex 3.

(c) Circuit 2, I, 1, II, 2 corresponds to the circuit of cells, (I, 2), (I, 1), (II, 1), (II, 2), (I, 2). Circuit 3, I, 1, II, 3 corresponds to the circuit of cells, (I, 3), (I, 1), (II, 1), (II, 3), (I, 3).