 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2014/functional-programming-design-and-analysis-of-algorithms/8/a/solution

G = (V, E)

with undirected edges and edge weights

w

, a spanning tree is a connected, acyclic subgraph containing all vertices. It has

∣ V ∣ - 1

T \in F \subseteq E (V, F) is a tree arg min e \in F \sum w (e) .

It minimizes total weight, rather than the distance of every route from a chosen root. Equal edge weights may permit more than one minimum spanning tree; negative weights do not invalidate the definition.

 New to topics? Read the docs here!