McGraw-Hill Higher Education
McGraw-Hill OnlineLearning Center
spacerInformation Centerspacer|spacerInstructor Centerspacer|spacerStudent Centerspacer|spacerHomespacerspacer
spacer
spacer
spacer
spacerSubmit Your Feedback
Go to the Help Center


spacer
Discrete Mathematics and Its Applications
Kenneth H. Rosen, AT&T Laboratories

Chapter 9. Trees

Click here to access a summary of all the Maple code used in this section.

This chapter is devoted to computation aspects of the study of trees. Trees are a specific type of graph, that is connected simple graphs that have no simple circuits.

The Maple code in this chapter assumes that you are using an upgraded version of Maple's networks package. These enhancements primarily affect the display of trees. In particular, the draw command has been updated to understand how to draw rooted trees. To test that you are using correct version, load the networks package and run the command version, as in

with(networks): version();

If this command does not produce a description of the version, then you are using the wrong version. An appropriate version can be found at the ftp site at http://www.mhhe.com/math/advmath/rosen/r5/instructor/maple.html along with installation instructions.

First, we will discuss how to represent, display, and work with trees using Maple. Specifically, we will describe how to represent and construct trees and derive basic characteristics about trees in Maple. We will show how to use Maple to display trees. We will show how to solve a variety of problems, where trees play an important role using Maple, such as in searching and in constructing prefix codes using a specific implementation of the Huffman coding algorithm. We will describe how to use Maple to carry out different methods of traversing trees, where a traversal is a visiting of vertices in some predefined order. Then we will discuss how these traversals relate to the topic of sorting. We continue by showing how to use Maple to create spanning trees of graphs. Then, we will show to use Maple to solve a variety of problems via backtracking. Finally, we will show how to find minimum weight spanning trees of weighted graphs using Maple.

1. Introduction to Trees

Click here to access a summary of all the Maple code used in this section.

To begin, we will demonstrate how to construct trees in Maple. Given an unrooted tree, we can construct this tree in Maple just as we would any graph. We will also provide a procedure that uses some built-in capabilities of Maple that determines whether a specific graph is a tree.

Before delving into the implementation, there are two important points that must be stressed. First, we note that Maple differs from the terminology of the text in the sense that Maple refers to simple cycles when the text refers to simple circuits. The second noteworthy point is that an unrooted tree is a simple graph that has no simple cycles. A rooted tree is exactly the same structurally as an unrooted tree, with the additional property that there is a specific vertex, called the root, which is viewed as the starting point in a tree. In terms of Maple implementation, we represent unrooted trees as graphs, and we create rooted trees from unrooted trees by using Maple commands such as spantree, which will be covered later, by specifying a desired root of an unrooted tree.

One other important type of tree is an ordered tree, which is a rooted tree where the children of a vertex of ordered in some manner, such as 1st, 2nd,...,m-th children if there are m children of a given vertex. We will make use of vertex weights to determine the order of children of a specific vertex. This type of tree will arise later, but it is important to distinguish between unrooted trees, rooted and unordered trees, and rooted and ordered trees.

As a first example, we will discuss unrooted trees. We create a tree in exactly the same fashion as we created a graph, using the networks package of Maple. As our first example, we will create a simple tree on 4 vertices.

with(networks):
new(T1): addvertex(a,b,c,d,f,g,T1):
addedge(a,b,a,c,a,d,b,f,b,g, T1):
draw(Tree(a),T1);

Suppose that we were given a graph and were asked to determine whether or not it was a tree. By the definition of trees, we need to verify the following 3 properties:

  1. The graph is connected.

  2. The graph is simple.

  3. The graph has no cycles.

Using Maple, these properties are easily checked. In particular, we can determine whether a graph is connected in Maple by using the components command, which returns a collection of sets of vertices, where each set in this collection contains the vertices from a connected component of the graph. We can determine whether a graph is simple by using the Maple command gsimp, that returns the underlying simple tree of a multigraph, and then comparing the number of edges of the underlying simple tree to the original graph. This leads to the procedure IsSimple.

IsSimple := proc(G::graph) local H;
    H := networks[duplicate](G); 
    if nops(edges(gsimp(H))) = nops(edges(G)) then true
    else false fi;
end:

Note that we should not simplify G itself as such a simplification is an irreversible process.

To test for connectivity we provide the procedure IsConnected

IsConnected := proc(G::graph) 
evalb(nops(components(G)) = 1) end:

We can determine whether a graph has no cycles by using the cyclebase command of Maple that returns a set of cycles, or simple circuits, that form a basis of all cycles (simple circuits) in the given graph; if the cyclebase has no cycles, the graph has no cycles. This, together with the two previous tests can be used to provide a test if a graph is a tree.

IsTree:=proc(G::graph)
  if not (IsConnected(G) and IsSimple(G)) then 
    RETURN(false); fi;
  if cyclebase(G) = {} then RETURN(true);
  else RETURN(false); fi;
end:

If you prefer, you can replace the cycle base test in this procedure by one which checks to see if the number of edges is one less than the number of vertices.

We are now ready to use the IsTree procedure to determine whether some particular graphs are trees;

IsTree(T1);  IsTree(complete(3));

1.1. Rooted Trees

Click here to access a summary of all the Maple code used in this section.

Up to this point we have dealt with only unrooted trees. We can use the Maplespantree command to change an unrooted tree into a rooted tree. It accomplishes this by updating the sets of ancestors and daughters (descendents) for each vertex, to reflect the structure of the spanning tree.

To use the spantree command, we select a vertex and form a spanning tree with this vertex as the root, directing all edges in the tree towards the root. (We will study spanning trees later in this chapter. Generally, the spantree command takes an undirected connected graph G and a vertex v of the graph and constructs a spanning tree of G using v as the root, directing all edges towards v.) For example, we can make the tree T1 into a rooted tree, taking a as its root using the command

T2:=spantree(T1, a):

We can easily examine relationships between the vertices of a tree using built-in Maple commands. Among the commands that are useful for this are the daughter, ancestor, neighbors and departures commands. The daughter command finds the children of a vertex in a rooted tree, and the ancestor command of Maple finds the parent vertex of a vertex in a rooted tree. The neighbors and departures act in a similar manner, determining the children of a vertex in the rooted tree.

To illustrate the usage of some of these commands in Maple, we can examine relationships of trees such as parents, children, ancestors and descendants of specific vertices. For instance, we can find the children of the vertex a in the tree T2, using the command:

daughter(a, T2);

To find the parent of d in the tree T2, we use the command:

ancestor(d, T2);

We now present a procedure that finds all the descendants, ancestors, and siblings of a particular vertex in a rooted tree. This procedure, called Family, can be described using the following pseudocode:

  1. To find all ancestors, we use the ancestor command of Maple until there are no more ancestors (i.e. when we reach the root vertex).

  2. To find all descendants, we use the daughter command repeatedly until there are no more descendants (i.e. when all leaves from a vertex have been reached).

  3. To find all siblings of a vertex v, we first find the ancestor of v, called w; the siblings of v are the descendants of w other than v.

An implementation of this procedure is as follows:

Family := proc(v::name,G::graph)
  local Temp, Ancestors, Descendants, Siblings;
  Ancestors := ancestor(v,G);
  Temp := ancestor(v,G);
  while not (Temp = {}) do
    Ancestors := Ancestors union Temp;
    Temp := ancestor(Ancestors,G);
  od;
  Descendants := daughter(v,G);
  Temp := daughter(v,G);
  while not (Temp = {}) do
    Descendants := Descendants union Temp;
    Temp := daughter(Descendants,G);
  od;
  Siblings := daughter(ancestor(v, G), G) minus v;
  [Ancestors,Siblings,Descendants];
end:

We will now build a larger tree, called T3 which is the tree shown on Page 5433 of the text, and then we will execute the newly created procedure on one of its vertices.

new(T3):
addvertex(A,B,C,D,E,F,G,H,I,J,K,L,M,N,T3):
addedge( [A,B],[A,J],[A,K],[B,C],[B,E],[B,F],
   [C,D],[F,G],[F,I],[G,H],[K,L],[L,M],[L,N], T3):
draw(Tree(A),T3);

The descendants of the vertex B are obtained by the commands

Bfamily := Family(B,T3);  Bfamily[3];

Next, we determine the set of internal vertices and leaves of a rooted tree. Recall that an v is an internal vertex of a rooted tree if v has children, and that v is a leaf vertex of a rooted tree if v has no children. In other words, in any non-trivial rooted tree (i.e. a rooted tree that is more than a single root vertex), the leaves are those with vertex degree 1, and the internal vertices are vertices with vertex degree greater than 1.

Knowing this, we can use the Maplevdegree command to determine the set of leaves and the set of internal vertices of a given rooted tree.

