How can the sequence of tasks be represented in a graph using only 6 nodes?

In summary, the 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
  • #1
Jamin2112
986
12

Homework Statement



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.

Homework 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.

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?
 
Physics news on Phys.org
  • #2
Don't fail me now, guys
 
  • #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
 

FAQ: How can the sequence of tasks be represented in a graph using only 6 nodes?

1. What is graph theory?

Graph theory is a branch of mathematics that deals with the study of graphs, which are mathematical structures used to model pairwise relations between objects. It has applications in various fields such as computer science, engineering, and social sciences.

2. What is a word problem in graph theory?

A word problem in graph theory is a problem that involves setting up and solving a graph-based scenario, typically using real-world examples. These problems require the use of graph theory concepts such as vertices, edges, paths, and cycles to find a solution.

3. How do I approach solving a graph theory word problem?

To solve a graph theory word problem, you can follow these steps: 1. Read the problem carefully and identify the given information.2. Draw a visual representation of the problem using a graph.3. Determine the type of graph (e.g. directed, undirected, weighted) and the appropriate graph theory concepts to use.4. Apply the necessary formulas and algorithms to solve the problem.5. Check your solution for accuracy and make any necessary adjustments.

4. What are some real-life applications of graph theory?

Graph theory has various real-life applications such as:- Social networks: Graph theory is used to analyze and model connections between individuals in social networks.- Transport networks: Graph theory is used to optimize transportation routes and schedules in public transport systems.- Telecommunications: Graph theory is used to design efficient routing algorithms for telephone and internet networks.- Biology: Graph theory is used to study the structure of protein molecules and genetic networks.- Computer networks: Graph theory is used to analyze and troubleshoot computer networks.

5. Are there any common pitfalls when solving graph theory word problems?

Some common pitfalls to avoid when solving graph theory word problems include:- Misinterpreting the given information and drawing an incorrect graph.- Using the wrong graph theory concepts or formulas.- Forgetting to consider edge cases or special scenarios.- Making computational errors.- Not checking the solution for accuracy.

Back
Top