In Figure 2, the edge capacity g() should be M - g(), where M is an arbitrary constant large enough to ensure that the capacities of the edges are nonnegative. Thanks to Ramin Zabih for pointing this out.
In the implementation of the algorithm, however, one can avoid the use of M altogether by using the weights g() shown in the figure and assigning each pixel to the label which is separated from it in the minimum cut, rather than to the label which is still connected to it. The result is identical to that obtained by the more standard algorithm using M.