Leaves:=proc(T::graph, root::name) 
  select( proc(x,T) evalb( vdegree(x,T) < 2 ) end,
     vertices(T) minus root , T );
end:
Internal:=proc(T::graph, root::name) 
  select( proc(x,T) evalb( vdegree(x,T) > 1 ) end,
     vertices(T) minus root , T );
end:
Leaves(T2, a); Internal(T2,a);

We will now discuss how to find the largest number of children of an internal vertex of a rooted tree. Recall that if m is this number, the tree is called an m-ary tree. We will also describe how to determine if an m-ary tree is balanced. Recall that a tree is balanced if all the leaves are at level h or h-1 if a tree has a total of h levels, where the level of a vertex is the length of the unique path from the root to that vertex.

To use Maple for determining whether a tree is an m-ary tree, we can simply look at the degree sequence of the vertices, taking into account that for all vertices except the root, the degree of that vertex is one more than the number of descendants. This can be accomplished by using the vdegree command in Maple. To determine whether a tree is balanced, we can use the internal storage structure of a tree in Maple. We will use the fact that Maple stores the level of a vertex in a tree as the vertex weight for that vertex. For instance, if v is a vertex that is at level 3 in a tree, then we can extract this information by using the vweight command on the vertex v.

This technique is formalized by the following Maple procedure:

ArityBalanced:=proc(G::graph, Root::name)
  local Leaf_Depth, V, Max_Children, is_balanced,i;
  V:=vertices(G); Leaf_Depth:={};
  is_balanced:=false;
  for v in V do
    if (not (v = Root)) and (vdegree(v,G)=1) then
      Leaf_Depth:=Leaf_Depth union vweight(v, G);
    fi;
  od;
  if nops(Leaf_Depth) > 2 then
    printf(`The tree is not balanced`);
  elif nops(Leaf_Depth) = 1 then
    printf(`The tree is balanced`);
    is_balanced:=true;
  elif nops(Leaf_Depth) = 2 
  and abs(Leaf_Depth[1] - Leaf_Depth[2]) > 1 then
    printf(`The tree is not balanced`);
  else
    printf(`The tree is balanced %a`, Leaf_Depth );
    is_balanced:=true;
  fi;
  Max_Children:=maxdegree(G)-1;
  if vdegree(Root, G) > Max_Children then
    Max_Children:=vdegree(Root, G);
  fi;
  printf(`The arity of the tree is %d`, Max_Children);
  [Max_Children, is_balanced];
end:
ArityBalanced(T3, A):

We will now use the ArityBalanced procedure to verify the formulae on page 541 of the text for full m-ary trees. That is, we will construct a procedure to compute the number of internal vertices and leaves of a given m-ary tree, and compare these quantities as outlined in Theorem 3 and Theorem 4 on page 541 of the text. The procedure called TheoremVerify will use

TheoremVerify:=proc(G::graph, Root::name) 
  local internal, m, leaves, n, i, V, is_full_tree;
  V:=vertices(G);
  n:=nops(V);
  i:=0; internal:=0; leaves:=0;
  is_full_tree:=true;

Use the ArityBalanced procedure to determine arity

  m:=ArityBalanced(G, Root)[1];
  while is_full_tree and i<n do
    i:=i+1;

If there are no children of the vertex, it is a leaf

    if nops(daughter(V[i], G)) = 0 then
       leaves:=leaves+1;

If the number of children is not m, then it is not a full tree

    elif not (nops(daughter(V[i],G)) = m) then
       printf(`The tree is not a full tree`);
       is_full_tree:=false;

The current vertex is an internal vertex

    else 
       internal:=internal+1;
    fi;
  od;
  if is_full_tree then 
    printf(`Vertices count is %d`, n);
    printf(`Computed count (m*i+1) is %d`, m*internal + 1);
    printf(`Leaf count is %d`, leaves);
    printf(`Computed count ((m-1)*i + 1) is %d`,
        (m-1)*internal+1);
  fi; NULL;
end:

We will use the TheoremVerify procedure to verify Theorems 3 and 4 from the text on a full 3-ary tree.

new(Full1):
addvertex(A,2,3,4,5,6,7,8,9,10, Full1):
addedge(A,2, A,3, A,4, 2,5, 2, 6, 2,7, 
         4,8, 4,9, 4,10, Full1):
TheoremVerify(Full1, A);

2. Application of Trees

Click here to access a summary of all the Maple code used in this section.

This section is concerned with the use of trees in binary search trees. Specifically, we address the use of trees in binary search algorithms as well as the use of trees in Huffman codes. The reason that we wish to use binary trees is that we can use the binary structure of the tree to make binary decisions (i.e. true/false) regarding insertion or search paths.

A tree is called a binary tree if all vertices in the tree have at most two children. In this chapter, we will be using ordered binary trees. The ordering of the vertices is simply a labeling of the children of a vertex as either the left child or the right child, where the left child is regarded as the child that should be visited first, and the right child is the child that should be visited second.

2.1. Binary Insertion

Click here to access a summary of all the Maple code used in this section.

A key benefit of ordered binary trees is that the search time required to find a specific element of the tree is logarithmic in the number of vertices of the tree. The major drawback is that the initial insertion of a vertex is much more expensive. We discuss these in greater detail as we go through the actual implementation of a binary insertion algorithm.

We require vertex labels. In Maple we can use the name of the vertex as a label as it can be either an integer or a character string.

A typical vertex in the tree has two descendents (daughters). We must be able to specify which of these two vertices is the left descendent, and which is the right. We can indicate this by using the weight of the vertex. In Maple, each vertex has a default weight of 0 as shown by the simple example

new(g): addvertex(1,2,g):
vweight(1,g);

We can use the weight of the vertex to specify a left to right ordering. An even simpler solution is simply to agree that the weight of the vertex is its name and to impose an ordering on those names.

To compare two vertex names, we can use a procedure such as

IsLessThan := proc(a,b) local t;
  if type( [a,b], [string,string]) then
      t := sort( [a,b] , lexorder );
  else 
      t := sort([a,b]);
  fi;
  if a = t[1] then true else false fi;
end:

Using this comparison allows us to generally ignore what type of label is being used.

IsLessThan(1,2); IsLessThan(b,a); IsLessThan(1,b); 

It also makes it easier to change the comparison criteria at some later point without recoding the entire algorithm.

We will also need to be able to find the root of the tree. The following procedure calculates such a root and forces the tree to remember its root so that the computation does not need to be repeated.

FindRoot := proc(T::GRAPH)
  local v, V;
  V := vertices(T);
  if not assigned( T(Root) ) then
      for v in V do 
        if indegree(v,T) = 0 then
           T(Root) := v;   # remember the root
        fi;
      od;
      if not assigned( T(Root) ) then 
  ERROR(`no root`) fi;
  fi;
  T(Root);
end:

The procedure for constructing an ordered binary tree by insertion is as follows. For simplicity, we use the vertex name as its value when doing comparisons.

  1. Given a vertex v to insert into tree T, we need to locate the correct place in the the tree T to insert v

  2. If the tree T is empty, insert v as the root

  3. Otherwise, make the root of the tree the current vertex cur_vertex and compare v with cur_vertex. If v =cur_vertex you are done.

  4. If v <cur_vertex then search the left child, otherwise, search the right child. This is accomplished by changing cur_vertex to be either the left or the right child and comparing the new cur_vertex with v.

  5. Eventually, we will not be able to go search in the direction the comparison says we should go. At this point, insert v as the missing child of cur_vertex.

A detailed implementation of the algorithm is as follows.

Binsertion := proc(T::graph, x::string,integer)
  local cur_vertex, V, i, Kids, Left, Right;
  V := vertices(T);
  if nops(V) = 0 then
    addvertex(x, T);
    T(Root) := x ;  # remember the root for later
    RETURN( x );
  fi;

We have a rooted tree ...

  cur_vertex := FindRoot(T);
  while x <> cur_vertex do

The relative orderings of the descendants and x and cur_vertex determine if x can be added as a leaf.

      Kids := daughter(cur_vertex,T);
      Kids := sort( convert(Kids,list) , IsLessThan );
      Candidates := 
       sort( [ x, cur_vertex, op(Kids)], IsLessThan );

Begin with the easy cases.

  if nops(Candidates) = 2 then

no children so just add in new vertex.

      if IsLessThan(x,cur_vertex) then
    addvertex(x,weight=`Lft`,T);
      else
    addvertex(x,weight=`Rht`,T);
      fi;
      addedge( [cur_vertex,x] , T);
      cur_vertex := x;
      break;
      elif nops(Candidates)=4 then

two descendents so no insertion at this level ...

      if IsLessThan(x,cur_vertex) 
          then cur_vertex := Kids[1];
      else cur_vertex := Kids[2]; fi;
      next;
  elif nops(Candidates) = 3 then

