During the construction of a home there are certain tasks that have to be comple

Question

During the construction of a home there are certain tasks that have to be completed before another one can commence, e.g., the roof has to be installed before the work on electrical wiring or plumbing can begin. How can a graph be used to model the different tasks during the construction? Should the edges be directed or undirected? Looking at the graph model, how can we find tasks that can be done at any time and how can we find tasks that do not have to be completed before other tasks can begin? 8. Many supermarkets use loyalty or discount cards to keep track of who buys which items. How can graphs be used to model this relationship? Should the edges be directed or undirected? Should multiple edges be allowed? Should loops be allowed? Does this graph have any special properties? Use Dikjstra's algorithm to find the shortest path, and its corresponding length, between vertices a and z. Show all the work

Explanation / Answer

8. Ans- We will have a nodes for each customer and nodes for each item. There exists an edge from customer node to item node if the customer buys that item. Each customer can buy an item only once(not the quantity). So multiple edges are not allowed. There does not exist any loops in the graph. All edges must be undirected. The graph can be bipartited into two sets of nodes with customers in one set and items in other set.

9. Dikjstra's algorithm follows the path from a->b->d->z . The total path length will be 3+2+4=9.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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