Answer to Question #176106 in Algorithms for krishna

Question

EXPLAIN IN DETAIL

A network G = (V, E) has 2²⁰ nodes. Each node v is labeled by a unique number L(v) between 0 to

2²⁰-1. No two nodes have the same label and there is a label for every node.

Two nodes u and v have an undirected edge (u, v) between them if and only if the following is true:

(i)The labels of the nodes L(u) and L(v) differ by a Hamming distance of at most 2 in their

binary representation, and

ii)The magnitude of the difference between the two numbers in the two labels is no

more than 9, i.e. | L(u) – L(v) | < 9. 

Answer all of the following questions:

(a) How many nodes in the graph are unreachable from the node with the label

00000000000000000111?

(b) Is the node 11110000000000000000 reachable from the node 00000000000000001111?

(c) How many edges are present in this graph?

(d) Is this graph bipartite?

(e) How many connected components are present in this graph?

 

Answer 1

Edge can connect nodes with numbers in range of 3 bits (| L(u) – L(v) | < 9); in this range Hamming distance$\leq$ 2 is very probable. So, I think, any node is reachable from any node.

a) $20^{20}-2$

b) Yes, it is reachable.

c) It is hard to say; no dependence between number of node and connected edges.

d) I think, it is possible divide the graph to two parts. In one part nodes are not connected (| L(u) – L(v) | > 9, Hamming distance>2); they connected only with nodes in another part.

e) One connected component is present in this graph.