Getting Started with Competitive Programming
(an NPTEL course)
Module A. Prerequisites
The lectures for this week are largely self-contained, and the pre-requisites are mostly the topics you have already seen in Weeks 5, 6, 7, and 8.
Here's a little bit of a historical perspective too:
Suppose you have a network of railroads and you want to transport trains from an origin station to a different station that we'll call the destination station. There are some intermediate stations in between connected via a railroad track. To avoid collisions, trains can only travel in one direction between any two stations.
The original inspiration for studying these questions comes from the Cold War. During the Cold War, the US military was interested in the Soviet Union Railway System that connected the Western Soviet Union to Eastern Europe, in particular East Germany. They were interested in knowing what was the minimum number of places on the railroad system they could bomb that would completely and accurately prevent movement between the Soviet Union and Eastern Europe.
Oh well. 😬