Explain algorithm properties or choices

A question is this type if and only if it asks you to explain why certain edges are always/never included in an MST or which algorithm to choose in a given scenario.

1 questions · Moderate -0.8

Sort by: Default | Easiest first | Hardest first
OCR D1 Specimen Q2
7 marks Moderate -0.8
2 This question is about a simply connected network with at least three arcs joining 4 nodes. The weights on the arcs are all different and any direct paths always have a smaller weight than the total weight of any indirect paths between two vertices.
  1. Kruskal's algorithm is used to construct a minimum connector. Explain why the arcs with the smallest and second smallest weights will always be included in this minimum connector.
  2. Draw a diagram to show that the arc with the third smallest weight need not always be included in a minimum connector.