Circuits as Two-Terminal Graphs
A circuit made from components that either work or fail can be studied by asking whether current has a route from a source terminal to a destination terminal. The graph model makes this a question about paths and edge failures. A path describes a set of components that can carry a connection; a cut set describes a combination of failed components that blocks every such path.
Unless stated otherwise, graphs in this tutorial are finite and simple. We use an undirected graph: an edge represents a component that conducts between its two endpoints when it works. The model assumes ideal binary states (working or failed), no component failures at vertices, and no additional electrical effects such as shorts or changes in current caused by resistance. Thus it answers a connectivity question, not every question about physical circuit behavior.
For a set \(F\subseteq E\), write \(G-F\) for the graph obtained by deleting the edges in \(F\), while retaining all vertices. We assume the intact network has at least one \(s\)-\(t\) path; otherwise it is already disabled, even with no component failures. An \(s\)-\(t\) edge cut set is a set \(F\subseteq E\) for which \(G-F\) has no \(s\)-\(t\) path. It is minimal if no proper subset of \(F\) is an \(s\)-\(t\) edge cut set. Minimal means inclusion-minimal, not necessarily smallest in size.
Paths and Cut Sets Describe Opposite Conditions
Proof. Suppose first that \(F\) contains an edge of every intact \(s\)-\(t\) path. If an \(s\)-\(t\) path remained in \(G-F\), it would also be an intact \(s\)-\(t\) path and would contain no edge of \(F\), contradicting the assumption. Therefore \(G-F\) has no \(s\)-\(t\) path. Conversely, suppose \(F\) does not contain an edge of some intact \(s\)-\(t\) path \(P\). Every edge of \(P\) remains in \(G-F\), so \(P\) is still an operating path and \(F\) does not disable the network. These two implications prove the equivalence. \(\square\)
This gives a direct way to search for cut sets: list the operating paths, then find edge sets that meet every path. Minimality asks for the smallest such sets under inclusion. There is also a useful test for minimality that does not require comparing \(F\) with every one of its subsets.
Proof. Suppose \(F\) is minimal and choose \(e\in F\). The set \(F\setminus\{e\}\) is a proper subset of \(F\), so minimality says it is not an edge cut set. By the definition of an edge cut set, \(G-(F\setminus\{e\})\) therefore has an \(s\)-\(t\) path. Conversely, suppose restoring each single edge as described produces a path. If some proper subset \(F'\subsetneq F\) were an edge cut set, choose \(e\in F\setminus F'\). Since \(F'\subseteq F\setminus\{e\}\), deleting \(F'\) removes no more edges than deleting \(F\setminus\{e\}\). The path that exists in \(G-(F\setminus\{e\})\) would still exist in \(G-F'\), contradicting that \(F'\) is a cut set. Hence \(F\) is minimal. \(\square\)
Finding Minimal Cut Sets
Worked Example: Two Separate Routes
Let \(V=\{s,a,b,t\}\) and \(E=\{sa,at,sb,bt\}\). The source is \(s\) and the terminal is \(t\). This network has two \(s\)-\(t\) paths: \(P_1=(s,a,t)\), with edge set \(\{sa,at\}\), and \(P_2=(s,b,t)\), with edge set \(\{sb,bt\}\). There are no other \(s\)-\(t\) paths because the only edges incident with \(a\) are \(sa,at\), and the only edges incident with \(b\) are \(sb,bt\).
A cut set must meet both paths. To be minimal, it must choose one edge from \(P_1\) and one from \(P_2\): choosing neither edge from either path leaves that path intact, while choosing both edges from one path makes one of those failures unnecessary. The four minimal cut sets are therefore \(\{sa,sb\}\), \(\{sa,bt\}\), \(\{at,sb\}\), and \(\{at,bt\}\).
For instance, \(F=\{sa,bt\}\) meets \(P_1\) at \(sa\) and \(P_2\) at \(bt\), so it disables the network. If \(sa\) is restored, the path \(s,a,t\) works. If \(bt\) is restored, the path \(s,b,t\) works. The minimality proposition confirms that \(F\) is minimal.
Check: \(G-F\) has only the edges \(at\) and \(sb\). Neither connects \(s\) to \(t\), so the network is disabled. Restoring either failed edge gives one of the two paths listed above.
Worked Example: A Shared Component and Six Minimal Cut Sets
Let \(V=\{s,a,b,c,t\}\) and \(E=\{sa,at,ac,ct,sb,bt\}\), with source \(s\) and terminal \(t\). The complete list of \(s\)-\(t\) paths is \(P_1=(s,a,t)\), \(P_2=(s,a,c,t)\), and \(P_3=(s,b,t)\). Indeed, after entering the \(a,c\) part, the only way to reach \(t\) is through \(at\) or \(ct\); the \(b\) part connects to the rest only through \(sb\) and \(bt\).
To hit both \(P_1\) and \(P_2\), a minimal choice is either the shared edge \(sa\), or one edge from each of \(\{at\}\) and \(\{ac,ct\}\). Thus the minimal choices for those two paths are \(\{sa\}\), \(\{at,ac\}\), and \(\{at,ct\}\). The remaining path \(P_3\) must be hit by \(sb\) or \(bt\). Combining one choice for \(P_1,P_2\) with one for \(P_3\) gives six minimal cut sets:
- \(\{sa,sb\}\) and \(\{sa,bt\}\);
- \(\{at,ac,sb\}\) and \(\{at,ac,bt\}\);
- \(\{at,ct,sb\}\) and \(\{at,ct,bt\}\).
For example, consider \(F=\{at,ac,sb\}\). It meets \(P_1\) at \(at\), \(P_2\) at both \(at\) and \(ac\), and \(P_3\) at \(sb\). Restoring \(at\) gives \(s,a,t\); restoring \(ac\) gives \(s,a,c,t\); restoring \(sb\) gives \(s,b,t\). So each failed edge is necessary, and \(F\) is minimal. The same path-hitting argument proves the listed sets are cut sets; the construction uses minimal choices for each required path group, so deleting any edge from any listed set leaves at least one of the three paths unhit.
Check: The six sets have sizes \(2,2,3,3,3,3\), respectively. Their differing sizes illustrate why “minimal cut set” does not mean “cut set of minimum cardinality.” Each set is minimal under inclusion because restoring any one of its edges permits an operating path.
Using Cut Sets in Reliability Calculations
Paths and cut sets describe which combinations of component states work or fail. To calculate a probability of operation, an additional probability model is needed. In the following examples, component states are independent, and each stated probability is the probability that the component works. Independence is essential to multiplying probabilities of specified combinations.
Worked Example: Reliability of Two Parallel Routes
Use the graph from the first example. Suppose each of its four edges works independently with probability \(0.9\). One route works only if both its edges work, so the probability that \(P_1\) works is \(0.9\cdot0.9=0.81\); the probability that it fails is \(1-0.81=0.19\). The same calculations give probability \(0.81\) that \(P_2\) works and \(0.19\) that it fails.
The edge sets of the two paths are disjoint, so their success or failure events are independent. The whole network fails precisely when both paths fail. Consequently, its failure probability is \(0.19\cdot0.19=0.0361\), and its reliability (the probability it operates) is \(1-0.0361=0.9639\).
Check: The failure of each two-edge route has probability \(1-0.9^2=1-0.81=0.19\). Both routes fail with probability \(0.19^2=0.0361\), so the operating probability is \(1-0.0361=0.9639\), as calculated.
Worked Example: A Shared Component in Series with Parallel Routes
Let \(V=\{s,a,b,c,t\}\) and \(E=\{sa,ab,bt,ac,ct\}\), with terminals \(s,t\). The paths are \(P_1=(s,a,b,t)\) and \(P_2=(s,a,c,t)\). They share the component \(sa\). The minimal cut sets are \(\{sa\}\), together with the four sets obtained by choosing one edge from each of \(\{ab,bt\}\) and \(\{ac,ct\}\): \(\{ab,ac\}\), \(\{ab,ct\}\), \(\{bt,ac\}\), and \(\{bt,ct\}\). The first set alone disables both paths; otherwise one edge from each route beyond \(a\) must fail.
Suppose the independent edge-working probabilities are \(p_{sa}=0.9\), \(p_{ab}=0.8\), \(p_{bt}=0.95\), \(p_{ac}=0.7\), and \(p_{ct}=0.9\). The probability that the \(b\)-route from \(a\) to \(t\) works is \(0.8\cdot0.95=0.76\), so its failure probability is \(1-0.76=0.24\). The probability that the \(c\)-route works is \(0.7\cdot0.9=0.63\), so its failure probability is \(1-0.63=0.37\). These two routes use disjoint edges; both fail with probability \(0.24\cdot0.37=0.0888\). Therefore, after \(sa\) works, at least one route works with probability \(1-0.0888=0.9112\). The total reliability is \(0.9\cdot0.9112=0.82008\).
Check: Failure occurs either because \(sa\) fails, with probability \(1-0.9=0.1\), or because it works and both following routes fail, with probability \(0.9\cdot0.0888=0.07992\). The total failure probability is \(0.1+0.07992=0.17992\), giving reliability \(1-0.17992=0.82008\), which agrees.
A Common Counting Pitfall
Do not add the probabilities of minimal cut sets as if their events were disjoint. In the two-route example with four edge-working probabilities \(0.9\), each minimal cut set consists of two failed edges and therefore has probability \(0.1\cdot0.1=0.01\). Adding the four probabilities gives \(4\cdot0.01=0.04\). That is not the network’s failure probability, which is \(0.0361\): some failure configurations belong to more than one minimal-cut-set event.
To see the correction directly, write \(A\) for the event that the first route fails and \(B\) for the event that the second route fails. Each has probability \(0.19\), and the events are independent because the routes use distinct edges. The network fails on \(A\cap B\), whose probability is \(0.19\cdot0.19=0.0361\). Minimal cut sets are valuable descriptions of ways failure can occur, but their events need not form a disjoint partition of all failure outcomes.
The graph method separates two tasks. First, determine which paths provide operation and which component sets block them; these are structural questions. Then, if probabilities are supplied, combine the component-state probabilities using the stated dependence assumptions. Listing cut sets without checking their minimality, or treating overlapping failure scenarios as disjoint, can give an incorrect reliability conclusion.
Check Your Understanding
For each question, specify the terminals and use the path and cut-set definitions rather than relying on a drawing.
- In the graph \(V=\{s,a,b,t\}\), \(E=\{sa,at,sb,bt\}\), why does \(\{sa,at,sb\}\) disable the network but fail to be a minimal cut set?
- For the same graph, list the minimal cut sets and explain why a one-edge failure cannot disable it.
- State the two implications in the path-cut theorem: what does meeting every path imply, and what does the existence of a path avoiding the failure set imply?
- In the shared-component example, explain why \(\{sa\}\) is a minimal cut set even though it has fewer edges than the other minimal cut sets.
- For two independent routes, each of which works with probability \(0.8\), and with disjoint component sets, calculate the probability that both routes fail. State why independence is applicable.