网络理论及其应用
2003-12
Imperial College Press
Chen, Wai-Kai
660
Electrical, communication, transportation, computer, and neural networks are special kinds of nets. Designing these networks demands sophisticated mathematical models for their analysis. This book is the first to present a unified, comprehensive, and up-to-date treatment of net theory. It brings together elements of abstract graph theory and circuit analysis to network problems.
Preface1 Graphs and Networks 1.1 Basic Definitions of Abstract Graphs 1.2 Operations on Graphs 1.3 Nonseparable Graphs and Bipartite Graphs 1.4 Planar Graphs 1.5 Dual Graphs 1.6 2-Isomorphism 1.7 Matrices Associated with a Graph 1.7.1 Incidence Matrix 1.7.2 Circuit Matrix 1.7.3 Cut Matrix 1.7.4 Interrelationships Among the Matrices A Bf and Qf 1.7.5 Node-to-Datum Path Matrix 1.8 Directed Graphs 1.8.1 Matrices Associated with a Directed Graph 1.8.2 Interrelationships Among the Matrices 1.8.3 Some Important Classes of Directed Graphs 1.9 The Circuit Matrix Associated with a Planar Graph or Directed Graph 1.10 Summary and Suggested Reading References2 The Shortest Directed Path Problem 2.1 Shortest Directed Paths 2.2 Shortest Directed Path Algorithms 2.2.1 Dijkstra Algorithm 2.2.2 Ford-Moore-Bellman Algorithm 2.2.3 Yen Algorithm 2.2.4 Ford-Fulkerson Algorithm 2.3 Multiterminal Shortest Directed Paths 2.3.1 Matrix Algorithm 2.3.2 Floyd-Warshall Algorithm 2.4 Enumeration of the Shortest Directed Paths by Decomposition 2.5 Summary and Suggested Reading References3 Maximum Flows in Networks 3.1 Flows 3.2 s-t Cuts 3.3 Maximum Flow 3.4 Ford-Fulkerson Algorithm 3.4.1 Integrity Theorem 3.4.2 Irrational Arc Capacities 3.5 Layered Nets 3.6 A Blocking Flow Algorithm 3.7 Variants of the Ford-Fulkerson Algorithm 3.7.1 Edmonds-Karp Algorithm 3.7.2 Dinic Algorithm 3.7.3 Other Variations 3.8 Karzanov Algorithm 3.9 Flows in Undirected and Mixed Nets 3.10 Flows in Node-and-Arc Capacitated Nets 3.11 Summary and Suggested Reading References4 Minimum Trees and Communication Nets 4.1 Forests Subtrees and Trees 4.2 Minimum and Maximum Trees 4.3 Minimum and Maximum Tree Algorithms 4.3.1 Borfivka Algorithm 4.3.2 Kruskal Algorithm 4.3.3 Prim Algorithm 4.3.4 General Remarks 4.4 Terminal Capacity Matrix ……5 Feasibility Theorems and Their Applications 6 Applecations of Flow Theorems to Subgraph Problems7 Signal-Flow Graphs8 Other Net ApplicationsIndex
