recategorized by
724 views
1 votes
1 votes

A matching in a graph is a set of edges such that no two edges in the set share a common vertex. Let $G$ be a graph on $n$ $\textit{vertices}$ in which there is a subset $M$ of $m$ $\textit{edges}$ which is a matching. Consider a random process where each vertex in the graph is independently selected with probability $0< p< 1$ and let $B$ be the set of vertices so obtained. What is the probability that there exists at least one edge from the matching $M$ with both end points in the set $B$?

  1. $p^{2}$
  2. $1-\left ( 1-p^{2} \right )^{m}$
  3. $p^{2m}$
  4. $\left ( 1-p^{2} \right )^{m}$
  5. $1-\left ( 1-p\left ( 1-p \right ) \right )^{m}$
recategorized by

1 Answer

2 votes
2 votes

$\text{Probability(selecting any vertex)} = p~,$

$\text{Probability(getting any particular edge)} =  p^2, $

$\text{Probability(not getting any particular edge)} = (1-p^2)$,

$\text{as there are total} \textit{ m edges}  \text{ in the Matching set} \textit{ M,}$

$\text{Probability(not getting any of these} \textit{ m edges}) = (1-p^2)^m$,

$\text{Probability(getting at-least 1 edge from M)}\\ \> = \text{1 – Probability(not getting any edge from M)} \\ \> = 1 – (1-p^2)^m$

Option B.

Answer:

Related questions

3 votes
3 votes
2 answers
4
soujanyareddy13 asked Mar 25, 2021
695 views
Consider the following greedy algorithm for colouring an $n$-vertex undirected graph $G$ with colours $c_{1}, c_{2}, \dots:$ consider the vertices of $G$ in any sequence ...