Trees.html (3170B)
1 <?xml version="1.0" encoding="UTF-8"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 <html><head><link rel="stylesheet" type="text/css" href="sitewide.css"><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta name="exporter-version" content="Evernote Mac 7.1.1 (456663)"/><meta name="keywords" content="ng"/><meta name="altitude" content="278"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-05-10 14:10:45 +0000"/><meta name="latitude" content="50.11340970954857"/><meta name="longitude" content="14.33735134323983"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-25 22:58:34 +0000"/><title>Trees</title></head><body><div>Tree definitions:</div><ul><li><div>is a connected, simple, acyclic graph</div></li></ul><ul><li><div>a tree T ⊆ G is a spanning tree of G if it covers all vertices</div></li><li><div>sink tree — spanning tree optimised for all (v,u)-paths</div></li></ul><div><br/></div><div>Theorems/lemmas:</div><ul><li><div>for any connected G with n vertices, m edges: n ≤ m+1</div></li><li><div>a connected G, n vertices, n-1 edges is a tree</div></li><li><div>simple graph G is a tree if there is exactly one path between any two vertices</div></li><li><div>connected G is a tree iff every edge is a cut edge (a loop is never a cut edge, a cycle has no cut edges)</div></li><li><div>a spanning tree is minimal if sum of weights of edges is minimal</div></li><li><div>T is spanning tree of G. if e ∈ (E(G) \ E(T)), then T ∪ {e} contains a cycle</div></li><li><div>G is weighted connected graph. V<span style="vertical-align: sub; font-size: smaller; font-size: smaller;">1</span>, V<span style="vertical-align: sub; font-size: smaller; font-size: smaller;">2</span> are nonempty partitions, e is an edge with min weight connecting V<span style="vertical-align: sub; font-size: smaller; font-size: smaller;">1</span>-V<span style="vertical-align: sub; font-size: smaller; font-size: smaller;">2</span>. Then there is a minimum spanning tree containing e.</div></li><li><div>G is weighted graph with distinct edge weights, T is its MST, S is a subtree of T, e is lowest-weight outgoing edge of S (incident to exactly one vertex in S). then e ∈ E(T).</div></li></ul><div><br/></div><div><br/></div><div>Constructing minimum spanning trees (Kruskal):</div><ol><li><div>Remove all loops and parallel edges, except one with smallest weight</div></li><li><div>Create edge table in ascending order of weight</div></li><li><div>Pick smallest edge. If it creates a cycle in the graph, discard it. Otherwise, include it.</div></li><li><div>Repeat step 3 until there are n-1 edges in the three. This is the minimum spanning tree.</div></li></ol><div><br/></div><div>Prim-Jarnik algorithm:</div><ol><li><div>Select any vertex as first of T</div></li><li><div>Consider which edge connects vertices in T to vertices outside T. Pick the one with minimum weight. Add edge and vertex to T.</div></li><li><div>Repeat step 2 until T has every verrtex of G.</div></li></ol><div><br/></div></body></html>