Graph Theory · Algebra & Patterning
Trees and Spanning Trees
Trees are connected graphs with no cycles. Minimum spanning tree algorithms (Kruskal, Prim) find the cheapest connected subgraph of a weighted graph.
WHAT STUDENTS WILL LEARN
✓Define trees; apply characterization theorems
✓Prove a tree on n vertices has n−1 edges
✓Apply Kruskal’s and Prim’s algorithms
✓Apply trees to data structures and network design
COURSE OUTLINE · CLICK A PART FOR RESOURCES