Exercises for the week 13 exercise session¶

Task 1¶

A spanning tree of a graph is the subset of graph edges so that they connect all nodes and form a tree, i.e. the result doesn’t contain cycles. Typically there are many possible spanning trees for a graph. The minimal spanning tree is the one where the sum of its edge weights is smallest. A minimal spanning tree is useful, if there is a need to minimize the ”total cost”, i.e. create the cheapest possible graph where you can still reach every node. You can meet these problems for example when configuring and building communications networks.

Kruskal’s algorithm is one way to create the minimal spanning tree. Read about the algorithm from Wikipedia article Kruskal’s algorithm How does the algorithm work and create the minimal spanning tree? Can you notice why it creates specifically a minimal spanning tree? You can also check a visualisation of the algorithm. (Kruskal’s algorithm works also if the graph is not connected. Then it automatically creates a set of spanning trees, i.e. a forest.)

Run Kruskal’s algorithm for the graph below.