MA 103 Chapter Notes - Chapter 7-8: Critical Path Method, Prussian G 12, European Route E6
Document Summary
Tree graph: a connected graph that has no circuits. In a tree, there is only one path connecting two vertices. In a tree, every edge is a bridge. 2: a tree with n vertices has n 1 edges. Spanning tree: a subgraph that is a tree and contains all of the vertices. If the edges in a graph have weights, we can find a spanning tree that has minimal weight. Due to property #3, since this graph has 4 vertices, the spanning tree will have 3 edges. Steiner points: suppose you have a triangular graph with points a, b, and c, but d lies in the middle. If all three angles at d measure 120 degrees, then the red edges displayed below are the optimal solution. If each angle of the original triangle measures less than 120 degrees, then a steiner point always exists.
