Между некоторыми из 2n городов установлено воздушное сообщение, причём каждый город связан (беспосадочными рейсами) не менее чем с n другими.
  а) Докажите, что если отменить любые  n – 1  рейсов, то всё равно из любого города можно добраться в любой другой на самолётах (с пересадками).
  б) Укажите все случаи, когда связность нарушается при отмене n рейсов.

   Решение

Страница: 1 [Всего задач: 1]      

Между некоторыми из 2n городов установлено воздушное сообщение, причём каждый город связан (беспосадочными рейсами) не менее чем с n другими.
  а) Докажите, что если отменить любые  n – 1  рейсов, то всё равно из любого города можно добраться в любой другой на самолётах (с пересадками).
  б) Укажите все случаи, когда связность нарушается при отмене n рейсов.

Прислать комментарий

Решение

Страница: 1 [Всего задач: 1]