Minimum Spanning Trees


A minimum spanning tree of a weighted connected graph is a spanning tree whose weight is less than or equal to the weight of every other spanning tree.

But what does that mean? Because that statement might not be terribly clear, let’s break it down:

Informally, a graph is a set of points called vertices that are joined by lines called edges. Formally, a graph is an ordered pair of sets (V, E), where V is a finite set of vertices and E is subset of V x V.

A weighted graph has a number associated with each edge of the graph. Each number is a weight for that edge. The weight of a graph is the sum of all those numbers.

A walk is a finite sequence of vertices in which each pair of neighboring vertices has an edge between them.

A graph is connected if and only if…

View original post 383 mots de plus

Par défaut