1
$\begingroup$
  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

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)

  • 0
    `Fro$m$ each $n$ode, there are exactly three outgoing edges` is the right one..2011-07-27

1 Answers 1

2

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$

  • 0
    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$2011-07-28