Задача 78653

Темы:    [ Связность и разложение на связные компоненты ] [ Примеры и контрпримеры. Конструкции ]

Сложность: 3 Классы: 8,9

Условие

Как соединить 50 городов наименьшим числом авиалиний так, чтобы из каждого города можно было попасть в любой, сделав не более двух пересадок?

Решение

  Выделим один город и соединим его авиалинией с каждым из остальных 49 городов. Для этого потребуется 49 авиалиний.
  Меньшим числом авиалиний обойтись нельзя. Действительно, согласно задаче 31098 г) в связном графе с 50 вершинами не менее 49 рёбер.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	31
Год	1968
вариант
	1
Класс	7
Тур	1
задача
Номер	4