In Engineering theory and applications, we think and operate in terms of logics and models with some acceptable and reasonable assumptions. The present text is aimed at providing modelling and analysis techniques for the evaluation of reliability measures (2-terminal, all-terminal, k-terminal reliability) for systems whose structure can be described in the form of a probabilistic graph. Among the several approaches of network reliability evaluation, the multiple-variable-inversion sum-of-disjoint product approach finds a well-deserved niche as it provides the reliability or unreliability expression in a most efficient and compact manner. However, it does require an efficiently enumerated minimal inputs (minimal path, spanning tree, minimal k-trees, minimal cut, minimal global-cut, minimal k-cut) depending on the desired reliability. The present book covers these two aspects in detail through the descriptions of several algorithms devised by the "reliability fraternity" and explained through solved examples to obtain and evaluate 2-terminal, k-terminal and all-terminal network reliability/unreliability measures and could be its USP. The accompanying web-based supplementary information containing modifiable Matlab(R) source code for the algorithms is another feature of this book.

A very concerted effort has been made to keep the book ideally suitable for first course or even for a novice stepping into the area of network reliability. The mathematical treatment is kept as minimal as possible with an assumption on the readers' side that they have basic knowledge in graph theory, probabilities laws, Boolean laws and set theory.

Sanjay K. Chaturvedi is currently working as an Associate Professor at Reliability Engineering Centre, Indian Institute of Technology, Kharagpur (WB) India. He received his Ph D. degree from Reliability Engineering Centre, IIT Kharagpur (India) in year 2003. He holds a Bachelor's degree in electrical engineering and Master's degree in system engineering and operations research, both from Indian Institute of Technology, Roorkee. He has research interests in the areas of reliability modeling and analysis, network reliability, life-data analysis, maintenance and optimization, and has done several consultancy projects, and delivered lectures in Indian industries in these areas. He has guided several Ph.Ds. and published papers in several international journals.

Preface xiii

Acknowledgements xvii

1 Introduction 1

1.1 Graph Theory: A Tool for Reliability Evaluation 2

1.1.1 Undirected Networks 4

1.1.2 Directed Networks 4

1.1.3 Mixed Networks 5

1.2 Large versus Complex System 7

1.2.1 Large System 7

1.2.2 Complex System 7

1.2.3 Large and Complex System 9

1.3 Network Reliability Measures: Deterministic versus Probabilistic 9

1.3.1 Terminal-pair Reliability Measure 11

1.3.2 All-Terminal Reliability Measure 12

1.3.3 k-terminal Reliability Measure 12

1.4 Common Assumptions 12

1.5 Approaches for NSP Network Reliability Evaluation 13

1.5.1 Non Path or Cut Sets Based Techniques 14

1.5.1.1 State Enumeration Technique 14

1.5.1.2 Network Decomposition Technique 18

1.5.1.3 Probability Transformation Technique 19

1.5.1.4 Binary Decision Diagram Based Technique 20

1.5.2 Minimal POC Based Techniques 21

1.5.2.1 Inclusion-Exclusion Technique 21

1.5.2.2 Monte-Carlo Simulation Based Technique 22

1.5.2.3 Domination Theory Based Technique 23

1.5.2.4 Reliability Bounds Technique 24

1.5.2.5 Sum-of-disjoint Product Based Technique 25

Exercises 26

References 27

2 Reliability Evaluation of General SP-Networks 31

2.1 Notation and Assumptions 33

2.2 Unit-Reliability and Failure Models 34

2.2.1 Constant-Hazard Model 35

2.2.2 Linear-Hazard Model 35

2.2.3 Weibull-Hazard Model 35

2.2.4 Extreme Value-Hazard Model 36

2.3 Module Representation of Reliability Graphs 36

2.3.1 Single-Unit Module 36

2.3.2 Multi-Unit Module 36

2.3.2.1 Series Model 37

2.3.2.2 Parallel Model 38

2.3.2.3 Standby Model 39

2.3.2.4 k-out-of-m Model 41

2.4 Misra Matrix Method 44

2.5 Algorithm 45

2.6 Implementation and Documentation 55

2.6.1 Main Module 55

2.6.2 Function formCmat 56

2.6.3 Function processCmat 58

2.6.4 Function systDetail 58

2.7 Remarks 58

Exercises 59

References 60

3 Path Sets Enumeration 63

3.1 Enumeration of (s, f) Connected Path Sets 64

3.1.1 Method 1: Using Powers of Connection matrix 65

3.1.2 Method 2: Traversing Through Connection Matrix 67

3.1.3 Method 3: Using Incidence Matrix 69

3.2 Enumeration of All-node Connected Path Sets: Spanning Tree 73

3.2.1 Method 1: Using the Cartesian Product of the Node Cut Sets 74

3.2.2 Method 2: Using the Incidence Matrix 75

3.3 Number of Spanning Trees 84

3.3.1 Matrix Tree Theorem 84

