Spanning Tree
First learned in MATH239, but also revisited in CS341.
A spanning tree of a graph consists of all nodes of the graph and some of the edges of the graph so that there is a path between any two nodes.
Like trees in general, spanning trees are connected and acyclic. Usually there are several ways to construct a spanning tree.
minimum spanning tree = spanning tree whose weight is as small as possible maximum spanning tree = spanning tree whose weight is as large as possible
You can find the minimum / maximum spanning tree:
From MATH239
Spanning Tree
A spanning tree of is a spanning subgraph of that is a tree. In other words, is a tree.
Theorems and Corollaries