What is the expected number of vertex pairs that are able to communicate with each other in cycle C4?

75 Views Asked by At

Consider the cycle graph C4 Assume that the edges of the cycle fail independently with probability q What is the expected number of vertex pairs that are able to communicate with each other (that are in the same component) ?

1

There are 1 best solutions below

1
On BEST ANSWER

Here's an idea
If the graph is not labeled then these cases appear with their vertices pair count
1. No edge failed. ${4 \choose 2}$
2. One edge failed. ${3 \choose 2}$
3. Two edges failed. Two subcases if edges are consecutive then ${3 \choose 2}$ or if alternate then ${2 \choose 2} + {2 \choose 2}$
4. Three edges failed. ${2 \choose 2}$
5. All edges failed. ${0 \choose 2}$

Now, P(case 1) = $(1-q)^4$
Similarly, P(case 2) = $q(1-q)^3$
P(case 3) = $q^2(1-q)^2$
P(case 4) = $q^3(1-q)$
P(case 5) = $q^4$

I guess you can follow up from here.