Разделы 
Дополнительно
Задача по математике - 3645
2019-06-13 
В некотором государстве система авиалиний устроена таким образом, что любой город соединен авиалиниями не более чем с тремя другими и из любого города в любой другой можно проехать, сделав не более одной пересадки.
Какое максимальное число городов может быть в этом государстве?
Решение:
Из любого города $A$ можно добраться не более чем до трех городов, а из каждого из них не более, чем до двух (не считая $A$). Таким образом, всего городов не более $1 + 3 + 3 - 2 = 10$.
Пример на рис. показывает, что нужная система авиалиний в государстве с десятью городами существует.
Граф на рис. часто используется в качестве примера и даже имеет специальное название "граф Петерсена".
Ответ: 10 городов.
В некотором государстве система авиалиний устроена таким образом, что любой город соединен авиалиниями не более чем с тремя другими и из любого города в любой другой можно проехать, сделав не более одной пересадки.
Какое максимальное число городов может быть в этом государстве?
Решение:
Из любого города $A$ можно добраться не более чем до трех городов, а из каждого из них не более, чем до двух (не считая $A$). Таким образом, всего городов не более $1 + 3 + 3 - 2 = 10$.
Пример на рис. показывает, что нужная система авиалиний в государстве с десятью городами существует.
Граф на рис. часто используется в качестве примера и даже имеет специальное название "граф Петерсена".
Ответ: 10 городов.
