During the construction of a house there are certain tasks that have to be compl

Question

During the construction of a house 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? By analyzing the graph model, how can we find tasks that can be done at any time? Knowing the amount of time that each task takes, what do we need to compute to find the minimum length of time necessary to build the whole house (assuming enough resources are always available)?

Please write out work

Explanation / Answer

Construction of house can be modelled using graph

where each vertex coresponds to task

Edges should be directed

where direction of edge tells the order of connecting vertices(tasks)

The vertices which are not connected by edges to any other vertices( isolated vertices) are the tasks which can be done any time as no other task is dependent on the and these are not dependent on any of them

Minimum time needed to construct the house can be find using shortest spanning tree alogorithm( )

where A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges

Minimum time to construct the house will be Max (max time of all isolated tasks,minimum spannin tree)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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