# What would be a failure chance of visiting all nodes in this graph traversal?

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
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)

-
Apparently, I am getting failure(graph is not connected) almost 100% of the times. – user482594 Jul 27 '11 at 21:30
I think that [probability] might be more suited to your question than [graph-theory]. – Asaf Karagila Jul 27 '11 at 21:33
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. – Asaf Karagila Jul 27 '11 at 21:36
From each node, there are exactly three outgoing edges is the right one.. – 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$
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$ – Ross Millikan Jul 28 '11 at 12:33