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,
After reading this question words "Gray code", "Hypercube graph", "Haming Distance" and "Even length cycles" are coming in mind.
Now if you are thinking why Hypercube graph has chromatic no = 2 or Even length cycle then refer -->
https://math.stackexchange.com/questions/227681/how-to-find-chromatic-number-of-the-hypercube-q-n
Chromatic number is 2 so maximum independent set size is $2^{n-1}$.
how u calculate diameter of graph?
The diameter of a graph is the length of the shortest path between the most distanced nodes
set2018 $diameter = max(eccentricity(v), v \ \epsilon \ G)$
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
for traversing from 000. . .0 ⟶ 111. . .1 , we require to traverse atleast 'n' edges.
To find the diameter of a graph, first find the shortest path between each pair of vertices. The greatest length of any of these paths is the diameter of the graph.
Link to the MIT page in answer: http://web.archive.org/web/20100715032114/https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2005/assignments/pset5_soln.pdf
https://math.stackexchange.com/questions/301562/prove-n-cube-is-bipartite
People who are wondering why the resultant K-map will be bipartite, here's how.
Every 2-chromatic graph is known to be bipartite. Converse holds except a particular case - every bipartite graph except graphs of 2 or more isolated nodes (no edges whatsoever) is 2-chromatic.
https://math.stackexchange.com/questions/1503130/can-bipartite-graphs-have-isolated-vertices
toxic desire,
according to your diagram the diameter would be 4 not 3 you missed the edge between
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
@Ritik Jain RJ What an idea sirji 😅🙏
64.3k questions
77.9k answers
244k comments
80.0k users