GATE CSE 2023 | Question: 46

Question

Let $U=\{1,2,3\}$. Let $2^{U}$ denote the powerset of $U$. Consider an undirected graph $G$ whose vertex set is $2^{U}$. For any $A, B \in 2^{U},(A, B)$ is an edge in $G$ if and only if (i) $A \neq B$, and (ii) either $A \subsetneq B$ or $B \subsetneq A$. For any vertex $A$ in $G$, the set of all possible orderings in which the vertices of $G$ can be visited in a Breadth First Search $\text{(BFS)}$ starting from $A$ is denoted by $\mathcal{B}(A)$.

If $\emptyset$ denotes the empty set, then the cardinality of $\mathcal{B}(\emptyset)$ is ______________.

Comments

Detailed Video Solution:

 BFS question value of B(Φ)

---

what will happen in the case of DFS?

Answer 1

Given that U = {1,2,3} → |U| = 3 → Vertex set = {∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}} and cardinality is 8.

There is an edge between A and B vertices iff either of vertex set is proper subset to other vertex.

As we know ∅ is proper subset to every other set in the vertex set except itself.

That implies, ∅ is connected with 7 vertices directly, these 7 vertices can be visited in any order in BFS.

Therefore No.of BFS orders = 7! = 120x6x7 = 5040.