Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Graph theory word problem

  1. Jul 6, 2012 #1
    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?
  2. jcsd
  3. Jul 8, 2012 #2
    Don't fail me now, guys
  4. Jul 9, 2012 #3
    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook