Graph Theory in Modern Engineering: Computer Aided Design, Control, Optimization, Reliability Analysis (eBook)

Front Cover 1
Graph Theory in Modern Engineering 4
Copyright Page 5
Contents 6
Preface 10
Acknowledgments 13
Nomenclature 14
Chapter 1. Basic Concepts 18
Directed Graphs 18
Flow Graphs for Differential Equations 21
Further Terminology 23
Chapter 2. Construction and Analysis of Signal Flow Graphs 24
Signal-Flow-Graph Reduction and the Solution of Equations 26
Flow-Graph Algebra 27
Loop Elimination and Equation Solving by Equation Reduction 29
Mason’s Rule 32
Applying Mason’s Rule 33
Application of Mason’s Rule to Dynamic Systems 36
References 38
Chapter 3. Systematic Analysis of Large Flow Graphs 40
Determining Specific Paths and Loops 41
Determining Specific Paths 48
List Processing Approach to Determining Paths 50
Evaluation of Gains 52
Removing Unnecessary Paths from the List Structure 53
Evaluating Determinants in Mason’s Formula 54
Computing the Determinants Corresponding to Specific Paths as Required by Mason’s Rule 57
Computing Transmittances 57
Implementing the Algorithms 58
References 60
Chapter 4. Frequency Response Analysis 62
Final Value Theorem 62
Initial Value Theorem 63
Substitution Rule 64
Bode Diagrams 65
A Typical Application 67
Other Stability Criteria 68
Reference 69
Chapter 5. Sensitivity Analysis 70
Sensitivity Analysis in General 70
Derivation of Network Functions 73
Deriving Sensitivity Functions 76
Applying Sensitivity Functions to Structural Analysis 77
Gain and Phase Sensitivity 80
Pole and Zero Sensitivity 81
Sensitivities via Structural Methods 82
Sensitivities for Large Parameter Variations 85
Transfer Functions and Sensitivities in Static Systems 85
References 86
Chapter 6. Examples and Further Applications 88
Closed-Form Solution of an Absorption Column 95
Sensitivity Analysis of a Heat Exchanger Network 95
Continuous Stirred Tank Reactor 100
Eigenvalue Problems 117
Ordering Recycle Calculations 119
Transportation Problems 122
References 124
Chapter 7. Linear and Nonlinear Programming 126
General Form of LP Problems 129
Simplex Solution by Signal-Flow-Graph Methods 129
Example Problems 130
Discussion of Solution Procedure (MASNLP) 135
An Advantage of MASNLP 135
Dual Simplex Method 137
Postoptimal Analysis 138
Sensitivity Analysis 139
Nonlinear Systems 139
Method of Feasible Directions 142
A Heat Exchanger Problem 148
Solution to the Heat Exchanger System 150
Results and Discussion 156
References 165
Chapter 8. Ranking by Flow-Graph Methods 166
Tennis Rankings 167
Implementation Difficulties 170
A Solution to the Implementation Problem 175
Reference 176
Chapter 9. Undirected Graphs 178
Undirected Graphs 178
Trees 179
Logic Trees 180
Branch and Bound Methods 184
Trees-Further Theorems and Definitions 186
Disconnecting Sets and Cut-Sets 188
Bipartite Graphs 188
Assigning Output Sets 190
References 191
Chapter 10. Matrix Representation of Graphs 192
Nondirected Graphs 194
Digraphs 196
References 205
Chapter 11. Branch and Eound. Search Tree Methods 206
Formal Definition of the Branch and Bound Technique 207
The Traveling Salesman Problem 209
Integer Programming and Pseudo-Boolean Progrhmming 222
Generalization of the Branch and Bound Method 226
Bidding Contest Problem 226
Conclusion 237
References 238
Chapter 12. Process Reliability Analysis by Flow-Graph Methods 240
Module Representation of Reliability Graphs 241
Principle of Path Enumeration and Sensitivity Calculation Methods 243
Basic Algorithm 245
Path Finding Algorithm 246
System Reliability 247
Comparison with State Enumeration Algorithm 248
Examples 252
Extension to System MTBF Calculation 259
Conclusions 260
References 261
Appendix A. Matrix Theory 262
Appendix B. Linearization of Equations 270
Appendix C. Derivation of Mason’s Rule 274
Appendix D. Boolean and Modulo-2 Algebra 282
Appendix E. Linear Programming 286
Appendix F. The Coates Flow Graph 294
Appendix G. The Fibonacci Search Method 298
Appendix H. Glossary of Graph Nomenclature 302
Appendix I. Computer Programs for Chapters 1-6 306
Appendix J. Computer Programs for Chapter 7 310
BIBLIOGRAPHY 312
INDEX 314