CSC263H1 Lecture 20: Lecture 20.docx
22 Apr 2014
School
Department
Course
Professor
Document Summary
A tree is a connected undirected graph with no cycles : Fact 1: a tree with n nodes has n-1 edges. Fact 2: adding any edge to a tree creates a cycle containing that edge. Removing any edge from that cycle results in a tree again: Let g (v, e) be undirected connected graph. A spanning tree of g is a tree t = (v, e"), e" e. A spanning forest of g is a set of trees t1 = (v1, e1), t2 = (v2, e3), , tk = (vk, ek) such that. A minimum spanning tree of g is a spanning tree with minimum weight. Mst problem given any weighted g, find an mst of g. In a complete graph with n nodes there are about nn-2 different spanning trees! Let t1, t2, , tk be a spanning forest of g such that some mst t of g contains t1, t2, , tk.
