Texas A&M University-Corpus Christi / Dept. of Computing and Mathematical Sciences

MATH 2305 §002 -- Discrete Mathematics I -- Spring 2003

Chapter 5 Study Questions

Section 5.1 Graphs and Their Representations-- Name:

  1. A graph is just a set of points.
  2. An arc in a graph is determined by the two nodes it connects.
  3. Hasse diagrams (graphical representations of partially ordered sets) are graphs.
  4. The graph K_4 (Example 8) has 4 vertices and 4 edges.
  5. Every acyclic graph is simple.
  6. Two graphs can be isomorphic if one graph is connected and the other is not.
  7. Graphs can only be represented by diagrams.

 

Section 5.2 Trees and Their Representations -- Name:

  1. Trees have roots.
  2. Trees were used to solve counting problems in Chapter 3.
  3. Every node in a tree has the same number of branches.
  4. For a binary tree, postorder traversal is left, right, root.
  5. Postfix notation is called reverse Polish notation.
  6. Trees have more arcs than nodes.

 

Section 5.3 Decision Trees -- Name:

  1. In a decision tree, arcs represent actions and nodes are the outcomes.
  2. A sequential search of an n item list may require log n steps.
  3. A binary search tree is always short and wide (balanced) rather than tall and skinny.
  4. Trees can be used for sorting as well as searching.
  5. Sorting a 3 item list by pairwise comparisions requires three steps.