MATtours of discrete mathematics

Order-requirement networks

An order-requirement network is a weighted digraph, or network, that has these characteristics:

It contains two special vertices, the starting vertex and the terminating vertex. They are usually designated by S and T. These vertices are sometimes also called the source and the sink. No edges end at the source; no edges begin at the sink. In other words, the indegree of the source and the outdegree of the sink are 0.
Every vertex in the network is on a (directed) path from S to T.

Order-requirement networks are used primarily to represent sets of tasks that make up a job. The tasks are represented by vertices; an arrow from one vertex to another represents the fact that the task represented by the first vertex must be completed before the task represented by the second vertex can be started. For that reason, in an order-requirement network, if a directed edge points from vertex U to vertex V, then U is said to be a prerequisite, or predecessor, of V, and V is a successor of U.

A critical path of the network is a path of greatest length from S to T. The length of this path is called the earliest finish time, or EFT, of the network. The Critical Path Method, or CPM, is an algorithm for finding a critical path of an order-requirement network. It relies on finding the length of the longest path from S to each vertex. That length is known as the EFT of the vertex.