Premium
Combinatorial properties of directed graphs useful in computing network reliability
Author(s) -
Satyanarayana A.,
Hagstrom Jane N.
Publication year - 1981
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230110405
Subject(s) - combinatorics , induced subgraph isomorphism problem , mathematics , spanning tree , discrete mathematics , probabilistic logic , vertex (graph theory) , induced subgraph , graph , line graph , voltage graph , statistics
This paper is concerned with the problem of computing the probability that a root vertex can communicate with all other vertices in a probabilistic directed graph. One method is to apply the inclusion‐exclusion principle of probability theory to the event “at least one rooted spanning tree of the graph is working.” We prove combinatorial properties of graphs which allow us to derive a much condensed form of the inclusion‐exclusion expression. Each term corresponds to an acyclic spanning subgraph of the original graph, with coefficient equal to (−1) b ‐ n +1 , where b and n are the number of edges and vertices of the subgraph, respectively.