Minimal Spanning Trees (HSC SSCE Mathematics Standard): Flashcards

Connected graph with no cycles, multiple edges, or loops

$n-1$ edges

A tree that connects all vertices of a graph

Spanning tree with minimum total edge weight

Finds minimum spanning tree in a weighted graph

Chooses smallest weight edge that doesn't create a cycle

Any vertex (choice doesn't matter)

Add up all edge weights in the tree

There is a path between any two vertices

Kruskal's algorithm