Chapter ObjeCtives
After studying this chapter, you will be able to:
• Understand and use the many terms associated with graphs, directed graphs,
and trees.
• Appreciate the use of graphs, directed graphs, and trees as representation tools
in a wide variety of contexts.
• Prove that two given graphs are isomorphic or give a reason why they are not.
• Use Euler’s formula for a simple, connected, planar graph.
• Understand the role of the two specific graphs K 5 and K 3,3 in graph planarity.
• Prove elementary properties about graphs and trees.
• Use adjacency matrix and adjacency list representations for graphs and directed
graphs.
• Do preorder, inorder, and postorder tree traversal.
• Use array and pointer representations for binary trees.
• Use decision trees to represent the steps a searching or sorting algorithm carries out.
• Build a binary search tree and conduct a binary tree search.
• Express lower bounds on the worst-case number of comparisons for searching
or sorting on a list with n elements.
• Find Huffman codes for characters whose frequency of occurrence is given.
You work in the Information Systems Department at World Wide Widgets (WWW), the
leading widget manufacturer. Widgets are extremely complex devices made up of an
enormous number of very simple parts. Each part is one of the following types: Bolt
(B), Component (C), Gear (G), Rod (R), or Screw (S). There are many different variations of each basic type. Part numbers consist of a leading character B, C, G, R, or S
to identify the part type, followed by an 8-digit number. Thus
C00347289
B11872432
S45003781
are all legitimate part numbers. Using the multiplication principle, there are 5 × 10
8
different potential part numbers! WWW maintains a data file of the part numbers
it uses, which, as it turns out, is most of the potential numbers. Most computers,
6 6
Graphs and Trees
C h a p t e r
475
After studying this chapter, you will be able to:
• Understand and use the many terms associated with graphs, directed graphs,
and trees.
• Appreciate the use of graphs, directed graphs, and trees as representation tools
in a wide variety of contexts.
• Prove that two given graphs are isomorphic or give a reason why they are not.
• Use Euler’s formula for a simple, connected, planar graph.
• Understand the role of the two specific graphs K 5 and K 3,3 in graph planarity.
• Prove elementary properties about graphs and trees.
• Use adjacency matrix and adjacency list representations for graphs and directed
graphs.
• Do preorder, inorder, and postorder tree traversal.
• Use array and pointer representations for binary trees.
• Use decision trees to represent the steps a searching or sorting algorithm carries out.
• Build a binary search tree and conduct a binary tree search.
• Express lower bounds on the worst-case number of comparisons for searching
or sorting on a list with n elements.
• Find Huffman codes for characters whose frequency of occurrence is given.
You work in the Information Systems Department at World Wide Widgets (WWW), the
leading widget manufacturer. Widgets are extremely complex devices made up of an
enormous number of very simple parts. Each part is one of the following types: Bolt
(B), Component (C), Gear (G), Rod (R), or Screw (S). There are many different variations of each basic type. Part numbers consist of a leading character B, C, G, R, or S
to identify the part type, followed by an 8-digit number. Thus
C00347289
B11872432
S45003781
are all legitimate part numbers. Using the multiplication principle, there are 5 × 10
8
different potential part numbers! WWW maintains a data file of the part numbers
it uses, which, as it turns out, is most of the potential numbers. Most computers,
6 6
Graphs and Trees
C h a p t e r
475