not this level if pattern is [x,L,cur_vertex] or [L,x,cur_vertex] [cur_vertex,L,x] or [cur_vertex,x,L]

      if Candidates[1] = cur_vertex 
      or Candidates[3] = cur_vertex 
      then
          cur_vertex := Kids[1];
          next;
      fi;

For all remaining cases add in x as a new vertex

      if IsLessThan(x,cur_vertex) then
    addvertex(x,weight=`Lft`,T);
      else
    addvertex(x,weight=`Rht`,T);
      fi;

Yes! This level.

      addedge( [cur_vertex,x] , T);
      cur_vertex := x;
      break;
  fi;
    od;
    RETURN( cur_vertex );
end:

The addvertex procedure is used here in a manner which updates the weights of each vertex as it is created. This is to indicate if the vertex is a left or right descendent. While we do not use these weights, they could be used as an alternative measure for sorting the descendents of any particular vertex.

Instead, for sorting we use the names of the vertices to indicate the relative ordering of vertices. The fact that any two vertices (not just descendants of the same vertex) can be compared allows us to combine the new vertex, the descendents, and the current vertex all into one sorted list which is then inspected to determine which of the many special cases is relevant during the insertion of a new vertex. Whatever method of comparing vertices is used, it is important that the comparison procedure be passed on to the sort routine as an extra argument.

To validate this procedure, examine how the following list of integers is added:

Num_List:=[4,6,2,8,5,3,7,1]:
new(Tree_Num):
for i from 1 to 8 do
  Binsertion(Tree_Num, Num_List[i]);
od;

To see the resulting tree and its structure, use the Mapledraw command.

draw(Tree(4), Tree_Num);

The result is clearly a binary search tree.

Binary trees exist to be searched. The following procedure BiSearch does so. Print statements have been added to illustrate the path that the algorithm uses while searching the tree.

BiSearch := proc(T::graph, v) 
   local  i, Kids, cur_vertex;
   cur_vertex := FindRoot(T);
   while v <> cur_vertex do
      print(cur_vertex);

check the easy cases

      if v = cur_vertex then RETURN(true); fi;
      Kids := daughter(cur_vertex,T);
      if Kids = {} then RETURN( false) fi;

descendants so start looking ...

      Kids := sort( convert(Kids,list) );
      Candidates := 
        sort( [v , cur_vertex, op(Kids)], IsLessThan);
      if nops(Candidates) = 4 then # both descendents 
        if IsLessThan(cur_vertex,v) then
            cur_vertex := Kids[2];
        else
            cur_vertex := Kids[1];
        fi;
    next;   # back to top of loop
      elif nops(Candidates) = 3 then 

not present unless cur_vertex is the first or the last in the list

        if Candidates[1] <> cur_vertex 
        and Candidates[3] <> cur_vertex then
           RETURN( false );
        fi;
        cur_vertex := Kids[1];
        next;
     fi;
  od;
  RETURN(true);
end:

To test this procedure, we try searching for two elements, one of which is in the tree and one of which is not. Tree_Num;

BiSearch(Tree_Num,8);         
BiSearch(Tree_Num,12);         

2.2. Huffman Coding

Click here to access a summary of all the Maple code used in this section.

Huffman coding is a method for constructing an efficient prefix code for a set of characters. It is based on a greedy algorithm, where at each step the vertices with the least weight are examined. Huffman coding can be shown to produce optimal prefix codes. The following pseudocode describes an algorithm for Huffman coding. (For a fuller discussion of Huffman coding, see Cormen, Leiserson, and Rivest, Introduction to Algorithms, MIT Press, 1989.)

  1. Begin by creating an ordered list of the elements to be coded, where the ordering is with respect to the frequency of occurrence of these elements. Consider each element of the list as a vertex with weight equal to its frequency of occurrence.

  2. Remove the first two elements, x and y, from this list

  3. Assign x as the left child and y as the right child of a new vertex z in our tree

  4. Assign the weight of z to be the sum of the weights of x and y

  5. Insert z into the correct position of our list and repeat step (2).

  6. Upon completion, our list contains only one element, which is a rooted binary tree.

Once again, a special comparison routine is required. Code elements are represented by lists such as [a,15] and [b,10]. The following procedure HuffCompare compares two such elements.

HuffCompare :=proc(a::list,b::list) 
if a[2] <= b[2] then true else false fi;
end:

For example, we find that [b,10] < [a,15].

HuffCompare([b,10],[a,15]);

Using this method of comparison, lists of code elements can be sorted into ascending order.

sort( [[a,5],[b,10],[c,8],[d,11]], HuffCompare);

The full Huffman Encoding algorithm is implemented as follows:

Huffman:=proc(L::listlist)
  local i, j, k, n, Q, T, x, y, z, Temp;
  new(T);
  Q := sort( L , HuffCompare ); i := 1;
  while(nops(Q)>1) do
     i := i+1;

get the first two code elements

     x:=Q[1]; Q:=subsop(1=NULL, Q);
     y:=Q[1]; Q:=subsop(1=NULL, Q);

build the new vertex and its location

     z := [ i , x[2]+y[2]]; 
     for j to nops(Q) while HuffCompare( z, Q[j]) do
        j := j+1;
     od;  j := j-1;

add the vertices and edges to the tree

     Q := [seq(Q[k],k=1..j),z,seq(Q[k],k=j+1..nops(Q))];
     addvertex([x[1],y[1],z[1]],weights=[x[2],y[2],z[2]],T);
     addedge([z[1],x[1]],[z[1],y[1]],T);
  od;
  RETURN( eval(T) );
end:

The type listlist denotes a list of lists. The final eval is included to ensure that the result returned by the procedure is the actual tree and not just its name.

Try this newly created procedure on the following list of English characters paired with a relative frequency of occurrence;

Huf:=Huffman([[f,15],[b,9],[d,22],[c,13],[a,16],[e,45]]):

To see the result we again use the Mapledraw command;

rt := FindRoot(Huf);
draw(Tree(rt), Huf);

3. Tree Traversal

Click here to access a summary of all the Maple code used in this section.

In this section we show how to use Maple to carry out tree traversals. Recall that a tree traversal algorithm is a procedure for systematically visiting every vertex of an ordered rooted tree. In particular, we will provide procedures for three important tree traversal algorithms: preorder traversal, inorder traversal, and postorder traversal. We will then show how to use these traversal methods to produce the prefix, infix, and postfix notations for arithmetic expressions.

These tree traversals rely on the construction of ordered rooted trees. We shall use vertex weights to represent the order of children, as was done in earlier sections.

We create an ordered tree, based on the tree of Figure 3 on page 5566 of the text, in order to see the behavior of the various tree traversals. Then, the graph becomes

d := 'd':

new(Trav): 
addvertex( [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p],
  weights=[0,1,2,3,1,2,1,2,3,1,2,1,2,1,2,3], Trav):
addedge( [[a,b],[a,c],[a,d],[b,e],[b,f],[d,g],[d,h],
  [d,i],[e,j],[e,k],[g,l],[g,m],[k,n],[k,o],[k,p]], Trav):
draw(Tree(a),Trav);

The weights added to the vertices here represent the number of that vertex in terms of its parent. For example, d is the 3rd child of a. As in the previous section, such weights could be used for sorting, though in fact the underlying ordering is simply alphabetic on the names of the vertices.

We first implement the the preorder traversal algorithm. This visits the root and then each subtree left to right in a preorder traversal manner. In pseudocode form, the algorithm is;

  1. Visit the root of T. Set current vertex to be the root.

  2. Consider the children of the current vertex as roots of trees T_1, T_2, ...T_m, taken in left to right order. Repeat step (1) on each of these subtrees in order.

As can be seen from step (2) of the above pseudocode, this algorithm is recursive. We provide the following implementation in Maple:

Preorder:=proc(G::graph, r)
  local Dep, v, T;

Visit the root

  printf(`%a `, r);

Consider children of the root

  Dep:= departures(r, G);

Form the correct order of children

  Dep:= sort( convert(Dep,list) , IsLessThan );

Preorder traverse these subtrees in order

  for v in Dep do 
    Preorder(G, v);
  od;
  printf(``, r);
end:

The order in which we traverse the descendents is determined by the boolean procedure IsLessThan (from in the previous section). To traverse the descendants in a different order, use a different comparison routine.

We can examine the execution of this procedure on the earlier created tree Trav, rooted at vertex A.

Preorder(Trav, a);

We implement inorder traversal, in a similar manner. We simply alter the sequence in which the vertices are visited. Specifically, we look at leftmost subtree vertices, followed by the root, followed by the rightmost subtree vertices. In pseudocode this is:

  1. If the tree T has only one vertex, r then visit r

  2. Else, the tree T has more than one vertex. Call the leftmost subtree (rooted at the leftmost child) T_1. Inorder traverse T_1, then visit the root r of T.

  3. Inorder traverse the rooted subtrees T_2,...,T_m.

