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.
- Is there a name for this algorithm, so that I can look up more information?
- 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.