Problem D: I wish to model the following word problem as a graph problem: The Ma

Question

Problem D: I wish to model the following word problem as a graph problem: The Maytag repairman has been called to repair washers and dryers at several customer’s homes. Assume travel times between locations are known. The repairman starts and ends his day at his home, and would like to complete his work as quickly as possible.

(a). What do the nodes of the graph to be constructed represent?
(b). What do the edges of the graph to be constructed represent?
(c). State which graph problem it is: Shortest path, Minimum spanning tree, Traveling Salesman Problem, Breadth or Depth First Search.

Explanation / Answer

a) The nodes or the vertices of the graph must be the houses of the customers the repairman ought to visit. The repairman's home must also be a node.

b) The edges shall represent the possible paths between each node(customers)

c)This is Traveling salesman problem.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.