01 · Assignment Overview
Use one small campus network to compare edge and vertex routes, then trace a decision tree. Complete after Week 15.
Weeks 13–15
25
75–90 minutes
Instructions: Show the mathematical steps and explain each conclusion in one or two sentences. State any assumption you use. Hand reasoning and diagrams are required; Python or Colab may check a prediction but cannot replace the argument. Write your name and roll number on the first page.
Submission: One readable PDF of your own written or typed work, with pages in question order. Include diagrams and tables where requested. The instructor will announce the date and course-grade weight separately; the 25 points below describe only this assignment's internal rubric.
Assume each walkway can be traveled in both directions. Distances, closures and battery limits are not included in this mathematical model.
02 · Questions
Network data
Buildings are V={A,B,C,D}; walkways are E={AB,BC,CD,DA,AC}. Draw a square A–B–C–D–A with diagonal AC. Treat each walkway as an undirected edge.
Q1 · Every walkway once 7 points
- List the neighbors and degree of each vertex; verify the degree sum equals 2|E|. (3)
- Decide whether an Euler trail and an Euler circuit exist, using connectivity and odd degrees. (2)
- Give one route that uses every walkway exactly once; list its edges to verify no repeat. (2)
Q2 · Every building once 5 points
- Give a Hamiltonian cycle starting and ending at A and explain the return to A. (3)
- Which walkway does your cycle omit, and why does the Euler degree test not answer this vertex-once question? (2)
Q3 · Drawing and changed network 8 points
- For the original crossing-free drawing, count V,E,F (including outside) and check V−E+F=2. (4)
- Add walkway BD. Recompute degrees and decide whether an Euler trail exists; state whether the earlier Hamiltonian cycle still exists. (4)
Q4 · One path versus all-node visits 5 points
A rooted binary tree has root A, left child B and right child C. B has left D and right E. C has left child F and no right child. Draw the tree.
- Write its preorder, inorder, postorder and level-order sequences. (4)
- What is F's depth, and why is a root-to-leaf decision path different from a whole-tree traversal? (1)
03 · Submission Checklist
- Include original and changed graph drawings, plus the binary tree.
- Check route edges individually rather than stating only a route name.
- Count the outside face and distinguish Euler from Hamiltonian.
- Keep left and right child order in the four tree traversals.
Mark distribution: 7 + 5 + 8 + 5 = 25. One sentence on a physical constraint the graph ignores may be included as a reflection without extra points.