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?

Explanation / Answer

Graphs are mathematical objects that can be used to study relationships between objects, locations or events to mention some examples.

In this question, if we want to understand the relationship between the different tasks that can be done while constructing a house we can use a graph with directed edges. Where node A is connected by an edge pointing to node B if and only if the event A has to take place before event B. We say the edge starts on A and ends in B.

In the example above, a node labeled ' Construct roof ' will have an edge pointing to the node labeled ' Electrical wiring ' since the roof has to be installed before any lectrical wiring can take place. The more apropriate graph to use is then a directed one.

By looking at the graph model we can decide that if a node has no edges ending in it, then the task has no necessary previous actions to allow us to do it. Hence the task can be done at any time.

On the other hand if a node has no edges starting on it, that means the task it represents does not have to be completed before other actions can take place. It is not a prerequisite of any task.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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