A Maple implementation is as follows:

Inorder:=proc(G::graph, r)
  local v, Dep, T;

If we have reached a leaf vertex, print it

  if outdegree(r, G) = 0 then
    print(r);

We are at an internal vertex

  else
    Dep:=departures(r, G);

Determine order of children and traverse the subtree based at the leftmost child.

    Dep := sort( convert( Dep , list ), IsLessThan );
    Inorder(G, Dep[1]);

Visit the root

    print(r);

Inorder traverse the remaining subtrees

    for v in Dep[2..nops(Dep)] do 
      Inorder(G, v);
    od;
  fi; NULL;
end:

We have added a NULL as the last statement so that nothing is returned.

Once again, to traverse the children in a different order, use a different comparison routine to sort the descendants. Test this newly created procedure by executing it on the tree Trav.

Inorder(Trav, a);

The final traversal that we shall implement in the postorder traversal. Postorder traversal is similar to the preorder traversal, except that we visit the root after we visit each subtree. In pseudocode this is:

  1. Consider the children of the root as subtrees T_1, T_2, ...T_m, taken in left to right order.

  2. Postorder traverse T_1, then T_2, up to T_m.

  3. Print the root of the current tree.

A Maple implementation of this procedure is as follows:

Postorder:=proc(G::graph, r::name)
  local v,i, Dep, T;

Consider children of the root

  Dep:=departures(r, G);

Form the correct order of children

  Dep:= sort( convert(Dep,list) , IsLessThan) ;

Postorder traverse these subtrees in order

  for v in Dep do
    Postorder(G, v);
  od;

Visit the root

  printf(` %c`, r);
end:

We also test this procedure on the tree Trav with root A.

Postorder(Trav, a);

3.1. Infix, Prefix and Postfix Notation

Click here to access a summary of all the Maple code used in this section.

We will now discuss how to use Maple to work with the infix, prefix, and postfix forms of arithmetic expressions. These forms are discussed in Section 8.33 of the text. Specifically, we will show how to create a binary tree representation of an infix expression, how to use postorder and preorder traversals to create postfix and prefix forms of the expression, respectively, and how to evaluate these expressions from their postfix and prefix forms.

To begin this section, we construct a Maple procedure that takes a infix arithmetic expression and converts it into a binary tree representation. This binary tree representation can then be traversed using the traversals of the previous sections to form various arithmetic representation formats. As an example, we can construct a binary tree representation of an infix expression, such as (3+10)^2 - (100-30)/(5*2), then execute a preorder traversal to form a prefix representation of this arithmetic expression.

In the Maple procedure that we will implement, we will consider a modified version of infix notation, to avoid complicated string manipulation that detract from the underlying problem.

Specifically, we will use lists braces instead of the normal parenthesis () of infix notation.

Additionally, we will define our operators in terms their string representations: + for addition, - for subtraction and so on.

In this way, Maple's list handling facilities are immediately available. Thus, we represent expressions such as x + y as [x,"+",y] where + is a string.

Maple procedures can be used to help us to construct such lists. For example,

`&Plus` := proc(a,b) [a,Unique(`+`),b] end:

allows us to write and use

x &Plus y;

Maple handles procedure names of the form ... as infix operators. The procedure Unique has is defined especially for the routines used in this book and is part of the the support library for this book that is available via ftp.

The result is a list including a specially encoded version of the string + which does not collide with prior uses of + as a name. (Every vertex of the expression tree must have a different name, even if they look the same.)

Similarly we use

`&Times` := proc(a,b) [a,Unique(`*`),b] end:
`&Pow` := proc(a,b)   [a,Unique(`^`),b] end:
`&Div` := proc(a,b)   [a,Unique(`/`),b] end:
`&Minus` := proc(a,b) [a,Unique(`-`),b] end:

so that we can write and use

x &Times y, x &Pow y;

These can be used to write the arithmetic expression ((x+y)^2)+((z-4)/3) as

Expr1:= (((x &Plus y) &Pow 2) &Plus ((z &Minus 4) &Div 3 ));

The result is a nested list of lists, each list representing a binary operation.

Now we are ready to construct a binary tree representing such an expression. The required algorithm in pseudocode is:

  1. If there is a single algebraic expression (such as a name or a number) the tree consists of a single vertex.

  2. Otherwise, the list consists of a left operand, an operator and a right operand. Use the algorithm to build a binary tree for the left operand .

  3. Repeat step (2) on the right operand.

  4. Combine the results of steps (2) and (3) to form the binary tree.

Our implementation is as follows:

InFixToTree:=proc(L::list,algebraic)
  local r1,r3, T1, T3,LocL; 

If we have no sublists in our expression, return the vertices and edge lists as shown

  if type(L,algebraic) then
    new(T1); LocL := Unique(L); 
    addvertex(LocL,T1); 
    T1(Root) := LocL;
    RETURN( eval(T1) );
  fi;

L is now a list such as [a , + , b]

  T1 := InFixToTree(L[1]); r1 := T1(Root);
  T3 := InFixToTree(L[3]); r3 := T3(Root);

construct the new tree

  addvertex(vertices(T3),T1);
  addedge( ends(T3), T1 );
  addvertex( L[2] , T1 ):
  addedge( [L[2],r1], [L[2],r3]  , T1 );
  T1(Root) := L[2];
  RETURN( eval(T1) );
end:

The root of the tree is handled in a special way. Recomputing the root of the tree is awkward and expensive so we simply ask each tree to remember its own root. This is accomplished by assignment statements such as T(Root) := LocL;.

The procedure Unique is used once again to ensure each instance vertex name is unique, even if it looks the same as another. In all other aspects, the implementation is almost exactly as outlined in the pseudocode.

To test this procedure, use it to build an expression tree for the earlier expressionExpr1.

Expr1;
TreeExpr1:=InFixToTree(Expr1):

To see this, draw it as a tree.

r := TreeExpr1(Root);
draw(Tree(r),TreeExpr1);

Suppose we are given a binary tree representation of an arithmetic expression. We can use the earlier created algorithms to express these trees as either postfix or prefix expressions by executing the postorder or preorder traversals, respectively. Since this is straightforward, it is left up to the reader to explore this technique.

As a final example in this section, we demonstrate how to evaluate a given postfix expression. For simplicity, we have represented the the basic operations by the first letters of the words add, subtract, multiply, divide, and exponentiate. The reader is left to explore how to implement a procedure that will evaluate a prefix expression, since the technique is a simple modification of the argument that will be used in the postfix case.

Post1:=[7,2,3,M,S,4,E,9,3,D,A];
Postfix:=proc(T::list)
  local i, L;
  L:=T;
  while nops(L)>1 do
    i:=1;
    while not member(L[i], 'A','S','D','M','E') do
      i:=i+1;
    od;
    if L[i]='A' then
      L[i]:= L[i-2]+L[i-1];
    elif L[i]='M' then
      L[i]:= L[i-2]*L[i-1];
    elif L[i]='S' then
      L[i]:= L[i-2]-L[i-1];
    elif L[i]='D' then
      L[i]:= L[i-2]/L[i-1];
    elif L[i]='E' then
      L[i]:= L[i-2]^L[i-1];
    fi;
    L := [op(L[1..i-3]),op(L[i..nops(L)])];
  od;
  L;
end:
Postfix(Post1);

Note that in release 4, we are permitted to assign directly to list elements.

4. Trees and Sorting

Click here to access a summary of all the Maple code used in this section.

This section explains how to use Maple to carry out and analyze sorting algorithms. Trees are often used to model sorting algorithms, especially when the complexity of these algorithms is being studied. In particular, this section focuses on two of the many different sorting algorithms will be studied, the bubble sort and merge sort.

4.1. Bubble Sort

Click here to access a summary of all the Maple code used in this section.

To begin, we will examine an implementation of bubble sort. The reason why bubble sort has been given the title of "bubble" is that the smallest of the list "bubble" towards the front of the list, moving one step closer to their position after each iteration. The pseudocode, which is outlined on page 575 of the text, is as follows;

  1. Receive as input a list, L, of n elements

  2. Loop on index i from 1 to n-1

  3. Loop on index j from 1 to n-i

  4. If the element at position j+1 in the list L is smaller than the element at position j of L, swap these two elements

At the end of each j loop, we placed the largest i elements at the end of L.

The following procedure, called BubbleSort, is an implementation of this pseudocode.

BubbleSort:=proc(L::list)
  local i, j, temp, T;
  T:= array(L);
  for i from 1 to nops(L)-1 do
    for j from 1 to nops(L)-i do
      if T[j] > T[j+1] then
        temp:=T[j];
        T[j] := T[j+1];
        T[j+1] := temp;
      fi;
    od;
  od;
  convert(T,list);
end:

