Question

use kruskals algorithm to find the minimal spanning tree.
a
14
10
12
b
15
11
c
13
16
d
a. acbd
b. abcd
c. bdac
d. dacb

Explanation:

Step1: Sort the edges by weight

Sort all edges in ascending order of weight: \(10\) (\(A - C\)), \(11\) (\(B - D\)), \(12\) (\(A - D\)), \(13\) (\(C - D\)), \(14\) (\(A - B\)), \(15\) (\(B - C\)), \(16\) (\(C - D\) (arc)).

Step2: Select edges for MST

Start adding edges. First add \(A - C\) (weight \(10\)). Then add \(B - D\) (weight \(11\)). Then add \(A - D\) (weight \(12\)). These three edges connect all four vertices (\(A\), \(B\), \(C\), \(D\)) without forming a cycle.

Answer:

A. \(ACBD\)