Which of the graphs below correctly use Kurshal's Algorithm to determine a minimum spanning tree?
1 answer:
Answer:
C
Step-by-step explanation:
Conveniently, the edges have weights that are sequential numbers 1 to 9, so according to Kruskal's algorithm we can examine them in order by weight until we find a 5-branch tree connecting all 6 nodes. (We throw out any branches that cause the tree to have a cycle.)
The branches with weights 1-4 form no cycles, so we can include those branches in our tree. The branch with weight 5 (DE) introduces a cycle (ABCEDA), so we ignore that branch. The next branch has weight 6 and forms no cycles, so it completes the 5 branches we need for our tree.
The result is the tree that matches diagram C.
_____
The diagram of A is not a tree. It contains a branch.
The diagram of B is a tree, but has total weight 20, which is more than the total weight of 16 of the tree in diagram C. Hence the tree of B is not minimal, nor was it found using Kruskal's algorithm.
You might be interested in
Remember that the radicand (the area under the root sign) must be positive or zero for a radical with an even index (like the square root or fourth root, for example). This is because two numbers squared or to the fourth power, etc. cannot be negative, so there are no real solutions when the radicand is negative. We must restrict the domain of the square-root function.
If the domain has already been restricted to
, we can work backwards to add 11 to both sides. We see that 
must be under the radicand, so the answer is A.
If the domain has already been restricted to