1. I have created a 500 nodes in a graph, and assigned 3 edges(directed) for each node to any other nodes excluding itself. (no self loop)

  2. I randomly pick half of the nodes, and mark them as fail. (250 nodes are alive, and the other 250 nodes are marked as fail)

  3. I randomly pick a node that is alive, and traverse using its edges. (3 edges for each node)

The traversing algorithm looks like below, and it will be initiated with any alive node.

public void traverse(Node p){
    if(p.fail||p.visited){ //if node is marked as fail or has been visited already, return
    p.visited = true;      //mark it as visited
    for(int i = 0;i<p.edges.size();i++){  //p.edges.size() == 3 in this case
        traverse(p.edges.get(i).end); //traverse to all edges

What should be the average percentage that this operation end up traversing all the alive nodes? (start from random node, and see if graph is connected or not in the node's viewpoint)

  • $\begingroup$ Apparently, I am getting failure(graph is not connected) almost 100% of the times. $\endgroup$ – user482594 Jul 27 '11 at 21:30
  • $\begingroup$ I think that [probability] might be more suited to your question than [graph-theory]. $\endgroup$ – Asaf Karagila Jul 27 '11 at 21:33
  • $\begingroup$ You say three edges, does that mean that between any two nodes there are six edges, or from each node there are exactly three outgoing edges? If the latter is the case, I would think that the probability for failure is almost certain indeed. $\endgroup$ – Asaf Karagila Jul 27 '11 at 21:36
  • $\begingroup$ From each node, there are exactly three outgoing edges is the right one.. $\endgroup$ – user482594 Jul 27 '11 at 21:38

One way (not the only way) that the traversal can fail is for a live node to have all three of its outgoing edges or all three of its incoming edges connect to dead nodes. Assuming independence (not correct, but close enough), a node is connected to at least one other live node in each direction $\left (\frac{7}{8}\right )^2=\frac{49}{64}$ of the time. So the chance that all $250$ live nodes have both an in and an out is $\left(\frac{49}{64}\right ) ^{250}$, which is $\ll 1$

| cite | improve this answer | |
  • $\begingroup$ Where is 7/8 coming from? $\endgroup$ – user482594 Jul 27 '11 at 21:44
  • $\begingroup$ @user42584: each node dies with probability 1/2. So given that you have three outs, at least one will go to a live node with probability 1-(1/2)^3=7/8. Incoming edges are on average 3 per node, so I used the same factor, though it seems you did not constrain the graph to have three incoming edges. If you truly pick the original edges at random, there is a good chance you cannot traverse the original graph because there is a node you can't get to at all. $\endgroup$ – Ross Millikan Jul 27 '11 at 21:54
  • $\begingroup$ I understand it now, Thanks!! $\endgroup$ – user482594 Jul 27 '11 at 22:08
  • $\begingroup$ In the case before any vertices have died, again making the incorrect independence assumption, the incoming number of edges will follow (about) a Poisson distribution of mean $3$. So $e^{-3}\approx.05$ of your vertices on average will have no incoming edge. The chance of at least one vertex with no incoming edge is then about $1-8.7E-12$ $\endgroup$ – Ross Millikan Jul 28 '11 at 12:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.