Задача 32996

Тема:    [ Теория графов (прочее) ]

Сложность: 2 Классы: 8

Условие

Несколько Совершенно Секретных Объектов соединены подземной железной дорогой таким образом, что каждый Объект напрямую соединён не более чем с тремя другими и от каждого Объекта можно добраться под землей до любого другого, сделав не более одной пересадки. Каково максимальное число Совершенно Секретных Объектов?

Решение

  Оценка. Из данного Объекта можно добраться за один "ход" до трёх Объектов, а с пересадкой – еще до  2·3 = 6  Объектов. Следовательно, Объектов не больше 10.
  Пример с 10 Объектами изображен на рисунке.

Ответ

10.

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

Кружок
Название	ВМШ 57 школы
класс
Класс	8
год
Год	1997/98
Место проведения	57 школа
занятие
Номер	9
Название	Графы
Тема	Неизвестная тема
задача
Номер	06