MathCastle
Graph TheorySuperchallengeGraph Algorithms

Graph Algorithms · Superchallenge problem

Seven tasks 11–77 have prerequisites 1→2,1→3,1→4,2→5,3→5,3→6,4→6,5→7,6→71\to2, 1\to3, 1\to4, 2\to5, 3\to5, 3\to6, 4\to6, 5\to7, 6\to7 (the tail must be done before the head, and this forces further relations transitively). A CHAIN is a set of tasks that are pairwise forced into a specific order by these prerequisites. What is the fewest number of chains needed so that every one of the 77 tasks belongs to exactly one chain?