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 2n-2, whereas the number of path sets is of the order of 2l-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 ...

Get Network Reliability now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.