無限ネットワーク上のマキシミニ切断問題

Abstract

The study of duality relations between the max-flow problems and the min-cut problems seems to be one of the most important themes in the theory ofnetworks. On a finite network, the celebrated max-flow min-cut theorem due to Ford and Fulkerson [2] has been the unique result for this direction before the work of Strang [6]. On an infinite network, Yamasaki [7] and Nakamura and Yamasaki[4] gave several max-flow min-cut theorems related to several kinds of flows and cuts. In this paper, we shall introduce a notion of an exceptional set of cuts with respect to the extremal width and consider a maximin cut problem. It will be shown by using the penalty method that the value of this maximin problem is equal to thevalue of a max-flow problem.
For notation and terminology, we mainly follow [3] and [5].