MathDB
metro network with n stations

Source: Portugal OPM 2019 p6

May 15, 2024
combinatorics

Problem Statement

A metro network with n2n \ge 2 stations, where each station is connected to each of the others by a one-way line, is said to be dispersed i f there are two stations AA and BB such that it is not possible to go from AA to BB through is from the network. If a network is dispersed, but it is possible to choose a station AA and reverse the direction of all lines to and from AA so that the new network is no longer dispersed, the network is said to be correctable. Indicates all integers nn for which there is a network with nn stations, dispersed and not correctable.