MATH 101 Lecture 4: 14.4
Document Summary
A tree is a graph that is connected and has no circuits. All trees have the following properties: there is one and only one path joining any two vertices, every edge is a bridge (if the edge is removed, the graph becomes disconnected) Example- list the number of vertices/edges in each tree. A subgraph is a set of vertices and edges chosen from among those of the original graph. A subgraph that contains all of a connected graph"s vertices, is connected, and contains no circuits is called a spanning tree. The subgraph in the previous example is a spanning tree. The minimum spanning tree for a weighted graph is a spanning tree with the smallest possible weight. Here is a procedure for finding the minimum spanning tree from a weighted graph: find the edge with the smallest weight in the graph. Highlight it: find the next smallest edge in the graph.