3.4 Enumeration of k-node Connected Path Sets: k-Trees 86

Appendix 3A.1: Enumeration of Path Sets Algorithm, Illustration and Matlab® Code Notation 88

Appendix 3A.2: Sample program I/O for Figure 3A.1 Contents ix 97

Exercises 100

References 101

4 Cut Sets Enumeration 103

4.1 (s, f) Cut Sets Enumeration 104

4.1.1 Method 1: Using Connection Matrix 104

4.1.2 Method 2: Using Minimal Path Sets 106

4.1.2.1 Using Set-theoretic Product of Path Sets 106

4.1.2.2 Using Path Sets Matrix 107

4.1.2.3 Using Path Sets Inversion 108

4.2 Global Cut Sets Enumeration 109

4.2.1 Testing Connectivity of a Specified Node Set 110

4.2.1.1 Node Fusion Technique 110

4.2.2 Generation of Node Set Combination from its Lower Order Node-Sets 112

4.2.3 Checking Validity of a Node Set 112

4.2.4 Formation of Cutset 113

4.2.5 General Algorithm to Enumerate Minimal Cutsets for a Reliability Measure 113

Appendix 4A.1: Node Fusion Technique and Generation of Node Set Combination 123

Appendix 4A.2: Code for Checking Validity of a Node Set and Converting Node-Sets into Link Cutsets 124

Appendix 4A.3: Sample Program I/O for Network Graph of Figure 4.3 126

Appendix 4A.4: g-Terminal Reliability Evaluation

Program Sample I/O for Example of Figure 4.3 128

Appendix 4A.5: Results are provided by the program (output of g-reliability expression for the Figure 4.3

for method HM-1 of (Chaturvedi & Misra, 2002). 129

Exercises 130

References 131

5 Reliability Evaluation using MVI Techniques 133

5.1 Notation and Assumptions 134

5.2 Preliminaries 135

5.2.1 Definitions 135

5.3 MVI Methods 137

5.3.1 Method 1: KDH88 137

5.3.2 Method 2: CAREL 139

5.3.3 Comparison between KDH88 and CAREL 144

5.4 Method 3: Hybrid Methods-HM 147

5.4.1 An Alternative Representation of Path or Cut Sets 147

5.4.2 Hybrid Methods (HM) 149

5.4.2.1 HM-1 149

5.4.2.2 HM-2 149

5.5 Applying HM-1 and HM-2 149

5.5.1 Applying HM-1 150

5.5.2 Applying HM-2 151

5.5.3 Complete Solution to Example 5.2 152

5.6 Global and k-terminal Reliability with SDP Approach 159

5.6.1 All-terminal Reliability Evaluation 161

5.6.2 Characteristics of a g-reliability Expression 164

5.6.3 k-terminal Reliability Evaluation 164

5.6.4 Number of k-trees 167

5.7 Unreliability with SDP Approach 169

5.8 Some Suggested Guidelines 171

5.8.1 Directed Network Graph 171

5.8.2 Undirected Network Graph 172

Appendix 5A.1: Program output of g-reliability expression for the Figure 5.1(b). 173

Appendix 5A.2: Program output of k-terminal reliability expression for Figure 5.1(b). 179

Appendix 5A.3: Program output of k-terminal reliability expression for Figure 5.1(b). 181

Exercises 183

References 185

6 Unified Framework and Capacitated Network Reliability 187

6.1 The Unified Framework 188

6.2 Capacitated Reliability Measure: An Introduction 189

6.2.1 Some Related Definitions 191

6.2.1.1 Minimal Cutset and Subset Cut Group 191

6.2.1.2 External Redundant Subset Cut Group 191

6.2.1.3 Internal Redundant Subset Cut Group 192

6.2.1.4 Invalid Cut Set Cut Group 192

6.2.1.5 Description of the Algorithm 192

6.3 Algorithm Description 192

6.3.1 Equations: The idea 193

6.3.2 Is Cut itself a SCG or does it need its Subsets Enumeration? 194

6.3.3 What Initial Order? 194

6.3.4 Efficient enumeration of particular order SCG of a minimal cut 197

6.3.5 External or Both External/ Internal Redundancy Removal 197

6.3.6 Internal Redundancy Removal 199

6.4 The CRR Evaluation Algorithm 200

6.5 A Complete Example 202

6.6 Experimental Results, Comparison and Discussion 207

References 212

7 A LAN and Water Distribution Network: Case Studies 213

7.1 Case Study-I: IIT Kharagpur LAN Network 213

7.1.1 k-Terminal and global reliability evaluation for hostel area of IIT Kharagpur LAN 215

7.1.2 All terminal reliability evaluation for academic area of LAN 215

7.1.3 All terminal reliability evaluation for IIT Kharagpur LAN network 215

7.2 Case Study-II: Real-Type of Large Size Unsaturated Water Distribution Networks 219

References 222

Epilogue 223

References 225

Bibliography 227

Index 235