The Gateway to Computer Science Excellence
+1 vote
129 views
Consider a graph $G$ with $2^{n}$ vertices where the level of each vertex is a $n$ bit binary string represented as $a_{0},a_{1},a_{2},.............,a_{n-1}$,

where each $a_{i}$ is $0$ or $1$ respectively.

Two vertices $u\left ( u_{0}u_{1}.......u_{n-1} \right )$ and $v\left ( v_{0}v_{1}.......v_{n-1} \right )$ are adjacent if  $u$  and  $v$  satisfy the condition


$\left [\left ( u_{0}\neq v_{0} \right )\wedge \left ( u_{n-1}= v_{n-1} \right ) \right ]\vee \left [\left ( u_{0}= v_{0} \right )\wedge \left ( u_{n-1}\neq v_{n-1} \right ) \right ].$


Let $x$ and $y$ denote the degree of a vertex $G$ and number of connected component of $G$ for $n=8.$ The value of $x+10y$ is_____________
in Graph Theory by Veteran (117k points) | 129 views
0
Is it 138 ?
0
How 18? What are you getting x as?
0
x= 128 and y=1.
0
Yes , exactly , you wrote 18 that's why asked.
0

This question is a modified version of https://gateoverflow.in/204117/gate2018-43

0
yep (y)

1 Answer

+3 votes
Best answer

Let condition 1 = $[(u_{0} \neq v_{0})\wedge (u_{n-1}\doteq v_{n-1})]$  ($1^{st}\textrm{ bit different and last bit same}$)

and condition 2 =$ [(u_{0}=v_{0})∧(u_{n-1}≠v_{n-1})] $ ($1^{st}\textrm{ bit same and last bit different}$)


Connected Components

$\rightarrow$ We can make the vertices adjacent if either condition 1 or condition 2 satisfies.

$\rightarrow$ $u_{0}$ bits of first half nodes will be $0$ so we can connect them in serial order and $u_{0}$ bits of other half will be $1$ so we can connect them in serial order using condition 2

$\rightarrow$ Then we can connect $1^{st}$ half with other half by connecting $1^{st}$ node of first half with $1^{st}$ node of other half

$\rightarrow$ So connected components will always be $1$ (except for n=1)

$\rightarrow$ Now we need to find degree of node.


$\rightarrow$ Lets take $n=2$

$\rightarrow$ We have $2^{2}$ vertices.

$\rightarrow$ The vertices are $A(0,0),B(0,1),C(1,0),D(1,1)$

Vertices $u_{0}$ $u_{1}$
$A(a_{0}$) 0 0
$B(a_{1}$) 0 1
$C(a_{2}$) 1 0
$D(a_{3}$) 1 1

Here,

$\rightarrow$ we can connect A with B and C with D based on condition 2.

$\rightarrow$ we can connect D with B and C with A based on condition 1.

$\rightarrow$ No more connections(edges) are possible.

NOTE :- here $\rightarrow$ are bi-directional edges.

$\therefore$ We have $1$ connected component and degree of each node is $2^{1}$=${2}$ for $n=2$


Lets take $n=3$

We have $2^{3}$ vertices.

The vertices are $A(0,0,0),B(0,0,1),C(0,1,0),D(0,1,1),E(1,0,0),F(1,0,1),G(1,1,0),H(1,1,1)$

Vertices $u_{0}$ $u_{1}$ $u_{2}$
$A(a_{0})$ 0 0 0
$B(a_{1})$ 0 0 1
$C(a_{2})$ 0 1 0
$D(a_{3})$ 0 1 1
$E(a_{5})$ 1 0 0
$F(a_{6})$ 1 0 1
$G(a_{7})$ 1 1 0
$H(a_{8})$ 1 1 1

Here we need to Focus on $u_{0}$ and $u_{2}$ only.

$\rightarrow$ we can connect A with B ,A with G, B with C,B with F, C with D , C with E,D with A , D with H ,E with F, F with G , G with H ,H with B and H with E based on condition 2.

$\rightarrow$ we can connect E with A, F with B , G with C and F with D based on condition 1.

$\rightarrow$ No more connections(edges) are possible.

NOTE :- here $\rightarrow$ are bi-directional edges.

$\therefore$ We have $1$ connected component and degree of each node is $2^{2}$=$4$ for $n=3$


So in general we can see that for $n>=2$ nodes we always have $1$ connecetd component and degree of each node is $2^{n-1}$.

$\Rightarrow$ For $n =8$ we will have $1$ connected component and degree of each node will be $2^{8-1}$=$128$

so $x = 128$ and $y=1$

$x+10y = 128 + 10 = 138$

by Boss (21.7k points)
selected by
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
50,645 questions
56,567 answers
195,749 comments
101,708 users