Unit 6 Graph Theory Assignment Total Points

Unit 6 Graph Theory Assignmenttotal Points For Assignment

Identify the core assignment tasks from the provided instructions, removing any extraneous information such as grading rubrics, submission guidelines, and meta-instructions. Focus solely on the actual questions and the essential context needed to complete the assignment.

Paper For Above instruction

Part I. Basic Computations

1. The plan for a four-room house is shown below. Draw a graph that models the connecting relationships between the areas in the floor plan. Answer:

2. a. Identify all the vertices in the above graph with odd degree and the degree of each. Answer:

b. Describe two paths of different lengths starting at vertex A and ending at vertex F, specifying their lengths. Answer:

c. Describe a circuit of length 3. Answer:

d. Describe two different circuits of length 4. Answer:

3. Consider this graph:

a. Find an Euler circuit in this graph that starts and ends at vertex D. Answer:

b. Explain how you know that this graph has an Euler Circuit using Euler’s Rules. Answer:

4. Paths in a zoo are depicted on a map. To see every exhibit exactly once without retracing steps:

a. Where should you begin and end? Explain. Answer:

b. Find a path with no retracing. Answer:

Part II. Case Study – The Case of the Missing Cookies

1. The camp director needs to search along each path starting and ending at her office, only traveling each trail once. Can you determine such a path? If so, describe it. If not, explain why and suggest an alternative path. Answer:

2. The camp director’s house is connected by rooms and doors. Draw a graph showing these relationships. Answer:

3. Find a method for her to search each door without retracing steps. If possible, describe the path; if not, explain why. Answer:

4. Research graph theory applications beyond those in the course. Present one specific real-world application, explain its use, and include a concrete example. Answer:

References

  • Diestel, R. (2017). Graph Theory (5th ed.). Springer.
  • Biggs, N. (1993). Algebraic Graph Theory. Cambridge University Press.
  • West, D. B. (2001). Introduction to Graph Theory (2nd ed.). Prentice Hall.
  • Harary, F. (1969). Graph Theory. Addison-Wesley.
  • Gross, J. L., & Yellen, J. (2005). Graph Theory and Its Applications. CRC Press.
  • Reingold, E. M., & Tilford, J. (2002). Graph Drawing. Journal of Graph Algorithms and Applications.
  • West, D. B. (2000). Introduction to Graph Theory (2nd ed.). Prentice Hall.
  • Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory with Applications. Elsevier.
  • Deo, N. (1974). Graph Theory with Applications to Engineering and Computer Science. Prentice Hall.
  • Kleinberg, J., & Tardos, É. (2006). Algorithm Design. Pearson.

Related Assignments