Estimation for a Graph Theory problem

  • Thread starter chingkui
  • Start date
  • #1
chingkui
193
2
I am thinking about this problem that come up in some of my work, I think this has been solved before, though I am not aware where I could find the solution. Here is the question:
Suppose a graph has say 20 nodes with no edge initially, and at each instance, 4 (different) nodes are randomly drawn with equal probability and all 6 edges among them are added to the graph. How do I estimate the expected number of iterations before the graph become connected (just connected, no need to be completed)? Thanks.
 

Answers and Replies

  • #2
Zula110100100
253
0
I feel that I should include I am not an expert by any means, but here is how I would approach it.

So all you really need is the 20 nodes and 4 picked each time right, I think the graph will be connected once every node is picked once regardless of the extra 2 edges they don't matter, I don't know the answer, but I think the question could be asked "Picking 4 at a time, how long does it take for all 20 to be picked at random?" I guess one answer is that the number of rounds lies in the interval [5,∞).
The chance goes up with every round, with a minimal chance of 5!/(5^5) = 3.84%

for the 5 rounds to work, you have to get unpicked nodes every round and you'd have a first round with a 20/20 chance of getting an unpicked node, second round, 16/20 chance of getting an unpicked node,3rd 12/20 and so on, which reduces to 5/5,4/5,3/5,2/5,1/5, from which you get the above. How you would figure the chances if it didn't go perfect I am not sure of, sorry.
 
  • #3
Zula110100100
253
0
And actually that is bad, each round would break into the 4 individual draws? So you'd have 1*16/20*15/19*14/18*13/17*12/20*11/19...

so: [itex] \frac{20!}{(20^5)(19^5)(18^5)(17^5)} =\frac{20!}{(\frac{20!}{16!})^5} = .000000114 = .0000114% [/itex]% chance as a minimum?
 
Last edited:

Suggested for: Estimation for a Graph Theory problem

Replies
1
Views
161
Replies
1
Views
394
  • Last Post
Replies
2
Views
185
  • Last Post
Replies
5
Views
494
  • Last Post
Replies
0
Views
736
Replies
6
Views
703
  • Last Post
Replies
9
Views
928
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
8
Views
529
Replies
13
Views
412
Top