Задача 116441

Темы:    [ Теория графов (прочее) ] [ Классическая комбинаторика (прочее) ] [ Примеры и контрпримеры. Конструкции ]

Сложность: 3+ Классы: 9,10,11

Условие

Автор: Фольклор

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

Решение

  Оценка. Из фиксированного города А можно попасть напрямую не более чем в три города, а с одной пересадкой – еще не более чем в  3·2 = 6  городов. Таким образом, всего городов может быть не более десяти.
  Пример сети из 10 городов см. на рисунке.

Ответ

10.

Замечания

1. Приведённый граф называется графом Петерсена и служит иллюстрацией некоторых утверждений теории графов.

2. Ср. с задачей 78596.

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

олимпиада
Название	Московская математическая регата
год
Год	2011/12
Класс
	1
Класс	11
задача
Номер	11.4.3