# Algorithm for constructing a numbering reflecting the order of activities

I'm following a book about graphs and they introduce a concept called 'activity network'. In an activity network, each vertex represents an activity in a project (like building a house for example) that needs to be done. An arc between two activities $$uv$$ means $$u$$ needs to be done before $$v$$ and the weight of the arc represents the duration it takes to complete $$u$$.

A given activity network could look like this:

• $$A$$: Foundation, duration: 7 days
• $$B$$: Door frames, duration 2 days
• $$C$$: Put in walls, 10 days, depends on $$A$$, $$B$$
• ...

Based on this, we can draw the graph of the activity network, satisfying the precendence relations.

The book introduces a way to number the vertices in the network in such a way that the precedence relations are satisfied.

A good numbering in this case would be $$A \mapsto 1, B \mapsto 2, C \mapsto 3$$. What would not be possible is to number $$C$$ as $$1$$, since $$C$$ depends on $$A, B$$.

The book uses the following algorithm:

• Represent each activity as a vertex. For each vertex, create a shadow vertex.
• Construct a bipartite graph in which one set of vertices consists of the original vertices and the other set cosnstis of the shadow vertices.
• If an activity $$Y$$ depends on $$X$$, then draw an edge joining $$Y$$ to the shadow vertex of $$X$$.
• Number all the original vertices without edges.
• Delete all numbered vertices and their corresponding shadow vertices.
• Continue until all vertices are numbered.

Besides the description and some examples, the book doesn't contain any more details.

1. Is there a name for this algorithm, so that I can look up more information?
2. In particular, why does the usage of a bipartite graph necessarily result in a good numbering?

The book remarks that this algorithm was developed by Fulkerson. Tried to search for it, but mainly his network flow algorithms came up.