Choose your reading route
eduKateSG · Why Mathematics? · Network Reliability: Two-Terminal Connectivity, Minimal Paths, Cut Sets and Monte Carlo Estimation
Start with the question, audit the worked example, or jump to the assumptions and practice. Every chapter stays open for uninterrupted reading.
Understand the question
Define the quantity and follow the mechanism.Route 2 · Chapters 11–20
Reproduce the example
Audit the numbers one step at a time.Route 3 · Chapters 21–30
Check assumptions
See where design and calibration matter.Route 4 · Chapters 31–40
Explore applications
Connect the method to a concrete investigation.Route 5 · Chapters 41–50
Study and verify
Practise, inspect failure cases and read further.
Full chapter index · Practice and checking · Mathematics Learning Hub
Why is mathematics important in network reliability? A network succeeds when required nodes remain connected through working edges or vertices. That question is about graph structure as well as component probabilities: two-terminal, k-terminal and all-terminal reliability can give different answers for the same network.
This guide develops minimal paths, cut sets, deletion–contraction and Monte Carlo estimation with small checked examples. The examples are fictional. Real transport, communications, power or utility decisions require validated topology, dependence evidence, capacity analysis and competent review.
Full chapter index
Chapters 1–10 · Understand the question
Chapters 11–20 · Reproduce the example
Chapters 21–30 · Check assumptions
Chapters 31–40 · Explore applications
- Validation checks
- Student activity
- Parent guidance
- Common misconception: more paths always mean independence
- Common misconception: the most reliable edge is most important
- Did You Know?
- Practice questions
- FAQ: can ordinary series-parallel formulas solve every network?
- FAQ: does simulation prove the topology is correct?
- Reporting checklist
Chapters 41–50 · Study and verify
CHAPTER 1 OF 50 · Understand the question
1. The reliability question is a connectivity event
Represent sites as vertices and links as edges. A two-terminal question asks whether a path remains between specified source s and destination t. An all-terminal question asks whether every vertex remains connected. A k-terminal question concerns a chosen set. State the criterion before calculating because the same failure state can pass one criterion and fail another.
Some models let only edges fail; others also model nodes. Directed networks require a path that follows direction. Do not turn a directed or node-reliability problem into an undirected edge problem for convenience. Record switches, repeaters and shared conduits that affect connectivity.
Let each edge e work with probability p_e during a stated mission. Under independence, one network state has probability equal to the product of p_e for working edges and 1-p_e for failed edges. Network reliability sums the probabilities of states meeting the connectivity criterion. Independence is a baseline assumption, not a default fact.
Suppose s and t have two edge-disjoint paths. Path A has two series edges, each with reliability 0.9, so its path reliability is 0.81. Path B is one independent edge with reliability 0.8. The probability at least one path works is 1-(1-0.81)(1-0.8)=0.962.
| Path | Reliability |
|---|---|
| Two 0.9 edges in series | 0.81 |
| Direct independent edge | 0.80 |
| At least one path | 0.962 |
The worked complement formula treats the two path events as independent because they use disjoint independent edges. If both paths share an edge, their successes are dependent. Multiplying path-failure probabilities then double counts states. Inspect the topology before applying a parallel formula.
A path set is a set of components whose operation connects the required terminals. It is minimal when removing any member destroys that path. Minimal paths describe success logic, but overlapping paths create dependence even under independent edges. Inclusion–exclusion, decision diagrams or state enumeration can combine them correctly.
A cut set is a set of components whose failure disconnects the required terminals. It is minimal when no proper subset does so. Small-probability cut sets can identify vulnerabilities, but summing cut-set probabilities is generally an approximation when cut events overlap. Keep exact and approximate results labelled.
All-terminal reliability requires the working subgraph to be connected. It is stricter than one source–destination route. A leaf edge becomes critical for including its leaf vertex, while it may be irrelevant to a two-terminal pair elsewhere. Match the metric to the service promise.
A k-terminal model identifies important terminals such as hospitals, depots or controllers and asks whether those nodes remain mutually connected. Nonterminal nodes may fail without immediate loss if alternative routes exist. The chosen terminal set is a policy input and should be reviewed with service owners.
For an edge e with working probability p, reliability can be factored as p times reliability with e contracted plus (1-p) times reliability with e deleted, provided the criterion and model support the operation. Recursion terminates in graphs that are clearly connected or disconnected. Memoisation and graph reductions improve efficiency.
Choose the single direct edge in the two-path example. If it works, s and t are connected, giving conditional reliability 1. If it fails, the two-edge path must work, giving 0.81. Therefore R=0.8×1+0.2×0.81=0.962, matching the complement calculation.
A network with m binary edges has 2^m states. Enumeration is exact for small graphs and excellent for checking algorithms. It becomes expensive quickly. Use symmetry, factoring or decision diagrams, but preserve a small independently enumerated test case for verification.
For all-terminal reliability, every connected working state contains a spanning tree. Counting spanning trees helps describe connectivity, but summing tree probabilities naively double counts states with more than one tree. The matrix-tree theorem counts trees, not the probability of the union of their success events.
With identical independent edge reliability p, network reliability is a polynomial in p. Coefficients reflect how many working-edge subsets of each size meet the criterion. The polynomial supports sensitivity and limiting checks at p=0 and p=1, but heterogeneous probabilities need a multivariate expression or direct computation.
Sample each edge state, test connectivity and record an indicator I equal to one for success. The sample mean estimates reliability. Its standard error is approximately sqrt[R(1-R)/n], estimated with the sample proportion. Report n, seed, interval and connectivity algorithm.
If estimated reliability is 0.96 from 10,000 independent trials, the estimated standard error is sqrt(0.96×0.04/10000), about 0.00196. A rough 95% margin is about 0.0038. This quantifies simulation error only, not topology, probability or dependence uncertainty.
| Quantity | Value |
|---|---|
| Estimated reliability | 0.96 |
| Trials | 10,000 |
| Standard error | about 0.00196 |
| Rough 95% margin | about 0.0038 |
When reliability is extremely high, ordinary simulation may observe no failures. Zero observed failures does not prove zero risk. Importance sampling, splitting, cut-set conditioning or analytical bounds may improve rare-event estimation. Verify weights and compare against exact small cases.
CHAPTER 18 OF 50 · Reproduce the example
18. Capacity is different from connectivity
A connected network may have insufficient bandwidth, flow or voltage support. Connectivity reliability answers whether a path exists, not whether demand is met. Capacity reliability may use maximum flow or performance thresholds. Do not present connectivity as complete service reliability when congestion matters.
The shortest surviving route may be much longer than the normal route. A network can be connected yet exceed time or loss limits. Define weighted path or latency criteria when relevant. Reliability is always reliability of a stated performance event.
Weather, excavation, fire, power and common conduits can fail several edges together. Geographic closeness or shared ownership may signal dependence. Model shared hazards, conditional scenarios or joint probabilities rather than assigning correlation without a mechanism.
Two logical links may follow the same physical duct. Treating them as edge-disjoint exaggerates redundancy. Add a corridor event that disables both or model conditional edge reliabilities given corridor state. The physical map is as important as the logical network diagram.
Mission reliability may treat failures as permanent over a horizon. Operational availability includes repair and restoration. Connectivity then changes over time, and repair crews may share resources. State the clock and whether the result is a snapshot, interval survival or long-run availability.
The reliability block-diagram guide handles series and parallel logic. General networks contain bridge and mesh structures that cannot always be reduced by simple series-parallel rules. Graph algorithms extend the same success-path idea.
Reliability importance measures can rank edges by how much changing their state or reliability affects the network result. Rankings depend on criterion, mission time and other probabilities; they are not permanent properties of an edge.
The multi-state reliability guide treats performance levels. Network links can have several capacities or degraded modes. A connectivity model is the binary foundation, while a flow model carries richer service information.
Give every node and edge a stable identifier, direction, location, capacity, component type and dependency group. Version the topology. A stale or simplified map can dominate statistical precision. Validate the analysis graph against authoritative asset records and actual routing rules.
Use comparable exposure and a clearly defined failure event. Separate scheduled outages, transient errors and complete loss when they have different consequences. Censoring and sparse failures need appropriate methods. Do not infer edge probabilities from network-level incidents without an identifiable model.
Propagate uncertainty in edge probabilities, shared hazards and topology scenarios. A posterior or bootstrap distribution can be sampled through the network solver. Report network intervals and dominant input uncertainties. Monte Carlo trial count is only one layer of uncertainty.
Test removal, addition or reinforcement of candidate edges under the same criterion. A new link can improve connectivity yet introduce a shared corridor or operational burden. Compare benefit with dependence and capacity, and avoid translating model improvement directly into a construction recommendation.
For two terminals, reliability must be zero if s and t are disconnected in the full graph and one if an infallible path exists. Check p=0 and p=1 limits, monotonicity in each edge probability and agreement among enumeration, deletion–contraction and simulation on small graphs.
Compare predicted disconnections and route patterns with drills or incident records. Validate shared-hazard scenarios and restoration logic. A model that matches total outage frequency but predicts the wrong cuts may lead to ineffective interventions.
Draw the two-path network, calculate 0.962 by the complement and deletion–contraction methods, then add one shared edge. Explain why the old multiplication fails. Simulate 1,000 states and compare the estimate with the exact result.
Ask the student to trace every route with a finger and mark any shared link. Which terminals must communicate? Does a path merely exist, or must it carry demand? Encourage a graph, event definition and unit check before probability arithmetic.
CHAPTER 34 OF 50 · Explore applications
34. Common misconception: more paths always mean independence
Alternative paths can share edges, nodes, ducts, power or hazards. More drawn routes may still fail together. Structural diversity and physical independence need evidence. The mathematics makes overlap visible through joint events.
CHAPTER 35 OF 50 · Explore applications
35. Common misconception: the most reliable edge is most important
An almost perfect edge on an irrelevant branch may barely affect the criterion, while a moderately reliable bridge may dominate it. Importance combines structure and probability. Rankings can change when terminals or demand change.
Exact network reliability is computationally difficult for general graphs, even though checking whether one sampled graph is connected is easy. This gap explains why factoring, decision diagrams, bounds and simulation all matter.
Define two-terminal, k-terminal and all-terminal reliability. Reproduce 0.962. Identify minimal paths and cuts. Apply deletion–contraction. Estimate simulation error. Name a shared hazard. Distinguish connectivity from capacity. Propose a validation test.
CHAPTER 38 OF 50 · Explore applications
38. FAQ: can ordinary series-parallel formulas solve every network?
No. They solve reducible structures, but bridge and mesh networks may require factoring, decision diagrams or enumeration. Simplifying a graph is safe only when the transformation preserves the selected connectivity event and dependencies.
CHAPTER 39 OF 50 · Explore applications
39. FAQ: does simulation prove the topology is correct?
No. Simulation estimates the model supplied. Validate node, edge, direction and dependency data separately. Reproducibility and convergence do not establish real-world scope.
State terminals, criterion, node and edge rules, direction, topology version, mission time, component probabilities, dependence, capacity exclusions, exact or simulation method, random seed, intervals, reductions, verification cases, validation evidence and operational limits.
A University of Maryland review covers two-terminal, k-terminal and all-terminal network reliability, including complexity, exact methods, bounds and Monte Carlo. Pair it with authoritative topology and domain standards.
Mathematics matters because connectivity emerges from many overlapping component states. Paths, cuts and factoring reveal structure; simulation estimates large cases; dependence and performance criteria keep the answer honest. A responsible result names the terminals, topology, horizon and uncertainty it actually represents.
A diagram with crossing lines does not necessarily mean links intersect physically. Connectivity follows declared vertices, not the drawing. Geographic networks may add a vertex at a real junction, while communication tunnels can cross without interacting. Clean topology data prevent visual assumptions from changing path and cut calculations.
Protocols can reroute after a failure, so the success criterion includes control convergence and permitted paths. A static graph may overstate service during the transition or miss policy constraints. Model routing rules, convergence time and controller dependencies when they matter. Test sampled failure states against the actual routing engine where practical.
After an outage, crews may repair critical cuts first rather than edges independently. Availability then depends on inspection, travel, spares and scheduling. A connectivity snapshot cannot answer restoration-time questions. Couple the graph to a resource and repair model if service recovery is part of the decision.
Union and cut-set bounds can bracket reliability when exact calculation is costly. A bound is useful only if it is tight enough for the decision. State whether it is an upper or lower bound and verify its direction on a small graph. Never present a bound as an exact probability.
Compare candidate topologies across several plausible edge probabilities and shared-hazard scenarios. A design that wins only under one fragile assumption deserves caution. Report trade-offs in cost, capacity, maintainability and physical diversity rather than naming a universal best network.
Overlay logical edges with routes, flood zones, power feeds and construction corridors. This converts vague correlation into scenario-based dependence. Protect sensitive infrastructure details in public reports while retaining enough internal evidence for review. Geography can change the effective cut sets.
Graph reliability appears in telecommunications, transport, utilities, cloud systems and logistics. Students combine graph theory, probability, algorithms and simulation. Those skills keep education and career options open, while real professional work also needs domain knowledge, standards, communication and ethical judgement.
A student should define the terminal set, find minimal paths and cuts, reproduce an exact small-network calculation and estimate simulation error. A mature solution also identifies shared infrastructure and states why connectivity may be insufficient for capacity or latency.
Extended practice laboratory
Practice case 1: Two paths
Setup: Use a two-edge 0.9 path and one 0.8 direct edge.
Task: Calculate at least one path.
Checking target: Obtain 0.962.
Method note: Draw the sampled or conditioned graph, mark the required terminals and trace the surviving route. Then identify any shared edge, node or hazard. This separates a connectivity proof from an unsupported independence assumption and makes the calculation reproducible.
Reflection: Explain why the checking target follows from the setup, what evidence would be needed outside this illustration, and how a wrong assumption could change the result. Preserve the calculation and final cautious sentence for review.
Practice case 2: Deletion–contraction
Setup: Condition on the direct edge.
Task: Compute 0.8×1+0.2×0.81.
Checking target: Match 0.962.
Method note: Draw the sampled or conditioned graph, mark the required terminals and trace the surviving route. Then identify any shared edge, node or hazard. This separates a connectivity proof from an unsupported independence assumption and makes the calculation reproducible.
Reflection: Explain why the checking target follows from the setup, what evidence would be needed outside this illustration, and how a wrong assumption could change the result. Preserve the calculation and final cautious sentence for review.
Practice case 3: Minimal paths
Setup: List each irreducible s–t path.
Task: Remove one edge from each.
Checking target: Every reduced set fails to connect.
Method note: Draw the sampled or conditioned graph, mark the required terminals and trace the surviving route. Then identify any shared edge, node or hazard. This separates a connectivity proof from an unsupported independence assumption and makes the calculation reproducible.
Reflection: Explain why the checking target follows from the setup, what evidence would be needed outside this illustration, and how a wrong assumption could change the result. Preserve the calculation and final cautious sentence for review.
Practice case 4: Minimal cuts
Setup: Find irreducible disconnection sets.
Task: Check overlap.
Checking target: Do not sum overlapping cut probabilities as exact.
Method note: Draw the sampled or conditioned graph, mark the required terminals and trace the surviving route. Then identify any shared edge, node or hazard. This separates a connectivity proof from an unsupported independence assumption and makes the calculation reproducible.
Reflection: Explain why the checking target follows from the setup, what evidence would be needed outside this illustration, and how a wrong assumption could change the result. Preserve the calculation and final cautious sentence for review.
Practice case 5: Terminal choice
Setup: Compare two-terminal with all-terminal success.
Task: Mark one state that differs.
Checking target: State the service promise.
Method note: Draw the sampled or conditioned graph, mark the required terminals and trace the surviving route. Then identify any shared edge, node or hazard. This separates a connectivity proof from an unsupported independence assumption and makes the calculation reproducible.
Reflection: Explain why the checking target follows from the setup, what evidence would be needed outside this illustration, and how a wrong assumption could change the result. Preserve the calculation and final cautious sentence for review.
Practice case 6: Shared edge
Setup: Make the two routes share one link.
Task: Explain failed independence.
Checking target: Recalculate by states or factoring.
Method note: Draw the sampled or conditioned graph, mark the required terminals and trace the surviving route. Then identify any shared edge, node or hazard. This separates a connectivity proof from an unsupported independence assumption and makes the calculation reproducible.
Reflection: Explain why the checking target follows from the setup, what evidence would be needed outside this illustration, and how a wrong assumption could change the result. Preserve the calculation and final cautious sentence for review.
Practice case 7: Monte Carlo error
Setup: Use estimate 0.96 and n=10,000.
Task: Compute standard error.
Checking target: Obtain about 0.00196.
Method note: Draw the sampled or conditioned graph, mark the required terminals and trace the surviving route. Then identify any shared edge, node or hazard. This separates a connectivity proof from an unsupported independence assumption and makes the calculation reproducible.
Reflection: Explain why the checking target follows from the setup, what evidence would be needed outside this illustration, and how a wrong assumption could change the result. Preserve the calculation and final cautious sentence for review.
Practice case 8: Rare events
Setup: Suppose no disconnects are sampled.
Task: Give an upper-bound or rare-event plan.
Checking target: Zero observations do not prove zero risk.
Method note: Draw the sampled or conditioned graph, mark the required terminals and trace the surviving route. Then identify any shared edge, node or hazard. This separates a connectivity proof from an unsupported independence assumption and makes the calculation reproducible.
Reflection: Explain why the checking target follows from the setup, what evidence would be needed outside this illustration, and how a wrong assumption could change the result. Preserve the calculation and final cautious sentence for review.
Practice case 9: Capacity
Setup: Assign link capacities and demand.
Task: Find a connected but inadequate state.
Checking target: Separate connectivity from service.
Method note: Draw the sampled or conditioned graph, mark the required terminals and trace the surviving route. Then identify any shared edge, node or hazard. This separates a connectivity proof from an unsupported independence assumption and makes the calculation reproducible.
Reflection: Explain why the checking target follows from the setup, what evidence would be needed outside this illustration, and how a wrong assumption could change the result. Preserve the calculation and final cautious sentence for review.
Practice case 10: Common corridor
Setup: Place two links in one duct.
Task: Add a shared hazard.
Checking target: Logical diversity is not physical diversity.
Method note: Draw the sampled or conditioned graph, mark the required terminals and trace the surviving route. Then identify any shared edge, node or hazard. This separates a connectivity proof from an unsupported independence assumption and makes the calculation reproducible.
Reflection: Explain why the checking target follows from the setup, what evidence would be needed outside this illustration, and how a wrong assumption could change the result. Preserve the calculation and final cautious sentence for review.
Practice case 11: Verification
Setup: Enumerate a small graph and compare simulation.
Task: Check p=0, p=1 and monotonicity.
Checking target: All methods agree within simulation error.
Method note: Draw the sampled or conditioned graph, mark the required terminals and trace the surviving route. Then identify any shared edge, node or hazard. This separates a connectivity proof from an unsupported independence assumption and makes the calculation reproducible.
Reflection: Explain why the checking target follows from the setup, what evidence would be needed outside this illustration, and how a wrong assumption could change the result. Preserve the calculation and final cautious sentence for review.
Practice case 12: Conclusion
Setup: State terminals, topology, horizon and dependence.
Task: Name exclusions and uncertainty.
Checking target: Do not imply universal network safety.
Method note: Draw the sampled or conditioned graph, mark the required terminals and trace the surviving route. Then identify any shared edge, node or hazard. This separates a connectivity proof from an unsupported independence assumption and makes the calculation reproducible.
Reflection: Explain why the checking target follows from the setup, what evidence would be needed outside this illustration, and how a wrong assumption could change the result. Preserve the calculation and final cautious sentence for review.