Note that before starting to move elements around, we converted the list L to an array. This is because we can change each element of an array in one operation whereas to change any part of a list, we must recopy the entire list -- a process involving n operations. When we are finished moving elements around we turn the array back into a list.

We can examine the execution of this procedure on an unsorted list. Note that if the list has five elements, a total of 5*4/2 = 10 loop steps are used by the bubble sort algorithm to order these elements.

BubbleSort([3,2,4,1,5]);

4.2. Merge Sort

Click here to access a summary of all the Maple code used in this section.

We now will implement the merge sort in Maple. We will also use Maple to study the complexity of this algorithm. The merge sort algorithm can be implemented as a recursive procedure. The rough outline of the task of merge sorting a list is to split the list into two list of equal, or almost equal, size, sorting each sublist using the merge sort algorithm, and then merge the resulting lists. This can be described in pseudocode as follows:

  1. Given a list of elements, if the list length is 1, return this list

  2. If the list has more than two elements, Merge sort these two lists and return the merged list of the two (as the pseudocode on page 577 of the text outlines).

First we provide a procedure, Merge, that takes two sorted lists and merges them into a single sorted list, consisting of the elements in the two lists. Here is the Maple code for the Merge procedure:

Merge := proc(L1::list, L2::list)
  local  L, i,j,k,m,n;
  L:=[]; 
  i := 1; j := 1;  k := 1;
  m := nops(L1); n := nops(L2);
  L := array(1..m+n);
  while  i <= m and j <= n  do
      if L1[i] <= L2[j] then 
          L[k] := L1[i];
    i := i+1;
  else
    L[k] := L2[j];
    j := j+1;
  fi;
  k := k+1;
   od;
   while i <= m do 
       L[k] := L1[i];
       i := i+1; k := k+1;
   od;
   while j <= n do 
       L[k] := L2[j];
       j := j+1; k := k+1;
   od;
   convert(L,list);
end:

We illustrate the use of this procedure with the following example:

Merge([1,2,6,8],[3,5,7]);

We now provide the pseudocode for the merge sort algorithm.

The description of the merge sort algorithm that we will use is based on a recursive definition. In pseudocode,

  1. If the list, L has only one element, it is sorted in order, so we return L as is.

  2. If L has more than one element, we split the lists into two lists of the same size or where the second list has exactly one more element than the first.

  3. We recursively merge sort these two lists, and merge the two sorted lists together.

MergeSort:=proc(L::list)
  local First, Second,i, n;

If the list has only one element, return it

  if nops(L) = 1 then

print(L);

    L; 
  else 

The list has more than one element print(L);

    n := nops(L);
    mid := floor(n/2);

Split the lists into two sublists of equal size

    First  := L[1..mid];
    Second := L[mid+1..n];

Merge the result of the Merge sorts of the two lists

    Merge(MergeSort(First), MergeSort(Second));
  fi;
end:

We illustrate the use of the MergeSort procedure by sorting an unsorted list with 100 elements:

MergeSort([8,2,4,6,9,7,10,1,5,3]);

We will now analyze the running time for MergeSort in relation to the running time for BubbleSort. Specifically, we will create a 10000 element unsorted list with random elements, and execute both BubbleSort and MergeSort on this list. This will provide a limited illustration of the running time of these procedure, which the reader should expand upon by reading the theoretical analysis of the text.

To create a random list of 1000 elements, we use the rand and seq commands of Maple as follows:

A:=[seq(rand(), i=1..100)]:

Then, we can use the time command to measure the amount of time required to sort the random list:

st:=time(): BubbleSort(A): time() - st;
st:=time(): MergeSort(A): time() - st;

The reader is encouraged to implement other sorting algorithms using Maple and to study the relative complexity of these algorithms when used to sort lists of various lengths. It is also interesting to use animation techniques to illustrate the steps of sorting algorithms. Although we do not do that here, the reader with advanced programming skills is invited to do so. Take special note of the importance of using the right data structure, i.e., lists versus arrays.

5. Spanning Trees

Click here to access a summary of all the Maple code used in this section.

This section explains how to use Maple to construct spanning trees for graphs and how to use spanning trees to solve many different types of problems. Spanning trees have already been used in Chapter 7; they have a myriad of applications. In particular, we will show how to use Maple to form spanning trees using two algorithms: depth-first search and breadth-first search. Then we will show how to use Maple to do backtracking, a technique based on depth-first search, to solve a variety of problems.

To begin, we will discuss how to implement depth-first search in Maple. As the name of the algorithm suggests, vertices are visited in order of increasing the depth of the spanning tree. The pseudocode is:

  1. Given a graph G, and a root vertex v, consider the first neighbor of v, called w. Add edge (v,w) to the spanning tree.

  2. Pick x to be a neighbor of w that is not in the tree. Add edge (x,w) and set w equal to x.

  3. Repeat step (2) until there are no more vertices not in the tree.

The depth first search implementation is as follows:

Depth := proc(G::graph, r)
  local v, V, N, S,In_Tree;
  new(S);
  addvertex(r, S);
  In_Tree:=[r];
  while In_Tree <>[] do
    v := In_Tree[-1];
    N:=neighbors(v, G) minus vertices(S);
    if N = {} then In_Tree := In_Tree[1..nops(In_Tree)-1]; 
        next; fi;
    addvertex(N[1],S);
    addedge([v,N[1]],S);
    In_Tree:=[op(In_Tree), N[1]];
  od;
  eval(S);
  end:

We demonstrate the usage of the depth-first search procedure with the following example:

new(G1):
addvertex(A,B,C,D,E,F,G,H,I,J,K,L,M, G1):
addedge( A,B,A,D,B,C,B,E,C,F,D,E,
   D,H,E,F,E,I,F,G,F,J,G,L,
   G,J,H,K,H,I,I,J,I,K,M, K, G1);
S1:=Depth(G1,E):
draw(Tree(E), S1);

Having implemented the depth-first spanning tree algorithm, we can now modify the Maple code slightly and get a breadth-first spanning tree. Specifically, the breadth-first search algorithm operates by examining all vertices at the current depth of the graph before moving downwards to the next level of the graph. Before implementing this algorithm, we give a pseudocode description of the algorithm.

  1. Given a graph G, and a root vertex v, identify the neighbors of v. Call this neighbor set N_1.

  2. Add edges from v to each vertex in N_1 that is not already in the spanning tree.

  3. Pick the first vertex from N_1, called w. Consider the neighbors of w; call this set of neighbors N_2.

  4. Repeat step (2) with w substituted in for v, and N_2 substituted in for N_1.

  5. If all vertices in N_1 have been exhausted, move down to the next level, and repeat step (2).

A Maple implementation is the following, called Breadth;

Breadth:=proc(G::graph, r)
  local v, N, S, In_Tree;
  new(S);
  addvertex(r, S);
  In_Tree:=[r];
  while not(In_Tree=[]) do
    v := In_Tree[1];
    N:=neighbors(In_Tree[1], G) minus vertices(S);
    for v in N do
      addvertex(v,S);
      addedge([In_Tree[1], v],S);
      In_Tree:=[op(In_Tree), v];
    od;
    In_Tree:= In_Tree[2..nops(In_Tree)];
  od;
  eval(S);
  end:
S2:=Breadth(G1, E):
draw(Tree(E), S2);

Notice that the two spanning trees are different even though they are rooted at the same vertex. In particular, the depth-first search tree has a deep and thin structure, whereas as the breadth-first search tree has a shorter and wider structure. These graphical representations help to illustrate the algorithm used, and heuristically, we can use the representations to guess whether a depth-first search or a breadth-first search has been used.

5.1. Backtracking

Click here to access a summary of all the Maple code used in this section.

Backtracking is a method that can be used to find solutions to problems that might be impractical to solve using exhaustive search techniques. Backtracking is based on the systematic search for a solution to a problem using a decision tree. (See the text for a complete discussion.) Here we show how to use backtracking to solve several different problems, including coloring a graph, solving the n-queens problem of placing n queens on a n \times n chessboard so that no queen can attack another queen, and solving the subset sum problem of finding a subset of a set of integers whose sum is a given integer.

The first problem we will attack via a backtracking procedure is the problem of coloring a graph using n colors, where n is a positive integer. Given a graph, we will attempt to color it using n colors in a greedy manner, as done in the section on Graph Coloring in the text. However, when we reach a coloring that does not allow us to color an additional vertex properly, we backtrack, changing the color on an earlier colored vertex and trying again. Here is the pseudocode for our BackColor procedure which carries out this coloring based on backtracking. Here we order the colors as color 1, color 2,..., color n.

  1. Order the vertices of the graph G as v_1, v_2,...,v_m.

  2. Assign color 1 to v_1. Set i = 2

  3. Assign color c to v_i, where c is the smallest integer so that no neighbor of v_i has been assigned color c

  4. If we can assign such a color to v_i, increment i and repeat step (3).

  5. If we cannot assign any color to v_i, we backtrack, setting i = i-1 and incrementing the color of v_i if possible.

  6. If we do not have a valid coloring, repeat step (5).

  7. Stop when we color all vertices, or we have exhausted all possible colorings.

