Question

У деякому місті з будь-якої станції метро можна доїхати до будь-якої іншої станції (можливо, з пересадками). Доведіть, що існує станція, яку можна закрити (без права проїзду через неї), і при цьому з будь-якої станції з тих, що залишилися, можна буде доїхати до будь-якої іншої.

Answer 1

Відповідь:

Щоб доїхати з будь-якої станції метро до будь-якої іншої (можливо, з пересадками), зв'язки (тобто рейкові колії) між станціями будуються таким чином, що є щонайменше дві станції (A1, An), в яких сходяться три колії в кільцевому та радіальних напрямах (зі станцій, приміром, Аі, Ві і Сі чи зі станцій Аі, Ві та Сі). При закритті будь-якої зі станцій (А1 чи Аn) залишаються вільними дві колії, якими можна доїхати до будь-якої станції (приміром, при закритті А1 зі станції В1 до станції С1 через Аі або (при закритті Аn) зі станції Ві до станції C1 через А2). Аналогічно розглядаються випадки при закритті будь-якої станції метро на кільцевому чи радіальних напрямах.