Lecture Nine: Trees, part 2

  • Recall - a tree is connected graph without circuits
  • If G is a connected, undirected graph, then it has a spanning tree T -- a subgraph of G that is a tree, and which contains all the vertices of G. This spanning tree can be found, for example, by depth-first or breadth-first search.
  • prop: Every tree is bipartite, planar.
  • prop: if G is connected, E* a maximal set of circuit-free edges, then E* is a spanning tree for G. (Pf: if E* not connected, an edge can be added between components, contradicting maximality).
  • prop: If G is any connected graph on N vertices, if it has N-1 edges, no circuits, then it is a spanning tree.
  • We prove Caley's theorem, that there are n^(n-2) labelled trees of size n - done in text also
  • Suppose G is weighted: that is, each edge is assigned a non-negative weight. An important question: what's the least expensive (that is, minimum) spanning tree?
  • Two algorithms to find this: Prim - build tree incrementally, starting with cheapest edge, and always adding to this core subtree in assembly the next cheapest edge that doesn't create a circuit and that is adjacent to the core. And Kruskal: Assemble in order of cost, the first n-1 edges that don't create a cycle. Both algorithms produce the MST.
  • Key lemma: Given a weighted tree as described above, and let V1 and V2 be any non-trivial partition of the vertices in G. If e is the (a) cheapest edge connecting V1 and V2, then there is an MST which contains it.
  • Correctness of Kruskal and Prim follow directly from this. (But: different proof in book)

-- RobbieMoll - 05 Oct 2006

Topic revision: r3 - 2006-10-05 - RobbieMoll
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding UMass CS EdLab? Send feedback

mersin escort adana escort izmir escort gaziantep escort