There are seven vertices numbered from 1 to 7.
Accenture technical mcq question, verified with a worked answer. Free to practise - no sign-up.
There are seven vertices numbered from 1 to 7. When connecting this with several sides (u, v), which one create a directed tree structure?
Show answer & explanation
A directed tree with n vertices requires exactly n-1 edges with no cycles and a connected structure where each node (except the root) has exactly one incoming edge. Option D has 6 edges for 7 vertices, no self-loops, no cycles, and forms a valid tree rooted at vertex 1 with edges converging to it: 3←1, 2←3, 4←2, 5←2, 7←2, 6←5. Options A and C have self-loops (invalid). Option B has 7 edges (too many for a tree) and cycles.
Step-by-step Derivation:
Check each option for directed tree properties:
Option A: 5 edges for 7 vertices (too few), not connected.
Option B: 7 edges for 7 vertices (should be 6). Edges: (4,7), (1,3), (2,4), (4,1), (2,6), (4,5), (4,3). Contains cycle: 4→1→3 and 4→3. Invalid.
Option C: 6 edges, but contains self-loops: (1,1) and (3,3). Self-loops violate tree structure. Invalid.
Option D: 6 edges for 7 vertices ✓. Edges: (6,5), (7,2), (5,2), (4,2), (3,1), (2,3). In-degree analysis: vertex 1 (in-degree 0, root), vertices 2,3,5,7 (in-degree 1), vertex 4 (in-degree 1), vertex 6 (in-degree 1). Path checking: all vertices reachable from root 1 via directed paths. No cycles. Valid directed tree. ✓