Everyday Graph Theory
Computer Science
Level
2
Consider the following problems:
- One cannot take medicine before eating, or go to play before doing his homework, etc. How should he decide the order of his chores?
- Given a list of courses and their prerequisites, create a course plan such that no course is taken before its prerequisite.
- There are a number of libraries required to install a software, but there are, in turn, another set of libraries required to install those libraries. How would a script install the entire chain?
What is the common Graph Theory theme that unites these problems?
Graph Coloring
Shortest Path
Topological Sorting
Maximum Flow
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Topological sorting is more like flowcharts, they sort the order in which jobs have to be done in a flow