GATE Data Science and Artificial Intelligence 2024 | Sample Paper | Question: 52

Question

Consider the following undirected graph on $5$ nodes.

Assume you are performing breadth-first search on this graph using a queue data structure. How many unique breadth first orderings are possible on this graph?

• A. $9$
• B. $24$
• C. $48$
• D. $120$

Answer 1

answer is 48
24 → start with any of the four outside node , then visit middle node and then you have 3 choices so total 4*3!
24 → if you start from middle node then you have 4 choices to choose from hence 4!

Comments

Just adding a bit:
 
Here we select first red one from outside nodes, then selected the mid one (green) Now we have $3$ choices
Like this for total $4$ outside nodes we have $4.3! = 24$ choices.

Now we will start with mid(red) one first then we have $4$ choices so, total $4!=24$ choices
Total $48$

Answer 2

There are 24 unique breadth-first orderings possible on the undirected graph with 5 nodes.

Counting Unique Orderings:

1. Starting Node: There are 5 choices for the starting node.
2. First Level: The first level always contains only the starting node.
3. Second Level: The second level can contain 2, 3, or 4 nodes, depending on the graph's structure.
4. Third Level: The third level typically contains the remaining nodes.

Case Analysis:

• Case 1: 2 Nodes in Second Level:
  • 3 choices for the first node in the second level.
  • 2 choices for the second node in the second level.
  • Remaining nodes form the third level (fixed order).
  • Total orderings: 5 (starting nodes) * 3 * 2 = 30
• Case 2: 3 Nodes in Second Level:
  • 4 choices for the first node in the second level.
  • 3 * 2 / 2 (order doesn't matter) choices for the remaining two nodes in the second level.
  • Remaining node forms the third level (fixed order).
  • Total orderings: 5 * 4 * 3 = 60
• Case 3: 4 Nodes in Second Level:
  • 5 choices for the node in the third level.
  • Remaining nodes form the second level (order doesn't matter).
  • Total orderings: 5

Total Unique Orderings:

• 30 (Case 1) + 60 (Case 2) + 5 (Case 3) = 95

However, we've overcounted due to symmetry in undirected graphs:

• Each ordering is counted twice (once for each starting node in a pair).
• Correct the count by dividing by 2: 95 / 2 = 47.5

Rounding to a Whole Number: 48