MathCastle
Graph TheoryChallengeGraph Algorithms

Graph Algorithms · Challenge problem

A project's activities are arcs in a directed network from start event 11 to finish event 77: 1→2:5,1→3:3,1→4:6,2→5:4,3→5:7,3→6:5,4→6:2,5→7:3,6→7:61\to2{:}5, 1\to3{:}3, 1\to4{:}6, 2\to5{:}4, 3\to5{:}7, 3\to6{:}5, 4\to6{:}2, 5\to7{:}3, 6\to7{:}6 (days). Every activity leaving an event can start only once ALL activities entering that event are finished, and the project takes as long as its critical (longest) path, which is 1414 days. Activity 2→52\to5 is NOT on the critical path. By how many days could activity 2→52\to5 be delayed (started late) without delaying the project's overall finish time?