An implementation of this pseudocode in the following Maple algorithm called BackColor:

BackColor := proc(G::graph,n::integer)
local i,k, v, V, cur_vertex, Assigned, Available,
        used , N, cur_color;
  V:= convert(vertices(G), list );

Initialize the Assigned and Available colors

  for v in V do
    Assigned(v):=0;
    Available(v):=[seq(k, k=1..n)];
  od;
  cur_vertex:=1;
  while cur_vertex >= 1 and cur_vertex <=nops(V) do
    v := V[cur_vertex];

Assign smallest color to current vertex Gather all neighbors of current vertex

    N:=neighbors(v, G);
    while Assigned(v)=0 and Available(v) <> [] do
      Used := map( Assigned , N );
      if not member( Available(v)[1], Used ) then
          Assigned(v) := Available(v)[1];
      fi;
      Available(v) := Available(v)[2..nops(Available(v))];
    od;

Backtrack if no such color exists

    if Assigned(v) = 0 and (Available(v) = []) then
      printf(`Backtracking on %a %d`,
          v, Assigned(v));
      while (Available(v)= []) and cur_vertex > 1 do
         Available(v) := [seq(k, k=1..n)];
         Assigned(v) := 0;
         cur_vertex := cur_vertex - 1;
         v := V[cur_vertex];
      od;
      if cur_vertex > 1 then 
          Assigned(v) := 0;
      else
          break;
      fi;
    else
      cur_vertex:=cur_vertex+1;
    fi;
  od;
  if not has( map( Assigned , V ), 0 ) then
    for v in V do
      printf(`Assign vertex %a color %d`, v, Assigned(v));
    od;
  else
    printf(`There does not exist a proper vertex coloring`);
    printf(`with %a colors`, n);
  fi;
end:

We will now try this implementation on a new graph called C1. Notice that the output of the BackColor procedure is the current assignment of colors at any backtracking stage, and the final coloring or indication of the non-existence of proper coloring upon termination of the procedure.

new(C1): addvertex([E,B,C,D,A], C1):
addedge(A,B,A,E,B,C,B,D,B,E,C,D,D,E,C1):
BackColor(C1,3);

Next, we will examine the execution of the BackColor procedure on C1 with two new edges added. Notice that there this new graph has K_4 as a subgraph;

addedge(A,D,A,C, C1):
BackColor(C1,3);
BackColor(C1,4);

Another problem with an elegant backtracking solution is the problem of placing n-queens on an n \times n chessboard so that no queen can attack another. This means that no two queens can be placed in the same horizontal, vertical, or diagonal line. We will solve this problem using a procedure based on backtracking. We will place queens on the chessboard in a greedy fashion, until either all the queens are placed or there is no available position for a queen to be placed without sitting on the same diagonal, vertical or horizontal line, with a queen that has already been placed.

To make the main procedure easier to understand, we will create a helper procedure that will verify whether a particular placement of queens is valid. If there are two queens on the same row, column or diagonal, then ValidQueens will return false; otherwise, the procedure will return true;

ValidQueens:=proc(Q::matrix, 
 row::integer, col::integer, size::integer)
 local i,return_value;
  return_value:=true;

Verify the dimensions are valid

  if row > size or col > size then
    return_value := false;
  else

Check Queens horizontally Note that main algorithm never places two queens in the same column, so vertical check is not needed

    for i from 1 to col-1 do
       if Q[row, i] = 1 then
         return_value:=false;
       fi;
    od;

Check Queens on the two diagonals

    for i from 1 to col-1 do
      if row>i then
        if Q[row-i, col-i] = 1 then 
          return_value:=false; 
        fi;
      fi;
      if row+i <=size then
        if Q[row+i, col-i] = 1 then 
          return_value:= false; 
        fi;
      fi;
    od;
  fi;

Return the value

  return_value;
end:

The main procedure for solving the n-queens problem, which will be called NQueens, follows the same control flow as the BackColor procedure, as can be deduced from the in-line comments. Specifically, we have an initialization stage, an incremental stage where we try to fill the current column, and a backtracking stage where we backtrack if we cannot place a queen in the current column. The Maple implementation of this procedure follows:

NQueens:=proc(n::integer)
  local cur_col, cur_row, Q, bad_position, Assigned;

Initialize Queens

  Q:=linalg[matrix](n, n, 0);
  cur_col:=1;  Assigned:=[];
  while cur_col >= 1 and cur_col <=n do

Assign a Queen to the next column

    bad_position := true;
    cur_row:=0;

does first available position work?

    while cur_row < n and bad_position do
      cur_row := cur_row+1;
      bad_position := false;

bad if there is a neighbor vertex colored

      Q[cur_row, cur_col] := 1;
      if not ValidQueens(Q, cur_row, cur_col, n) then
        bad_position := true;
        Q[cur_row, cur_col] := 0;
      fi;
    od;

Backtrack if no available Queen position

    if cur_row=n and bad_position then
      printf(`Backtracking on column`);
      printf(` %d of %a since stuck`, cur_col, Q);
      while not ValidQueens(Q, cur_row, cur_col, n) 
      and cur_col > 1 do
        cur_col := cur_col-1;
        Q[Assigned[cur_col], cur_col]:=0;
        cur_row := Assigned[cur_col] + 1;
        Assigned:=subsop(cur_col=NULL, Assigned);
      od;
      if cur_col >= 1 and cur_row <= n then
        Assigned:=[op(Assigned), cur_row];
        Q[cur_row, cur_col] := 1;
        cur_col := cur_col + 1;
      else
        cur_col := cur_col - 1;
      fi;
    else

If Queen placement is currently valid, move to the next column

      cur_col:=cur_col+1;
      Assigned:=[op(Assigned), cur_row];
    fi;
  od;
  if (cur_col >= 1) then
    printf(`A proper Queen placement is %a`, Q);
  else
    printf(`No Queen placement with %d Queens`, n);
  fi;
end:

We now use the NQueens procedure to solve the n-queens problem when n=3 and n=4;

NQueens(3);
NQueens(4);

We consider a third problem which can be solved using backtracking; the subset sum problem. Given a set of integers S, we wish to find a subset B of S such that the sum of the elements of B is a given value M. To use backtracking to solve this problem, we successively select integers from S until the sum of these elements equals M or exceeds M. If it exceeds M, we backtrack by removing the last element in the sum, and we insert a different value.

Before we implement the main procedure, we will create two small helper functions that aid in the manipulation of lists. The first helper procedure, which is called ListSum determines the sum of the elements in a given list.

ListSum:=proc(S::list, Ind::list) local i, T;
  T:=0;
  for i from 1 to nops(Ind) do
    T:=T+S[Ind[i]];
  od;
  T;
end:

The second helper function, called ListInd determines a subset of a given list S that is indicated by the positions stored in list J.

ListInd:=proc(S::list, J::list) local i, T;
  T:=[seq(S[J[i]],i=1..nops(J))];
end:

The main procedure to determine a possible solution to the subset sum problem, called SubSum, follows;

SubSum:=proc(S::list, M::integer)
  local CurSub, next_index, T, Ind, CurSum,i;

Initialize variables

  Ind:=[];
  CurSum:=0;
  i:=1;
  next_index:=0;
  T:=S;

Loop until we reach the given sum value

  while not (CurSum = M) do
    printf(`The current subset %a has sum %d`, 
           ListInd(T, Ind), CurSum);
    next_index:=next_index+1;

If we have reached an impasse, backtrack

    if next_index > nops(T) 
    and Ind[nops(Ind)] = nops(T) then
      Ind:=subsop(nops(Ind)=NULL,Ind);
      Ind:=subsop(nops(Ind)=NULL,Ind);
      CurSum:=ListSum(T, Ind);
    else

if out of values to sum, backtrack

      if next_index > nops(T)  then 
        next_index:=Ind[nops(Ind)]+1;
        Ind:=subsop(nops(Ind)=NULL, Ind);
        CurSum:=ListSum(T,Ind);
      fi;

If the current subset less than M, then we add the next value to the subset

      if CurSum+T[next_index] < M then 
        Ind:=[op(Ind), next_index ];
        CurSum:=ListSum(T, Ind);
      fi;
    fi;

If we have exhausted the index, set variables to halting values

    if Ind=[] then
      T:=subsop(1=NULL, T);
      break;
    fi;
  od;

Return the list sum

  ListInd(T,Ind);
end:

We execute this procedure on the Example 6 on page 588 of the text:

SubSum([31,27,15,11,7,5], 39);

