For a network consisting of N nodes,a minimal spanning tree will consist of
A)N − 2 arcs.
B)N − 1 arcs.
C)N arcs.
D)N + 1 arcs.

Question

Quizplus · Accepted Answer

A minimal spanning tree connects all the N nodes, without including any cycles, and with the sum of arc weights minimized. In order to achieve this, we need N - 1 arcs, which will connect all N nodes without forming any cycles. Therefore, option B (N-1 arcs) is the correct answer.

For a Network Consisting of N Nodes,a Minimal Spanning Tree