Connectivity of finite anisotropic random graphs and directed graphs (Q3742403)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3978020
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Connectivity of finite anisotropic random graphs and directed graphs |
scientific article; zbMATH DE number 3978020 |
Statements
Connectivity of finite anisotropic random graphs and directed graphs (English)
0 references
1986
0 references
graphs on a finite set of vertices
0 references
Recursive formulas for computing the reliability
0 references
random graphs
0 references
reliability and redundancy
0 references
0 references
0 references
0 references
0.7847246527671814
0 references
0.7806015610694885
0 references
For graphs on a finite set of vertices with arbitrary probabilities of independently occurring edges, the reliability is defined as the probability that the graph is connected, and the redundancy as the expected number of spanning trees of the graph. Analogous measures of connectivity are defined for random finite directed graphs with arbitrary probabilities of independently occurring directed edges. Recursive formulas for computing the reliability are known. Determinantal formulas, based on matrix-tree theorems, for computing the redundancy are given here. Among random graphs with a given sum of edge probabilities, the more evenly the probabilities are distributed over potential edges, the larger the redundancy. This inequality, proved using the theory of majorization, in combination with examples shows unexpectedly that conflicts between reliability and redundancy can arise in the design of communication networks modelled by such random graphs. The significance of these calculations for the command and control of nuclear forces is sketched.
0 references