《FLOWS IN NETWORKS》

CHAPTER ⅠSTATIC MAXIMAL FLOW1

Introduction1

1．Networks2

2．Flows in networks4

3．Notation9

4．Cuts10

5．Maximal flow11

6．Disconnecting sets and cuts14

7．Multiple sources and sinks15

8．The labeling method for solving maximal flow problems17

9．Lower bounds on arc flows22

10．Flows in undirected and mixed networks23

11．Node capacities and other extensions23

12．Linear programming and duality principles26

13．Maximal flow value as a function of two arc capacities30

References35

CHAPTER ⅡFEASIBILITY THEOREMS AND COMBINATORIAL APPLICATIONS36

Introduction36

1．A supply-demand theorem36

2．A symmetric supply-demand theorem42

3．Circulation theorem50

4．The K？nig-Egerváry and Menger graph theorems53

5．Construction of a maximal independent set of admissible cells55

6．A bottleneck assignment problem57

7．Unicursal graphs59

8．Dilworth＇s chain decomposition theorem for partially ordered sets61

9．Minimal number of individuals to meet a fixed schedule of tasks64

10．Set representatives67

11．The subgraph problem for directed graphs75

12．Matrices composed of O＇s and l＇s79

References91

CHAPTER ⅢMINIMAL COST FLOW PROBLEMS93

Introduction93

1．The Hitchcock problem95

2．The optimal assignment problem111

3．The general minimal cost flow problem113

4．Equivalence of Hitchcock and minimal cost flow problems127

5．A shortest chain algorithm130

6．The minimal cost supply-demand problem:non-negative directed cycle costs134

7．The warehousing problem137

8．The caterer problem140

9．Maximal dynamic flow142

10．Project cost curves151

11．Constructing minimal cost circulations162

References169

CHAPTER ⅣMULTI-TERMINAL MAXIMAL FLOWS173

Introduction173

1．Forests,trees,and spanning subtrees173

2．Realization conditions176

3．Equivalent networks177

4．Network synthesis187

References191