Topics in Contemporary Mathematics
What You Should Be Able To Do For Test 3
Draw a graph from a description, explain why two pictures represent the same graph (problems 3 and 5).
Know the meaning of terms like degree of a vertex, loop, path, circuit, bridge. I will not ask you to construct examples of graphs with certain properties (problems 7, 9). I might ask you to find a bridge or a loop or a path or a circuit in a graph (problems 11a, b, 13a, c). I might ask you to find all circuits that start at A or all paths from A to B (problems 11 c, d, e, 13 b).
Determine if a graph has an Euler circuit or an Euler path by looking at degrees of the vertices (problems 23, 25).
If a graph has an Euler path or Euler circuit, find one using Fleury's algorithm (problems 29, 30, 33, 35, 36).
Find optimal Eulerizations (problems 41, 42).
Applications like problems 15, 17, 19, 51, 53, 60, 63.
Find Hamilton circuits in a graph (problems 1, 3, 7, 8). If I ask for "all" I'll keep it simple. But: you should be able to list all Hamilton circuits in a complete graph (a small one, of course).
Find the number of edges and Hamilton circuits in a complete graph (problem 19).
Find optimal Hamilton circuits using
(Problems 23, 25, 29, 37, 39, 45.) The Repetitive Nearest-Neighbor Algorithm takes too long for a test.
- Brute-Force Algorithm
- Nearest-Neighbor Algorithm
- Cheapest-Link Algorithm
Personal Help Sheet
You may bring to the test one sheet of paper containing whatever you find helpful.
MA 103-005 home page
Test study guides
NC State home page
Last modified Thu Oct 17 2002
Send questions or comments to firstname.lastname@example.org