Theory of Nets: Flows in Networks

Cover......Page __sk_0000.djvu
Copyright......Page __sk_0002.djvu
Contents......Page __sk_0003.djvu
Preface......Page __sk_0007.djvu
1.1 Basic Definitions of Abstract Graphs......Page __sk_0011.djvu
1.2 Operations on Graphs......Page __sk_0020.djvu
1.3 Nonseparable Graphs and Bipartite Graphs......Page __sk_0024.djvu
1.4 Planar Graphs......Page __sk_0028.djvu
1.5 Dual Graphs......Page __sk_0046.djvu
1.6 2-Isomorphism......Page __sk_0058.djvu
1.7 Matrices Associated with a Graph......Page __sk_0062.djvu
1.7.1 Incidence Matrix......Page __sk_0063.djvu
1.7.2 Circuit Matrix......Page __sk_0067.djvu
1.7.3 Cut Matrix......Page __sk_0073.djvu
1.7.4 Interrelationships Among the Matrices A, B_f and Q_f......Page __sk_0080.djvu
1.7.5 Node-to-Datum Path Matrix......Page __sk_0081.djvu
1.8 Directed Graphs......Page __sk_0084.djvu
1.8.1 Matrices Associated with a Directed Graph......Page __sk_0091.djvu
1.8.2 Interrelationships Among the Matrices......Page __sk_0099.djvu
1.8.3 Some Important Classes of Directed Graphs......Page __sk_0101.djvu
1.9 The Circuit Matrix Associated with a Planar Graph or Directed Graph......Page __sk_0103.djvu
1.10 Summary and Suggested Reading......Page __sk_0106.djvu
References......Page __sk_0107.djvu
2 The Shortest Directed Path Problem......Page __sk_0109.djvu
2.1 Shortest Directed Paths......Page __sk_0110.djvu
2.2.1 Dijkstra Algorithm......Page __sk_0113.djvu
2.2.2 Ford-Moore-Bellman Algorithm......Page __sk_0123.djvu
2.2.3 Yen Algorithm......Page __sk_0132.djvu
2.2.4 Ford-Fulkerson Algorithm......Page __sk_0140.djvu
2.3.1 Matrix Algorithm......Page __sk_0149.djvu
2.3.2 Floyd-Warshall Algorithm......Page __sk_0156.djvu
2.4 Enumeration of the Shortest Directed Paths by Decomposition......Page __sk_0163.djvu
2.5 Summary and Suggested Reading......Page __sk_0170.djvu
References......Page __sk_0172.djvu
3.1 Flows......Page __sk_0177.djvu
3.2 s-t Cuts......Page __sk_0180.djvu
3.3 Maximum Flow......Page __sk_0187.djvu
3.4 Ford-Fulkerson Algorithm......Page __sk_0194.djvu
3.4.1 Integrity Theorem......Page __sk_0201.djvu
3.4.2 Irrational Arc Capacities......Page __sk_0202.djvu
3.5 Layered Nets......Page __sk_0207.djvu
3.6 A Blocking Flow Algorithm......Page __sk_0215.djvu
3.7 Variants of the Ford-Fulkerson Algorithm......Page __sk_0225.djvu
3.7.1 Edmonds-Karp Algorithm......Page __sk_0226.djvu
3.7.2 Dinic Algorithm......Page __sk_0230.djvu
3.7.3 Other Variations......Page __sk_0231.djvu
3.8 Karzanov Algorithm......Page __sk_0233.djvu
3.9 Flows in Undirected and Mixed Nets......Page __sk_0239.djvu
3.10 Flows in Node-and-Arc Capacitated Nets......Page __sk_0241.djvu
3.11 Summary and Suggested Reading......Page __sk_0243.djvu
References......Page __sk_0246.djvu
4 Minimum Trees and Communication Nets......Page __sk_0250.djvu
4.1 Forests, Subtrees and Trees......Page __sk_0251.djvu
4.2 Minimum and Maximum Trees......Page __sk_0256.djvu
4.3 Minimum and Maximum Tree Algorithms......Page __sk_0262.djvu
4.3.1 Borůvka Algorithm......Page __sk_0264.djvu
4.3.2 Kruskal Algorithm......Page __sk_0269.djvu
4.3.3 Prim Algorithm......Page __sk_0271.djvu
4.3.4 General Remarks......Page __sk_0275.djvu
4.4 Terminal Capacity Matrix......Page __sk_0276.djvu
4.5 Synthesis of a Flow-Equivalent Tree......Page __sk_0285.djvu
4.5.1 Gomory-Hu Algorithm......Page __sk_0290.djvu
4.5.2 Proof of the Gomory-Hu Algorithm......Page __sk_0300.djvu
4.6 Synthesis of Optimum Undirected Communication Nets......Page __sk_0303.djvu
4.6.1 Gomory-Hu Procedure......Page __sk_0307.djvu
4.6.2 Dominant Flow Realization......Page __sk_0313.djvu
4.7 Oriented Communication Nets......Page __sk_0318.djvu
4.8 Summary and Suggested Reading......Page __sk_0324.djvu
References......Page __sk_0325.djvu
5.1 A Supply-Demand Theorem......Page __sk_0328.djvu
5.2 An Extended Supply-Demand Theorem......Page __sk_0345.djvu
5.3 Circulation Theorem......Page __sk_0355.djvu
5.4 Feasible Circulation Algorithm......Page __sk_0367.djvu
5.5 Flows in Nets with Lower Bounds on Arcs......Page __sk_0376.djvu
5.6 Feasible Flows in Node-and-Arc Capacitated Nets......Page __sk_0382.djvu
5.7 Summary and Suggested Reading......Page __sk_0393.djvu
References......Page __sk_0395.djvu
6.1 The Subgraph Problem of a Directed Graph......Page __sk_0396.djvu
6.2 Digraphic Sequences......Page __sk_0423.djvu
6.3 The Subgraph Problem of a Graph......Page __sk_0442.djvu
6.4 Graphical Sequences......Page __sk_0451.djvu
6.5 The (p, s)-Matrix......Page __sk_0459.djvu
6.6 Realization of the 1-Matrix and the (1, 0)-Matrix......Page __sk_0473.djvu
6.7 Minimal Transformations......Page __sk_0479.djvu
6.8 Summary and Suggested Reading......Page __sk_0490.djvu
References......Page __sk_0492.djvu
Index......Page __sk_0495.djvu