Let G = (V,E) be a connected, undirected, weighted graph. Our aim is to find a tree that "touches" all the vertices, using a subset of the edges of the original graph. This is called a spanning tree.

A graph could have more than one spanning tree. If the edges have weights (costs), the aim is to find a spanning tree for which the sum of the weights is minimum. This is called a minimum cost spanning tree.

G Tree 1 Tree 2 Tree 3 ... o o o o 7 / \ 8 7 / 7 / \ 8 / 6 \ / / 6 6 \ o-----o o o o-----o o-----o ... \ / \ / / \ 2 \ / 5 2 \ / 5 / 5 2 \ o o o o Cost = 14 Cost = 18 Cost = 16

How do we find the minimum cost spanning tree? There are two standard algorithms.

©IARCS 2012–2016

PÄ›stujeme web | visit: Skluzavky