The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+24 votes
3.6k views

Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is $\dfrac{1}{2}.$ What is the expected number of unordered cycles of length three?

  1. $\dfrac {1}{8}$
  2. $1$
  3. $7$
  4. $8$
asked in Probability by Veteran (367k points)
edited by | 3.6k views
0

2 Answers

+65 votes
Best answer

Answer is (C)

A cycle of length $3$ requires $3$ vertices.

Number of ways in which we can choose $3$ vertices from $8$ = $^{8}C_{3} =56.$

Probability that $3$ vertices form a cycle $=\text{ Probability of edge between vertices 1 and 2}\times \text{ Probability of edge}$
$ \text{between vertices 2 and 3} \times \text{Probability of edge between vertices 1 and 3}$

$=\dfrac{1}{2}\times \dfrac{1}{2}\times \dfrac{1}{2} =\dfrac{1}{8}$

So, expected number of cycles of length $3 = 56\times \dfrac{1}{8} = 7$

[email protected] http://stackoverflow.com/questions/14801072/number-of-cycles-in-a-random-graph

answered by Veteran (367k points)
edited by
0
Sir , is there any significance of the term "expected" here , since I am unable to see anywhere the usage of random variable , so the question is actually just asking for the calculation of no of cycles in the graph with 8 vertices .
+9
presence of an edge is given by a random variable- so expectation is important.
+25
  • To count the no of triangles we need to scan the entire graph taking 3 points at a time. So no of experiments = $\binom{8}{3}$
  • Each such experiment result can either be a triangle (with prob p = $\frac{1}{8}$) or no triangle (with prob q = $\frac{7}{8}$ )
  • So, Binomial distribution with $E$ = $\text{np}$

can we model like this ? 

+2

@Debashish_Deka  How are you writing in Blue color ?

+4

..................

0
@ arjun sir, i did not understand your solution.
please  correct me if i am wrong.
here the number of cycles of length three is asked on average if we take a random graph of 8  vertices.
shouldnt the random variable taken be number of cycles of length three in a graph?
0
i think number of cycles of length 3 is acting as random variable here
0

@Arjun Sir, What is the significance of word "unordered cycle" here... What would be the answer if it asked for Number of Ordered Cycles?

0

If it were ordered cycles then total possibilities out of 56 will be (123,234,...678,781,812)?

So expected number of cycles of length 3 will be 8 x $\frac{1}{8}$ = 1

please verify. 

0
ur method is correct but is there some term like ordered cycles in a graph ??
0
Why it cant be 8p3/8 for ordered cycles plzz tell me
+10 votes
Maximum number of cycles of length 3 from 8 vertices = C(8,3) = 56.

It is a Binomial experiment as we keep on repeating the same Bernouli experiment again and again. What Bernouli experiment we keep on repeating ? We keep on checking all 56 possibilities whether there is a cycle or not. Checking is clearly a Bernouli experiment because after checking we will either find cycle (success) or no-cycle(failure).

So number of Bernouli experiments, n = 56.

Let X be a random variable which indicates number of 3-length cycles.

Expectation (X) (i.e) Expected number of 3-length cycles = n * p (since it is a Binomial distribution)

                             where n is number of Bernouli trials or experiments and p is probability of success (i.e) probability of getting a 3-length cycle in 1 Bernouli experiment. p = 1/8 as there are 8 possibilities of having edges with 3 vertices and only one among them will have 3 edges which form a cycle.

    So Expectation (X) = n * p

                                   = 56 *  1/8

                                   = 7.
answered by Loyal (7.7k points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,147 questions
49,639 answers
163,289 comments
65,807 users