CODEWITHSUNDEEP
pythonalgorithmgraph
anupam
anupam

Reputation: 91

"Connectedness" In Randomly Generated Graphs

For past 3-4 days I have been playing with implementing graphs, and associated structures in python. among other things, i have a trivial function to generate random-graphs i.e. graphs in which two vertices are connected with a given probability. the graphs are then displayed using graphviz.

anyways, during the course of above activity, i noticed that above certain probability almost all graphs with a given number of vertices are always connected. couple of questions:

Upvotes: 2

Views: 349

Answers (1)

Aryabhatta
Aryabhatta

Reputation:

Good question!

In fact, the subject of random graphs is well known and dates back to Erdos and Renyi, 1959.

The observation of threshold is also excellent. There are other properties of graphs which share this "threshold" phenomena.

In fact, it has been proven that most "monotone" properties share this "threshold" property. This was proven by Erdös and Rényi (according the the book mentioned below).

A property P is monotone if a graph H on n vertices has P implies any supergraph G (on n vertices) of H (i.e H is a subgraph of G) also has P. For example, Hamiltonian Cycle is one such property. Connectedness is another.

Note: This definition of monotonicity might differ from other texts on graph-theory. I am mentioning the one provided in the book below.

The book Random Graphs by Béla Bollobás should get you started. See page 40 for a discussion about the monotone properties having a "threshold". I must warn you though, that book uses some pretty heavy mathematics.

Upvotes: 5

Related Questions