Network Reliability

Chapter 4

Cut Sets Enumeration

A cut set is a set of links (branches), which literally cuts the success path by severing all the possible lines of communication between the transmitting and receiving terminals. A minimal cut set of a network graph G is a set of links, whose removal or non-functioning ensures the network dis-connectivity for a specified set of nodes provide removal of no proper subset of these links disconnects G. The number of path sets or cut sets in any general network depends to a large extent on the topology of the network and it would be advantageous to work with path sets or cut sets, whichever has its number less. In most of the practical systems, particularly in highly redundant and well-connected networks, the number of cut sets is usually much less than the number of path sets and it may be advantageous to work with cut sets rather than path sets in such cases.

An advance estimate of the number of path sets or cut sets helps determine the approach that one may use eventually to evaluate reliability of a given network graph. One such estimate was provided by (Aggarwal, Chopra, & Wajwa, 1982), which suggests that relatively for a network of n nodes and l links, the number of cut sets between any pair of nodes would be of the order of 2^n-2, whereas the number of path sets is of the order of 2^l-n+2. Note that the estimation for other types of minimal cuts (global or k-minimal) is not known. Besides, if average degree of nodes in a given network graph is more ...