I´m looking for some good and clear example/s about using graph theory in scheduling. (I´m interested in good books/web/PDF in this way)

My target is to show the utility of graph theory to some people in a little college/academy.

Thank you.

  • 1
    $\begingroup$ Welcome to the site! Could you say a little more about the context? What is the background of the people? How much time do you have? $\endgroup$ – quid Sep 30 '15 at 13:30
  • $\begingroup$ @quid The background is a graduated math, but what I´m looking for is simple examples of aplications to understand the use of graphs apllied to the scheduling, not theorems or similar. $\endgroup$ – Mika Ike Oct 2 '15 at 5:19
  • $\begingroup$ Thanks for the reply. Please include this additional information via an edit in the post, and possibly still more details. How much graph theory do those people know for instance? As you see the question seems too broad as it is. $\endgroup$ – quid Oct 2 '15 at 10:39

You might try getting the students to understand Braess's Paradox, which can be phrased as a paradox about traffic flow, modeled by a weighted graph. The paradox is that the addition of a "short cut" road leads, under individual rational behavior by each driver, to everyone taking longer to reach their destination.


The above image is from: Frank Kelly. "The mathematics of traffic in networks." The Princeton Companion to Mathematics (2008). (PDF download link.)

The Wikipedia example might be even clearer for your purposes, because it is phrased without mentioning "Wardrop equilibrium."

| improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.