The three problems we have attacked using backtracking, coloring graphs, the n-queens problem, and the subset sum problem are representative of the vast number of problems that can be solved using backtracking and the reader will certainly find occasions when the techniques of this section will help solve such problems. (See Exercise 7 at the end of this section, for example.)

6. Minimum Spanning Trees

Click here to access a summary of all the Maple code used in this section.

This section explains how to use Maple to find the minimum spanning tree of a weighted graph. Recall that a minimum spanning tree T of a weighted graph G is a spanning tree of G with the minimum weight of all spanning trees of G. The two best known algorithms for constructing minimum spanning trees are called Prim's and Kruskal's algorithms (although they have an older history); we will develop Maple procedures that implement both of these algorithms here.

We will begin by studying Prim's algorithm, whose pseudocode is outlined on page 594 of the text. Prim's algorithm proceeds by constructing a tree by successively selecting a minimum weight edge that extends this tree from its current set of vertices. The pseudocode is as follows:

  1. Start to build the minimum weight spanning tree T with an edge of minimum weight of the entire graph.

  2. Add to T the edge of minimum weight that is incident to a vertex in T which does not form a simple circuit in T

  3. Repeat step (2) until we have a total of n-1 edges in T

To simplify our implementation of Prim's algorithm, we first create a procedure, MinWeight, that determines the edge of minimum weight with exactly one vertex in a given set of vertices.

MinWeight:=proc(G::graph, S::set)
  local e, i, Candidates, Del, Min_Edge;

Determine the set of adjacent edges

  if S=vertices(G) then Candidates:=edges(G)
  else Candidates := incident(S,G); fi;
  if Candidates = {} then RETURN(NULL) fi;

Determine the minimum weight edge candidate

  Min_Edge:=Candidates[1];
  for e in Candidates do
    if eweight(Min_Edge,G) > eweight(e ,G) then
      Min_Edge:=e;
    fi;
  od;
  RETURN(Min_Edge);
end:

The special case of all vertices of G is included to provide a convenient starting point Prim's algorithm. In this case, we simply return the edge of G of minimum weight. In all other cases, the search is restricted to edges emanating from the subgraph induced by the specified vertices. The implementation depends on the fact that the procedure incident finds all the edges that leave a particular set of vertices. Also, the overall efficiency of the algorithm can be improved by systematically working our way through a sorted list of edges rather than searching anew for edge candidates at every step.

Given the procedure MinWeight, the actual implementation of Prim's algorithm is straightforward. we first initialize the minimum weight tree T to be the tree with just one edge, an edge of least weight. At each step we add an edge of minimum weight that incident with the current tree T.

Prim := proc(G::graph)
  local i, VT, V, T, e;
  new(T);
  V := vertices(G);

Add minimum weighted first edge

  e := MinWeight(G,V);
  addvertex(ends(e, G), T);
  addedge(ends(e,G), T);

Loop until all n-1 edges are added to tree

  for i from 2 to nops(V)-1 do
    e := MinWeight(G,vertices(T));
    if e = NULL then ERROR(`no spanning tree`) fi;

Add new vertex as well as new edge

    addvertex(ends(e,G) minus vertices(T), T);
    addedge(ends(e,G),weights=eweight(e,G),T);
  od;
  RETURN( eval(T) );
end:

We return eval(T) rather than just T to ensure that the actual tree, rather than just its name is passed back.

To test the procedure Prim we find a minimum weight spanning tree of the weighted graph from Example 1 on page 595 of the text. You can construct the graph using the commands

new(City1):
addvertex(sf,chic,den,ny,atl,City1):
addedge( [sf,ny,sf,chic,sf,den,sf, atl],
  weights=[2000,1200,900,2200], City1):
addedge( [den,chic,den,ny,den, atl],
  weights=[1300,1600,1400], City1):
addedge( [chic,ny,chic,atl, atl, ny],
  weights=[1000,700, 800], City1):

Then the minimum weight spanning tree is T1 given by

T1 := Prim(City1):

This tree is best viewed as a tree by selecting a particular root and then drawing the tree.

draw(Tree(sf), spantree(T1,sf));

The total weight of its edges can be computed as

total := 0:
for e in edges(T1) do 
  total := total + eweight(e,T1) 
od:
total;

Kruskal's algorithm algorithm builds the minimum weight tree by successively adding an edge of least weight that does not form a simple circuit in any of the previously constructed tree fragments. The psuedocode for this algorithm is:

  1. Sort the edges of the graph in ascending order.

  2. Choose smallest weight edge, e

  3. If e creates a cycle in T when added, discard e from the list and repeat step (2)

  4. Add e to the minimum weight spanning tree T

  5. Repeat step (2) until the tree has n-1 edges

Before we can implement Kruskal's algorithm, we need to be able to sort edges. As in earlier sections, we can do this using Maple's built in sorting routine by providing a suitable procedure for comparison of any two edges.

The comparison routine required here is subtly more complicated than before because it must use the graph in addition to the edge names inside the comparison. This can be accomplished using a template procedure as follows. A specific graph is substituted for a placeholder in a template.

edgecompare := proc(G::graph) 
  subs(TESTG=eval(G) , 
    proc(a,b) 
        if eweight(a,TESTG) <= eweight(b,TESTG) then
        true else false fi;
    end );
end:

By invoking this procedure on a specific graph such as City1, we create a comparison procedure customized to that graph.

comp1 := edgecompare(City1):

It can be used as

comp1(e1,e2);

Now to sort a list of the edges of City1 by weight all we need do is

edgelist := convert(edges(City1),list);
edgelist := sort(edgelist,comp1);

The weights of this sorted list are in ascending order, as verified by mapping the eweight command onto the list.

map( eweight , edgelist , City1);

Armed with this sorting routine, we are nearly ready to implement Kruskal's algorithm. At each step of the algorithm, we have an edge e, a collection of trees T, formed from edges of G, and G, and we must determine if the edge e forms a cycle. This is done by finding the components of T, and checking each component to see if both ends of the edge e are in that same component. This is accomplished by the procedure

InComponent := proc(e,T::graph,G::graph)
  local c,C;
  C := components(T);
  for c in C do
    if ends(e,G) minus c = {} then 
        RETURN(true); fi;
  od;
  RETURN(false);
end:

It makes use of the fact that the components commands represents each component by a set of vertices.

Now we are ready to implement Kruskal's algorithm.

Kruskal:=proc(G::graph)
  local E,T,i,n,e;
  E := convert( edges(G), list); # sort the edges
  E := sort( E, edgecompare(G));

start building the forest

  new(T); i := 0; n := nops(vertices(G)):
  while i < n  and E <> [] do 
    e := E[1];
    if InComponent( e , T , G ) then
       E := subs(e=NULL,E);
       next;
    fi;

add new edge to forest

    addvertex(ends(e,G),T);
    addedge(ends(e,G),T);
    i := i+1;
    E := subs(e=NULL,E);
  od;
  eval(T);  # the new tree
end:                

This algorithm can also be tested on the tree City1. from Example 1 on page 595.

T2 := Kruskal(City1):
draw(Tree(sf), spantree(T2,sf));

7. Computations and Explorations

