Minimal Spanning Tree

chris cambré, Dec 2, 2017

A [url=https://en.wikipedia.org/wiki/Minimum_spanning_tree]minimum spanning tree (MST)[/url][/b] is a subset of the edges of a connected, edge-weighted (un)directed graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible.


  • 1. minimal spanning tree
  • 2. algorithm of Prim
  • 3. algorithm of Kruskal
  • 4. exercise 1
  • 5. exercise 2
  • 6. exercise 3

1.

minimal spanning tree

Drag in the applet one or more points of the graph and look how the [url=https://en.wikipedia.org/wiki/Minimum_spanning_tree]Minimal Spanning Tree[/url] changes with it.
The Minimal Spanning Tree forms a network in which all vertices are connected in such a way that the total weight (here the lenght of the segments) is minimal.
Рchris cambr̩

2.

–

3.

–

4.

–

5.

–

6.

–

Information