Flows in NetworksPDF电子书下载

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