Graph Theory

Tree definitions

If you already know what a binary tree is, but not a general tree, then pay close attention, because binary trees are not just the special case of general trees with degree two. I use the definition of a tree from the textbook, but bear in mind that other definitions are possible.

Definition. A tree consists of a (possible empty) set of nodes. If it is not empty, it consists of a distinguished node r called the root and zero or more non-empty subtrees T1, T2, …, Tk such that there is a directed edge from r to each of the roots of T1, T2, …, Tk.Definition. A forest is a collection of trees. You can always create a tree form a forest by creating a new root node and making it the parent of the roots of all of the trees in the forest. Conversely, if you lop off the root of a tree, what is left is a forest.

I assume that you are familiar with the terminology of binary trees, e.g., parents, children, siblings, ancestors, descendants, grandparents, leaf nodes, internal nodes, external nodes, and so on, so I will not repeat their definitions here. Because the definitions of height and depth may vary from one book to another, I do include their definitions here, using the ones from the textbook.

Definition. A path from node n1 to node nk is a sequence of nodes n1, n2, …, nk such that ni is the parent of ni+1 for 1 ≤ i < k. The length of a path is the number of edges in the path, not the number of nodes. Because the edges in a tree are directed, all paths are “downward”, i.e., towards leaves and away from the root. The height of a node is the length of the longest path from the node to any of its descendants. Naturally the longest path must be to a leaf node. The depth of a node is the length of the path from the root to the node. The root has depth 0. All leaf nodes have height 0.

The height of a tree is the height of its root. The degree of a node is the number of children of the node. The degree of a tree is the maximum degree of the degrees of its nodes. The tree on the next page has height 3 and degree 5.

It is not hard to see that a tree with N nodes must have N-1 edges because every node except the root has exactly one incoming edge. How many edges are in a forest with N nodes and K trees?

Applications of General Trees

A general tree is useful for representing hierarchies in which the number of children varies.

• In a file system, a node represents each file, and if the file is a directory, then it is an internal node whose children are the files contained in the directory. Some file systems do not restrict the number of files per folder, implying that the number of children per node is varying and unbounded.

• In computational linguistics, as sentences are parsed, the parser creates a representation of the sentence as a tree whose nodes represent grammatical elements such as predicates, subjects, prepositional phrases, and so on. Some elements such as subject elements are always internal nodes because they are made up of simpler elements such as nouns and articles. Others are always leaf nodes, such as nouns. The number of children of the internal nodes is unbounded and varying.

• In genealogical software, the tree of descendents of a given person is a general tree because the number of children of a given person is not fixed.

Spanning Trees

Given a connected graph G, a spanning graph of G that is a tree is called a spanning tree. A spanning tree for an undirected graph G = (V,E) is a graph G’ = (V,E’) such that G’ is a tree. In other words, G’ has the same set of vertices, but edges have been removed from E so that the resulting graph is a tree. This amounts to saying that G’ is acyclic. If G is directed, it means that cycles have been removed. Since a tree with |V| vertices has |V|-1 edges, to generate a spanning tree of a connected graph G having |V| vertices and |E| edges we must delete all but (|V|-1) edges from the G. We cannot do that randomly because it has to be a tree which is acyclic and connected. We must delete |E|-(|V|-1) = |E|-|V|+1 edges, none of which is a bridge. A graph G can have several spanning tree.

Removal of any single edge from a spanning tree causes the graph to be unconnected.

For any spanning tree T of graph G, if an edge e that is not in T is added, a cycle is created. And also see one thing if we add any edge from ~G, we will also create a cycle.

Minimum Spanning Trees

A spanning tree is minimum if there is no other spanning tree with smaller cost. If the graph is unweighted, then the cost is just the number of edges. If it has weighted edges, then the cost is the sum of the edge weights of the edges in the spanning tree.

An example of an application of spanning trees is for finding the least wiring to wire the electrical connections in a building.

A weighted graph and one of its minimum spanning trees:

Figure 1

Figure 2

A relatively simple algorithm for finding a minimum spanning tree is Kruskal’s Algorithm. It is a greedy algorithm in that it always tries to find the best solution at each step. Not all greedy approaches work. Here it does. It uses the Union-Find algorithm from Chapter 8.

Kruskal’s Algorithm

The strategy of this algorithm is continually to select the edges in order of smallest weight and accept an edge if it does not cause a cycle. The idea is to start out with a forest in which each vertex is a tree by itself. Then look for the edge with least weight and connect its two vertices into a tree with two vertices. Find the next smallest weight edge and connect the two vertices together if they are not already in a tree together. If they are in the same tree, then adding this edge would form a cycle, so the edge should not be added. If we continue this process until there is just one tree, then this tree will