THERE WILL BE CHOICES ON THE EXAM
Although there are choices, you will definitely have to choose some graph and/or tree problems and combinatorics problems!
Be sure to go over the problems assigned with each chapter; see the Web pages for problem numbers.
Reminder of subject-matter to be covered:
Here are the types of tree and graph problems that may be on the exam:
1. Recognize a cycle(or circuit) in a graph or give an example of one.
2. Know what Euler circuits are. Be able to determine if a graph has an Euler circuit; if not,
say why not; if so, find an Euler circuit.
3. Be able to define the components of a tree (root, terminating vertex,
interior vertex) and identify the level of a vertex and the height of a tree.
4. Know the diference between "free" trees (as special types of graphs)
and "rooted" trees.
Here are some possibilities for questions on old material (in addition to the
assigned problems):
A mathematical induction proof (yes again).
Give examples of relations having some or all of the 3 properties we studied:
Be sure you understand equivalence relations and partial orders.
Counting, Permutations and Combinations: be able to solve problems about orderings
of a sequence, both when there are no repetitions in the sequence (ABCDE) or when
there are repetitions (MISSISSIPPI); selecting some number of elements out of a set;
and picking some number of elements, some of which may be duplicates, out of a jar
(alternatively, classifying elements into groups).