Mid-Term Exam #1

The first mid-term exam will cover the content from Chapters 5 and 6 from the book as well as the new material on games on graphs.

Specific topics for the exam may include the following:

Chapter 5 Material

• Given a vertex and edge set, draw the graph.
• Given a graph, find the vertex and edge sets.
• Find the degree of a vertex.
• Know the difference between a path and a circuit.
• Know the difference between a path and an Euler path.
• Know the difference between a circuit and an Euler circuit.
• Know how to determine if a graph contains an Euler path or an Euler circuit (application of Euler Circuit/Path theorems).

Chapter 6 Material

• Know the difference between a Hamilton path and a Hamilton circuit.
• Know the definition of the factorial.  For example, 3! = 3*2*1 = 6.
• Know how to simplify expressions containing factorials.  
• Know what a complete graph with N vertices means, and know the notation K_n.
• Given the graph K_n, know 
  • the formula for the degree of each vertex.
  • the formula for the number edges.
  • the formula for the number of Hamilton Paths.
  • the formula for the number of Hamilton Circuits.
• Know the following algorithms for finding the optimal solution to the traveling salesman problem:
  • Brute force
  • Nearest Neighbor (and repetitive nearest neighbor)
  • Cheapest link
• Know how to calculate the relative error.

‘Games on Graphs’ Material

• Know the mechanics of an irreversible k-threshold process.
• Given a graph and the initial outbreak location(s), know how to ‘simulate’ the spread of a disease through the network.
• Know how to calculate the survival and mortality percentages.
• Know how to include a vaccination strategy in the model.