MA 103-005

Topics in Contemporary Mathematics

Mathematics

What You Should Be Able To Do For Test 3

Chapter 5

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.

Chapter 6

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
• Brute-Force Algorithm
• Nearest-Neighbor Algorithm
• Cheapest-Link Algorithm
(Problems 23, 25, 29, 37, 39, 45.) The Repetitive Nearest-Neighbor Algorithm takes too long for a test.

Personal Help Sheet

You may bring to the test one sheet of paper containing whatever you find helpful.

NC State home page