Graph theory word problem


by Jamin2112
Tags: graph, theory, word
Jamin2112
Jamin2112 is offline
#1
Jul6-12, 09:14 PM
Jamin2112's Avatar
P: 864
1. The problem statement, all variables and given/known data

A house has been framed and now several jobs remain to be done. Electrical wiring must be installed, a roof must be added, drywall must be put up and it must be painted, and flooring must be installed. The electrical work must be done before the drywalling, and the drywall must be installed before it can be painted. The roof must be on the house before either flooring or painting can be done. The electrical work requires 4 units of time, roofing requires 6 units of time, and drywalling requires 3 units of time. Painting requires 5 units of time if flooring has already been installed and 3 units of time otherwise. Flooring requires 3 units of time if the walls have already been painted and 2 units of time otherwise. Draw a network showing the possible scheduling orders for different jobs.

2. Relevant equations

Def (from our course notes): A network has weights on the edges, often indicating the cost of moving from one vertex to the neighbor, e.g. the distance or driving time in the map example. A network could also be directed, for example if some routes on the map are one-way streets.

3. The attempt at a solution

I can't figure out how to capture this information in a graph with only the nodes "Start", "R", "E", "D", "F", "P", though I know that's what I'm supposed to do. Forget the weights for now; I just need to figure out how to draw the directional arrows for these 6 nodes.

The only 2 jobs that can be done first are R (roofing) and E (electrical work). So the first part of our graph should be 2 arrows pointing from Start, one to R and the other to E. We can then put an arrow from R to E, and another from E to R.

Here's where it gets tricky. Should I draw an arrow from R to D? I need to show that we can go Start-->E--->R--->D, but, from how I've drawn my graph so far, to draw an arrow from R to D would also imply that we can go Start--->R--->D, which is not possible since the drywall requires prior electrical work.

As I said before, I can't figure out how to capture this information in a graph unless. Any ideas?
Phys.Org News Partner Science news on Phys.org
SensaBubble: It's a bubble, but not as we know it (w/ video)
The hemihelix: Scientists discover a new shape using rubber bands (w/ video)
Microbes provide insights into evolution of human language
Jamin2112
Jamin2112 is offline
#2
Jul8-12, 10:32 PM
Jamin2112's Avatar
P: 864
Don't fail me now, guys
darthfunnybot
darthfunnybot is offline
#3
Jul9-12, 12:33 AM
P: 7
The point of this problem is to evaluate the most efficient (lowest time cost) path. From what i can find this problem is usually has some additional wording. Solutions are in the scroll box halfway down the page


Register to reply

Related Discussions
A problem in graph theory Calculus & Beyond Homework 1
Graph theory problem. Set Theory, Logic, Probability, Statistics 3
Area Word Problem + Graph Problem Precalculus Mathematics Homework 5
Graph Theory Problem Set Theory, Logic, Probability, Statistics 1
graph theory problem General Math 0