CHAPTER Ⅰ STATIC MAXIMAL FLOW 1
Introduction 1
1．Networks 2
2．Flows in networks 4
3．Notation 9
4．Cuts 10
5．Maximal flow 11
6．Disconnecting sets and cuts 14
7．Multiple sources and sinks 15
8．The labeling method for solving maximal flow problems 17
9．Lower bounds on arc flows 22
10．Flows in undirected and mixed networks 23
11．Node capacities and other extensions 23
12．Linear programming and duality principles 26
13．Maximal flow value as a function of two arc capacities 30
References 35
CHAPTER Ⅱ FEASIBILITY THEOREMS AND COMBINATORIAL APPLICATIONS 36
Introduction 36
1．A supply-demand theorem 36
2．A symmetric supply-demand theorem 42
3．Circulation theorem 50
4．The K？nig-Egerváry and Menger graph theorems 53
5．Construction of a maximal independent set of admissible cells 55
6．A bottleneck assignment problem 57
7．Unicursal graphs 59
8．Dilworth＇s chain decomposition theorem for partially ordered sets 61
9．Minimal number of individuals to meet a fixed schedule of tasks 64
10．Set representatives 67
11．The subgraph problem for directed graphs 75
12．Matrices composed of 0＇s and 1＇s 79
References 91
CHAPTER Ⅲ MINIMAL COST FLOW PROBLEMS 93
Introduction 93
1．The Hitchcock problem 95
2．The optimal assignment problem 111
3．The general minimal cost flow problem 113
4．Equivalence of Hitchcock and minimal cost flow problems 127
5．A shortest chain algorithm 130
6．The minimal cost supply-demand problem:non-negative directed cycle costs 134
7．The warehousing problem 137
8．The caterer problem 140
9．Maximal dynamic flow 142
10．Project cost curves 151
11．Constructing minimal cost circulations 162
References 169
CHAPTER Ⅳ MULTI-TERMINAL MAXIMAL FLOWS 173
Introduction 173
1．Forests,trees,and spanning subtrees 173
2．Realization conditions 176
3．Equivalent networks 177
4．Network synthesis 187
References 191