About

Trees are an important topic in graph theory. A tree is a connected graph with no cycles. They are of enormous practical importance in applied mathematics.

For example, in a connected weighted graph, it is interesting to know how to find a subgraph which is a tree and which maximizes or minimizes the total weight of the subgraph. A subgraph of a graph $G$ which is a tree that touches all nodes of $G$ is called a spanning tree for $G$.

For instance, imagine a network of electrical systems, such as a telephone system, between nodes. Suppose that signals can travel through any path in the network, passing through intervening nodes to get to the final destination. The amount of wiring can be reduced by deleting portions of cycles in the graph of the network. The graph can eventually be reduced to a tree, and all nodes remain connected and accessible through the network.

Dijkstra's algorithm is an effective way to determine the lowest-weight spanning tree for a given connected graph.

history | show excerpt | excerpt history