directed acyclic graphs directed graphs without directed cycles are encountered in many applications such directed graph is often referred to as directed acyclic graphor dagfor short applications of such graphs include the followingprerequisites between courses of degree program inheritance between classes of an object-oriented program scheduling constraints between the tasks of project we explore this latter application further in the following exampleexample in order to manage large projectit is convenient to break it up into collection of smaller tasks the taskshoweverare rarely independentbecause scheduling constraints exist between them (for examplein house building projectthe task of ordering nails obviously precedes the task of nailing shingles to the roof deck clearlyscheduling constraints cannot have circularitiesbecause they would make the project impossible (for examplein order to get job you need to have work experiencebut in order to get work experience you need to have job the scheduling constraints impose restrictions on the order in which the tasks can be executed namelyif constraint says that task must be completed before task is startedthen must precede in the order of execution of the tasks thusif we model feasible set of tasks as vertices of directed graphand we place directed edge from to whenever the task for must be executed before the task for vthen we define directed acyclic graph topological ordering be directed graph the example above motivates the following definition let with vertices topological ordering of is an ordering ,vn of the vertices it is the case that that isa toposuch that for every edge (vi of gof traverses vertices in logical ordering is an ordering such that any directed path in increasing order note that directed graph may have more than one topological ordering (see figure has topological ordering if and only if it is acyclic proposition justificationthe necessity (the "only ifpart of the statementis easy to is topologically ordered assumefor the sake of condemonstrate suppose tradictionthat has cycle consisting of edges (vi vi )(vi vi ),(vik- vi because of the topological orderingwe must have ik- which must be acyclic is clearly impossible thusg