Spanning tree

Dependencies:

1. Tree

The spanning tree of an undirected graph $G$ is a subgraph of $G$ which is a tree and contains all the vertices of $G$.

Let $T$ be a spanning tree of a weighted graph $G$. The weight of $T$, denoted as $w(T)$, is the sum of weights of edges of $T$.

A spanning tree of $G$ with minimal weight is called a minimum spanning tree of $G$. A spanning tree of $G$ with maximal weight is called a maximum spanning tree of $G$. The abbreviation MST, which can mean either 'minimum spanning tree' or 'maximum spanning tree', is used when it is either clear from context which meaning is intended, or when it does not matter.

Dependency for:

1. Spanning forest

Info:

• Depth: 3
• Number of transitive dependencies: 6

Transitive dependencies:

1. /sets-and-relations/equivalence-classes
2. /sets-and-relations/relation-composition-is-associative
3. /sets-and-relations/equivalence-relation
4. Graph
5. Path in Graph
6. Tree