 Solution

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

A spanning tree is a connected acyclic subgraph containing every vertex of the original undirected graph. For a graph with

∣ V ∣

vertices it has

∣ V ∣ - 1

T \in spanning trees S argmin e \in S \sum w (e) .

Connectedness guarantees existence for a finite graph; equal weights can permit several minimizers.

 New to topics? Read the docs here!