Graph Theory and Travelling Salesman Problem worksheet.docx

Module 05 Content

1. 
   
   1. Looking at the graph above, answer the following:
   a. Identify the number of odd vertices.
   b. Identify the number of even vertices.
   c. Does it have a Euler circuit? Does it have a Euler path? Explain your answers
   
   
   
   
   2. Looking at the graph above, answer the following:
   a. Identify the number of odd vertices.
   b. Identify the number of even vertices.
   c. Does it have a Euler circuit? Does it have a Euler path? Explain your answers.
   
   
   
   
   
   
   3. Find 3 different Hamilton circuits in the graph above
   
   
   
   
   
   
   4. How many distinct Hamilton circuits does the graph above have? List them using A as the starting vertex.
   
   
   5. How many edges are in K17, the complete graph with 17 vertices?
   
   
   6. Explain why the graph below has no Hamilton circuit but does have a Hamilton path
   
   
   
   
   
   
   
   
   Submit your answers to the questions above by downloading and completing the Graph Theory and Travelling Salesman Problem worksheet.