A Random Graph.

Abstract

Let X(1),X(2), ..., X(n) be independent random variables such that P(X(i) = j) = P sub j , j = 1,2, ..., n, sum from j = 1 to n of P sub j = 1 and consider a graph with n nodes numbered 1,2, ..., n and the arcs (i,X(i)), i = 1,2, ..., n. We determine the probability that the above so-called random graph is connected and then develop a recursive formula for the distribution of C, the number of connected components it contains. We also derive expressions for the mean and variance of C. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1979
Accession Number
ADA072513

Entities

People

  • Sheldon M. Ross

Organizations

  • University of California, Berkeley

Tags

DTIC Thesaurus Topics

  • Air Force
  • California
  • Engineering
  • Governments
  • Industrial Engineering
  • Military Research
  • Operations Research
  • Probability
  • Random Variables
  • Scientific Research
  • Security
  • Sequences
  • United States
  • United States Government
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Mathematical Modeling and Probability Theory.