CS202: Discrete Structures

8a. Define the basic components of a tree

• What is a tree?
• What are the components of a tree?
• What does acyclic refer to?
• What types of applications can be represented by trees?

A tree is an undirected graph in which any two vertices are connected by only one path. The best way to explain the basic components of a tree is to use a figure. Such a figure is shown in Figure 1.

Figure 1. Tree labeled with its basic components

There are other ways to form a tree, although all trees are, in a sense, hierarchical. In Figure 2, Graphs i, ii, and iii are all trees, while graphs iv, v, and vi are not trees.

Figure 2. Examples of trees and not-trees.

Notice that trees are acyclic, there are no cycles in a tree. However, also notice that trees are undirected graphs. So, it is possible to return to the root from a leaf if one follows the return path. This does not make for a cycle. A cycle is illustrated in Figure 3.

Figure 3. Transforming a tree into a cyclic graph.

Trees are quite useful in many applications. An example is providing an ability to undo prior actions. A tree can represent those actions as they progress so that just-prior actions can be used to replace present actions. Recall what game trees are. These amount to showing what actions are possible given the present situation.

Review:

• Quick Introduction to Trees
• Formal Introduction to Trees

 

8b. Explain trees as a special case of graphs

• What is the difference between a graph and a tree?
• What is the maximum number of edges in a tree?
• Is a tree always undirected?
• What is meant by a single path from one vertex to another?

Trees are graphs but are a special case, a subset of the class "graph". Our readings give a good explanation of that subset.

A tree is an undirected graph, G, that satisfies any of the following equivalent conditions:

• G is connected and acyclic (contains no cycles).
• G is acyclic, and a simple cycle is formed if any edge is added to G.
• G is connected, but would become disconnected if any single edge is removed from G.
• G is connected and the 3-vertex complete graph K3 is not a minor of G.
• Any two vertices in G can be connected by a unique simple path.

If G has finitely many vertices, say n of them, then the above statements are also equivalent to any of the following conditions:

• G is connected and has n − 1 edges.
• G is connected, every subgraph of G includes at least one vertex with zero or one incident edge.
• G has no simple cycles and has n − 1 edges.

Contrary to the way trees are typically drawn, trees can be directed or undirected. For instance, it is not always possible to follow an exact return path. If there is a tree (or other graph, for that matter) with some edges showing direction and some not, edges without direction notations are assumed to be bidirectional. 

Trees can have only one path between nodes. A simple example of a graph that is not a tree because of dual paths between nodes is shown here:

 

Being special cases of graphs, trees can be manipulated and employed in ways that graphs cannot. While reading through the course material, be alert for those differences.

Review:

• Quick Introduction to Trees
• A Formal Introduction to Trees

 

8c. Discriminate between binary and nonbinary trees

• What is a "binary tree"?
• What are standard ways to traverse a binary tree?
• What are ordered rooted trees?
• What are two important applications of binary trees?

A binary tree is a special case of rooted trees. A rooted tree has a labeled node called the root of the tree. This node generally has no ancestors. Each node of a binary tree has no more than two children. This type of tree is very much used in realistic problem-solving since so much data can be placed into a binary structure.

There are four standard ways to traverse a binary tree: Preorder, Inorder, Postorder. (these fall into the category of depth-first traversals), and breadth-first. The course material examines depth-first in detail. Breadth-First starts at the root and visits each node on each subsequent level before moving on to the next lower level.

When we look deeply at the various traversal methods, we see that they all depend on rooted ordered trees. A rooted ordered tree is a tree that has a root and whose subtrees are arranged in a specific order and which themselves are rooted ordered trees. A good example is shown in the figure. Note that, while both trees contain the same data on the same levels, with the same descendants and ancestors, they are not the same tree. And, the same traversal scheme applied to both trees will deliver different results.

Two important applications are discussed in the course material: sorting and the representation of numeric expressions. Take, for example, the game, "guess the number"? A range of numbers is given, a guess is made, and the response is either "high", "low", or "equal". That is exactly what a binary sort tree does with numbers as they arrive over time. It thereby builds a tree of numbers that can be easily searched to see if the number in question is present in the tree. If one takes "the number" as a unique key for a data record, the binary tree becomes an excellent means of creating a structured database for storing and searching those records.

