GATE 2023 CS – Question 56
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 \subset B$ or $B \subset 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 (BFS) starting from A is denoted by $B(A)$. If $\emptyset$ denotes the empty set, then the cardinality of $B(\emptyset)$ is ______.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 5040
Explanation
The graph has 8 vertices (the subsets of $\{1,2,3\}$), and an edge joins two **different** sets when one is a subset of the other.
The empty set $\emptyset$ is a subset of every other set, so it is adjacent to **all 7 other vertices**.
BFS from $\emptyset$: it visits $\emptyset$ first, and then every neighbour is enqueued. All 7 other vertices are neighbours of $\emptyset$, and they can be enqueued in any order (since the BFS may choose its neighbours in any order). No other vertex remains to be discovered later, so the BFS orderings are the $7!$ orders of the neighbours.
$$|B(\emptyset)|=7!=\mathbf{5040}.$$
More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions
- GATE 2022 CS Q49
- GATE 2021 CS (CS1) Q27
- GATE 2021 CS (CS1) Q46
- GATE 2021 CS (CS1) Q51
- GATE 2020 CS Q41
- GATE 2020 CS Q50
All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →