Trees.md (1624B)
1 +++ 2 title = 'Trees' 3 +++ 4 # Trees 5 Tree definitions: 6 7 - is a connected, simple, acyclic graph 8 - a tree T ⊆ G is a spanning tree of G if it covers all vertices 9 - sink tree — spanning tree optimised for all (v,u)-paths 10 11 Theorems/lemmas: 12 13 - for any connected G with n vertices, m edges: n ≤ m+1 14 - a connected G, n vertices, n-1 edges is a tree 15 - simple graph G is a tree if there is exactly one path between any two vertices 16 - 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) 17 - a spanning tree is minimal if sum of weights of edges is minimal 18 - T is spanning tree of G. if e ∈ (E(G) \ E(T)), then T ∪ {e} contains a cycle 19 - G is weighted connected graph. V1, V2 are nonempty partitions, e is an edge with min weight connecting V1-V2. Then there is a minimum spanning tree containing e. 20 - 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). 21 22 Constructing minimum spanning trees (Kruskal): 23 1. Remove all loops and parallel edges, except one with smallest weight 24 2. Create edge table in ascending order of weight 25 26 3. Pick smallest edge. If it creates a cycle in the graph, discard it. Otherwise, include it. 27 28 4. Repeat step 3 until there are n-1 edges in the three. This is the minimum spanning tree. 29 30 Prim-Jarnik algorithm: 31 1. Select any vertex as first of T 32 33 2. Consider which edge connects vertices in T to vertices outside T. Pick the one with minimum weight. Add edge and vertex to T. 34 35 3. Repeat step 2 until T has every verrtex of G.