Connectivity in probabilistic graphs
Irwin M. Jacobs · 1960
ments for the degree of Doctor of Science. A probabilistic graph is a linear graph in which both nodes and links are subject to random erasure. Such a graph may be thought of as an idealized model of a communi-cation network in which switching centers (nodes) and information channels (links) either operate perfectly or fail entirely. This report deals with the reliability of the communi-cation network. Two reliability criteria are established. The first is the probability that a path exists between all pairs of nodes that remain in the associated probabilistic graph after erasure, and the second is the probability that a path exists between one pair of nodes selected at random. For small communication networks, the interesting questions concern analysis-the calculation of the reliability of a given network- and synthesis- the construction, under certain constraints, of graphs with maximum reliability. For large communica-tion networks, the emphasis is on the link-to-node densities necessary and sufficient for attaining a desired reliability. The sufficient densities are determined by approxi-