Unit 7: Trees - Assignment
Part I. Basic Computations
1. Using the following tree, name two vertices that are considered the following. Explain in your own words how you know: (a) parent-child (2 points).
Answer: 202 - 401
Explanation: the parent of a vertex is the vertex connected to it on the path to the root, 202 is the parent and 401 is the child
(b) sibling nodes (2 points):
Answer: 301, 302, 303
Explanation: If two vertices are children of the same parent, then these two vertices are called siblings, 301, 302, 303 have the same parent that is 201
(c) leaf nodes (2 points)
Answer: 301, 302, 303, 401
Explanation: the leaves are all terminal vertices
2. Determine if each of the following graphs is considered a tree. Explain why or why not, using what you learned in this unit. a. (2 points) Answer: not a tree
Explanation: A tree is a connected graph with no cycles, and there is cycles in this graph
b. (2 points) Answer: yes
Explanation: A tree is a connected graph with no cycles, and there is no cycles in this graph
c. (1 point) Answer: no
Explanation: A tree is a connected graph with no cycles, and there a cycle in this graph
3. Determine and sketch two different spanning trees for this graph:
a. (1 point) b. (1 point)
4. Consider this graph:
a. Determine the total weight for this graph. Show your work. (1 point)
Answer: 122
Explanation: 5 + 10 +5 +10 +17 +15 + 5 +4+4+8+5+6+13+7+8
b. Draw one spanning tree for this weighted graph and determine its weight. Show your work. (1 point)
[Hint: One way to do this is to make a copy of the graph using cut/paste, then show your spanning tree.]
Answer:
Total weight:
Part II. Case Study The Case of the Yip-it-tee DooDahs
This week, the cast and crew of the “Patty Madeye Mysteries” will be filming on-location at the Yip-it-tee Amusement Park. The episode will be centered around a gang of purse-snatchers (they call them selves the “Doodahs”) who prey on vistors at the Yip-it-tee Amusement Park. While customers are having fun on the water rides, the purse-snatchers help themselves to any valuables that are left behind.
The park owner has provided a detailed map of the amusement park.
• The Entrance Gate is identified by the little house (location H)
• Numbered locations identify the 7 rides in the park (see legend at the bottom)
• Food Stands are identified by the “hamburger” icons (A, C, D, F)
• Restrooms are identified as locations G, B, and E
• The Storage and Maintenance Facility is identified as location S.
• The distance between each of the 16 locations is measured in meters and listed in green letters.
Task #1: (4 points) The first scene of the episode will be focused on ride #6 (Wippee Water Slide). Your first task is to sketch a binary spanning tree (that would be a spanning tree in which each parent has no more than 2 children) using the locations as vertices and the paths as edges. Use location 6 (Wippee Water Slide) as the root of the tree.
[Hint: Remember that all 16 locations must be included somewhere in your tree.]
Answer:
Task #2. (4 points) Your next task is to describe for Patty and the filming crew all the available paths from the Entrance (Location H). Sketch a spanning tree (it does not have to be a binary tree) using Location H as the root.
Answer:
Task #3. (4 points) Determine whether it is possible to visit each of the 16 locations on this map without retracing your steps on any given path. If so, describe the path below. If not, explain how you know that such a path is not possible.
Answer:
Task #4. (8 points) The crew will need to lay cable along the paths of the park so that they can film in each of the 16 locations. Your next task is to use a minimum spanning tree to determine how much cable the film crew will need to use. Sketch the tree and compute the total weight of the tree, using the distances indicated on the graph. Answer: 