For mathematical expressions, these are arranged in a way that facilitates certain types of processing. Infix notation is the notation commonly used in arithmetical and logical statements. It is characterized by the placement of operators between operands, "infixed operators", such as the plus sign in 2 + 2. We use this approach with most hand-calculators. Reverse Polish notation, also known as Polish postfix notation or simply postfix notation, is a mathematical notation in which operators follow their operands. An example is 2 2 +. There are hand-calculators that use this notation. Polish notation, also known as normal Polish notation, Łukasiewicz notation, Warsaw notation, Polish prefix notation or simply prefix notation, is a mathematical notation in which operators precede their operands. An example is + 2 2. Postfix notation is used in many stack-oriented programming languages like PostScript and Forth. CoffeeScript syntax also allows functions to be called using prefix notation, while still supporting the unary postfix syntax common in other languages.

Review Binary Trees.

 

8d. Identify subgroups within a specific graph that includes all vertices and a minimum number of edges

• What is a spanning tree?
• Suggest applications of spanning trees?
• What is a method of counting spanning trees within a graph?

A spanning tree, T, of an undirected graph, G, is a subgraph that is a tree that includes all of vertices in G, using the minimum number of edges. Spanning trees can also be defined as a maximal set of edges of G that contains no cycle, or as a minimal set of edges that connect all vertices, without forming a cycle. A graph can contain more than one spanning tree. This definition has many implications regarding the optimization of tree structure and traversal.

"Optimization" and "traversal" are very situationally dependent. Spanning trees are especially useful if we want to minimize the number of "lines" between destinations. This problem occurs in networks of all kinds. For instance, establishing lines for power, telecommunications, internet connectivity, or piping between various destinations. In all of these, we want to avoid cycles, returning to somewhere already visited. We may even want to maximize the benefit of traveling along a given path while visiting each node only once.

That there may be more than one spanning tree available for consideration is important because one tree may be more expensive to implement, or yield less benefit than another. How do we know how many spanning trees exist in a given undirected graph? How many such options do we have for finding a minimum or maximum optimization, while satisfying all requirements? Our course material gives us a simple approach to that:

To compute t(G), the number of spanning trees within a graph, G, construct a square matrix in which the rows and columns are both indexed by the vertices in G. The entry in row i and column j is one of three values:

1. The degree of vertex i, if i = j
2. −1, if vertices i and j are connected
3. 0, if vertices i and j are different from each other but not connected

The resulting matrix is singular, so its determinant is zero. However, deleting the row and column for an arbitrarily chosen vertex leads to a smaller matrix whose determinant is exactly t(G).

 

 

Following this same procedure with a four-node graph where all nodes are connected to all other nodes, we find that there are sixteen possible spanning trees. In the case of multiple spanning trees being available, we can eliminate all other edges, once a spanning tree has been selected. (Note: Calculating the determinant of a matrix can be rather involved. That calculation is outside our scope. However, those who are interested can usually find a function for that within their favorite spreadsheet. For instance, Excel uses the MDETERM built-in function).

What is wrong with "optimizing" in some situations, for instance, data network minimization? Reality may dictate criticality of connectivity. Reliability of communication may be necessary so that a lack of dataflow only lasts for a small amount of time. Thus, redundancy may be more important than data network minimization. This may require two spanning trees to be installed and the acceptance of cycles. Be sure to not optimize into non-performance.

Review:

• Overview of Spanning Trees
• Detailed Discussion of Spanning Trees

 

Unit 8 Vocabulary

This vocabulary list includes terms you will need to know to successfully complete the final exam.

• acyclic
• binary tree
• bidirectional
• game trees
• hierarchical
  
• infix notation 
• leaf
• Polish notation 
• postfix notation
• return path 
• reverse Polish notation
  
• root
• rooted tree
• spanning tree
• traverse
• trees