Click here to access a summary of all the Maple code used in this section.

  1. Display all trees with six vertices

    Solution

    To solve this problem, we use a recursive definition of trees. We know that an empty graph is a tree, and that a graph with a single vertex is a tree. We can then build up larger trees from these smaller trees by taking each vertex and forming a new tree by adding a leaf connected to that vertex. (The reader can verify that this truly creates all trees with one more vertex).

    Thus, we shall create a Maple procedure, called ExtendTree, that takes a set of trees on n vertices, and adds a new edge to each tree, returning the resulting set of trees on n+1 vertices. The maple{} implementation is as follows:

    ExtendTree:=proc(Trees::set) 
      local i, j, S, t, num_vertices, X;
      S:={};

    Loop over all trees in given set

      for i to nops(Trees) do 
        T := Trees[i];

    Add new vertex

        num_vertices:=nops(vertices(T));
        addvertex(num_vertices+1, T);

    For each vertex, add new leaf edge

        for v in vertices(T) do 
          new(X[i][v]); 
          X[i][v]:=duplicate(T);
          addedge([v , num_vertices+1], X[i][v]);
          S:=S union X[i][v];
        od;
      od;
      S;
    end:

    We will now illustrate how to form all trees on 4 vertices, and leave the determination of all trees of larger size to be determined by the reader;

    new(StartingTree):
    addvertex(1, StartingTree):
    X:=ExtendTree(ExtendTree(ExtendTree(StartingTree))):
    draw(Tree(1),X[1]); 
    draw(Tree(1), X[2]): 
    draw(Tree(1),X[3]): 
    draw(Tree(1), X[4]): 
    draw(Tree(1),X[5]): 
    draw(Tree(1), X[6]):
  2. Construct a Huffman code for the letters of the English language based on the frequence of their occurrence in ordinary English text

    Solution

    This problem can be broken down into two smaller problems. The first problem is to determine how to gather the frequency of occurrence for each letter of the English language. The second problem is how to construct a Huffman code based on this frequency of occurrence.

    We already have created the Huffman procedure in Maple that can be used to determine the correct Huffman code given the frequency of occurrence of the English characters. Hence, we have solved the second problem.

    To solve the first problem, we can use Maple to scan through a string of text and count the number of occurrences of each letter of the English alphabet. Specifically, we can use strings in Maple in the following manner. Suppose that we have a passage of text which is in lower case and has no punctuation, such as:

    input_text:=
      `the quick brown fox sat down and had lunch with me`;

    Then, we can initialize a table indexed on each character of the English language, and then scan through the input_text and count the occurrence of each character.

    Initialization

    alphabet:=`a bcdefghijklmnopqrstuvwxyz`;
    for i from 1 to length(alphabet) do
      freq[substring(alphabet, i..i)]:=0;
    od:

    Count occurrence of each character

    for i from 1 to length(input_text) do
      freq[substring(input_text, i..i)] := 
           freq[substring(input_text, i..i)] + 1;
    od:
    freq[a];
    freq[e];
    freq[q];

    To determine the frequency of occurrence of English letters in certain contexts we can run this program on large sample input. We can simply extend our alphabet to include punctuation and any other special characters that are used in the character set. You will find somewhat different frequency distribution for different types of content, such as literature, correspondence, computer programs, electronic mail, and so on. It is worth noting that many books on cryptography (such as Cryptography: Theory and Practice by Douglas R. Stinson, CRC Press, 1995) contain the frequencies of characters in English, and of many other languages. Additionally, this code can be used to count frequency of occurrence of any character set, such as the ASCII character set, the French character set, the Spanish character set, and so on.

  3. Compute the number of different spanning trees of K_n for n=1,2,3,4,5,6. Conjecture a formula for the number of such spanning trees whenever n is a positive integer

    Solution

    This problem can be solved quite easily using the counttrees command of Maple, which returns the number of unique spanning trees of an undirected graph. Thus, to determine the number of unique spanning trees on K_n, n=1..6 we can execute the following Maple statements:

    counttrees(complete(1));     
    counttrees(complete(2));     
    counttrees(complete(3));     
    counttrees(complete(4));     
    counttrees(complete(5));     
    counttrees(complete(6));

    We leave it to the reader to conjecture a formula. A useful hint is to look for a formula of the form n^{f(n)}, where f(n) is a simple function in terms of n.

  4. Compute the number of different ways n queens can be arranged on an n \times n chessboard so that no two queens can attack each other for all positive integers n not exceeding 10.

    Solution

    This problem can be solved by altering the procedure NQueens that was implemented in this chapter. Specifically, when a solution is determined, rather than exiting the procedure, we simply backtrack on that solution, and continue, until all solution paths have been examined. Thus, the procedure will exit only when all solutions have been outputted. We leave it to the reader to alter the NQueens procedure and conjecture a formula for the number of solutions in terms of n for the n-queens problem.

  5. Draw the complete game tree for a game of checkers on a 4 \times 4 board.

    Solution

    We will offer a partial solution to this problem; the reader is left to complete the full solution. Specifically, we will create a Maple procedure called MovePiece that will determine all possible new checker arrangements given a specific piece that is to be moved on a given checker arrangement. Once this procedure is created, the reader must determine how to represent these board positions as vertices and edges, how to determine the next level of the game tree, as well as any necessary halting conditions.

    The implementation of MovePiece is straightforward: we examine each piece that can be moved, and then determine if we can move the piece forward and to the left or right, depending on the piece's current board position and whether there is a piece occupying a possible new position. Also, we will determine if a piece can jump and capture an opponents piece, depending on the board space and position of the opponent's positions. Additionally, we will examine whether a piece is a king, in which case, the piece can move both forwards and backwards on the checkerboard.

    We now give the Maple implementation of MovePiece. In-line comments are provided to make this code easier to understand.

    MovePiece:=proc(A::matrix, piece::integer)
      local i, j, k, cur_column, is_king, S, Temp, direction;

    Initialize values, depending on the piece value

      S:=[]; 
      if piece = 1 then direction:=-1;
      else direction:=1; fi;

    Examine all possible positions on board

      for i from 1 to 4 do
        for j from 1 to 4 do

    If we have found a piece, determine whether or not it is a King

          if abs(A[i,j])=piece then
            if A[i,j] < 0 then is_king:=1;
            else is_king:=0; fi;

    If the piece is a King, then examine both forward and reverse directions

            for k from 0 to is_king do
              if k>0 then direction:=-1*direction; fi;

    Examine possible new positions to see if they are still on the board

              if i+direction >= 1 and i+direction <= 4 then
                for cur_column from -1 to 1 by 2 do
                  if j-cur_column >=1 and j-cur_column<=4 then

    Determine if the position is free

                    if A[i+direction, j-cur_column] = 0 then

    Move a single position

                      Temp:=copy(A);
                      Temp[i,j]:=0; 
                      Temp[i+direction, j-cur_column]:=piece;
                      S:=[op(S), copy(Temp)];
                    elif abs(abs(A[i+direction,j-cur_column])
          -piece)=1 then

    We may be able to jump a piece

                      if (i+2*direction >=1 and 
          i+2*direction<=4) and 
                        (j-2*cur_column >=1 and 
          j-2*cur_column<=4) then

    Jump a piece

                         if A[i+2*direction, j-2*cur_column] 
          = 0 then             
                            Temp:=copy(A);
                            Temp[i,j]:=0; 
                            Temp[i+direction, j-cur_column]:=0;
                            Temp[i+2*direction, j-2*cur_column]
            :=piece;
                            S:=[op(S), copy(Temp)];
                         fi;
                      fi;
                    fi;
                  fi; 
                od;
              fi;
            od;
            if is_king=1 then direction:=-1*direction; fi;
          fi;
        od;
      od;

    Check for Kings

      for i from 1 to nops(S) do
        for j from 1 to 4 do
          if S[i][1,j] = 1 then S[i][1,j]:=-1 fi;
          if S[i][4,j] = 2 then S[i][4,j]:=-2 fi;
        od;
      od;

    Return list of new board arrangements

      S;
    end:

    To examine this procedure, we will create an initial checkerboard arrangement, called A, using the matrix function of Maple.

    A:=linalg[matrix](4, 4, 
     [[2,0,2,0],[0,0,0,0],[0,0,0,0],[0,1,0,1]]);

    Then, we examine the execution of this procedure on several examples:

8. Additional Exercises

  1. Using page 546 of the text as reference, write a Maple procedure for finding the eccentricity of a vertex in an unrooted tree, and for finding the center of an unrooted tree.

  2. Develop a Maple procedure for constructing rooted Fibonacci trees (see page 547 of the text)

  3. Develop a Maple procedure for listing the vertices of an ordered rooted tree in level order (see page 604 of the text)

  4. Construct a Huffman code for the letters of French, based on their occurrence in ordinary French text. The frequency of letters in French is as follows:

    E: 18%, A: 8%, I: 7%, U: 6%, O: 5%, Y: 0.2%, S: 8%, N: 8%, T: 7%, R: 7%, L: 6%, D: 4%, C: 3%, M: 3%, P: 2%, V: 2%, F: 1%, Q: 1%, G: 1%, B: 0.9%, H: 0.6%, X: 0.4%, J: 0.3%, Z: 0.06%

  5. Develop a Maple procedure for producing degree-constrained spanning trees, as outlined on page 604 of the text. Use this procedure on a set of randomly generated graphs to attempt to construct degree-constrained spanning trees where each vertex has degree no larger than 3

  6. Use Maple to analyze the game of checkers on square boards of different sizes via the technique of game trees

  7. Develop Maple procedures for finding a path through a maze using the technique of backtracking

  8. Use Maple to generate as many graceful trees as possible (see page 605 of the text). Can you make any conjectures for this evidence?

  9. Implement the quick sort in Maple.

  10. Implement the selection sort in Maple.

  11. Implement the insertion sort in Maple.

  12. Use Maple to compare the complexity of different sorting algorithms when sorting the same list of numbers for various initial lists of numbers.

  13. Alter the postfix expression evaluator to handle prefix expressions.

  14. Use Maple to animate the steps of different sorting algorithms. Specifically, show each step of the algorithm with one second pauses between movements of elements.

  15. Modify the code for Prim and Kruskal so that the edges chosen are displayed as they are selected, and compare the choices of edges.

  16. Use the procedure provided to count the frequency of occurrence of characters to determine the frequency of characters in various types of English content using relatively large sample input. For example, you might want to use electronic mail messages, computer code, newspaper articles, fiction, and so on.



spacer