Made easy Test Series:Graph Theory+Automata

Question

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_____________

Comments

Yes , exactly , you wrote 18 that's why asked.

---

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

---

yep (y)

Answer 1

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$

Answer 2

for X part ,for n bit strings you have to  considered that string   string only whose exclusive OR is 1.

                                              EXCLUSIVE OR:(u0≠v0)∧(un−1=vn−1)]∨[(u0=v0)∧(un−1≠vn−1)]

lets take example for n=2,3.

n=2    possible combinations are 00,01,10,11  only 2 strings are eligible

n=3   possible combinations  are 000,001,010,011,100,101,110,111   only 4 strings are eligible  

hence for n bit strings  ,2^n-1 possibility hence for n=8  ,128 possibility is possible

and connected components is 1 .

hence ans is 128+10=138.

Answer 3

Although a very elegant answer has already been presented here i tried in a shorter method.

Given the premise of the question, we can consider vertices with associated strings of 4 types namely

0…..0, 0…..1, 1…...0, 1…...1

where dots mean any bit value.

I have only signified the first and last bits which are the only bits required to find adjacency.

Let’s shorten the notation even more.

The four types of vertices are 00, 01, 10 and 11. each having $2^{6}$ combinations for the 6 intermediate bits.

let a—b mean a and b are adjacent.

Hence we can write

00 – 01 – 11 – 10 – 00 // Cyclic graph

Hence this is a regular graph where each of the $2^{6}$ vertices are adjacent to $2^{6}$ + $2^{6}$ = $2^{7}$ vertices.

Note that none of the vertices inside the 0….0, 0….1 etc. combinations are adjacent to each other since both their first and last bits are same. hence each of the vertices in the 00 combinations are only adjacent to all the 01 combinations and so on and so forth.

Thus the degree of each node is 128. Thus x = 128

Now clearly the graph is connected thus y = 1

thus x + 10y = 138.