Trees and Minimum Connector Problems (VCE SSCE General Mathematics): Flashcards

Connected graph with no loops, multiple edges, or cycles

$n - 1$ edges

Tree that connects all vertices of a graph

Spanning tree with smallest possible total weight

Finds the minimum spanning tree of a graph

Any vertex (choice doesn't affect result)

Choose smallest edge that doesn't create a cycle

Sum of all weights on edges in the tree

Connector links all points; shortest links two specific points

Utilities, cables, pipelines, road networks