edited by
13,048 views
64 votes
64 votes

Consider the undirected graph $G$ defined as follows. The vertices of $G$ are bit strings of length $n$. We have an edge between vertex $u$ and vertex $v$ if and only if $u$ and $v$ differ in exactly one bit position (in other words, $v$ can be obtained from $u$ by flipping a single bit). The ratio of the chromatic number of $G$ to the diameter of $G$ is,

  1. $\frac{1}{\left(2^{n-1}\right)}$
  2. $\left(\frac{1}{n}\right)$
  3. $\left(\frac{2}{n}\right)$
  4. $\left(\frac{3}{n}\right)$
edited by

9 Answers

Best answer
46 votes
46 votes

Answer is (C)

For the given condition we can simply design a K-MAP and mark an edge between every two adjacent cells in K-Map. (adjacency has to seen just as we do for minimization )

That will give us a Bipartite graph. chromatic number for this $=2$.

Also from the same we can conclude that we need ,for a $'n'$ bit string, to traverse NO MORE than $\left(n-1\right)$ edges or $'n'$ vertices to get a path b/w two arbitrary points.

So ratio is $\left(\frac{2}{n}\right).$

The given graph is actually hypercubegraph. 

https://en.wikipedia.org/wiki/Hypercube_graph

See problem 4 here:
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2005/assignments/pset5_soln.pdf

edited by
31 votes
31 votes

Eccentricity is we have to traverse max distance using optimal path (i.e by using min vetrices)

Max. Eccentricity (i.e Diameter) here is 3, as we can start from any vertex say (000) and to reach vertex (111) diameter is 3.

Hence, the ratio 2/n.

n is here 3 i.e length of bit string

 

3 votes
3 votes
(ans c)

It can be easily solved by putting the value of n=1.

I.e, we have to node '0' and '1'. And they are connected with an edge. Here C.N. is 2 and diameter is 1. So ratio is 2.

Now put n=1 in option and check whether answer is 2 or not.
Answer:

Related questions

37 votes
37 votes
7 answers
1
Ishrat Jahan asked Oct 31, 2014
8,718 views
If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is aHamiltonian cyclegri...
34 votes
34 votes
4 answers
2
Ishrat Jahan asked Oct 27, 2014
8,174 views
What is the chromatic number of the following graph? $2$$3$$4$$5$
43 votes
43 votes
4 answers
3
Akash Kanase asked Feb 12, 2016
15,317 views
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.
46 votes
46 votes
6 answers
4
Kathleen asked Sep 15, 2014
11,046 views
The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is$2$$3$$4$$n-2 \lef...