из каждого города исходит ровно три дороги. При эт...

질문

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

사고

Explaining the 3-regular graph with diameter 2

This is a combinatorics problem involving a 3-regular graph where each city has 3 roads. The challenge is to find the maximum number of vertices with a diameter of 2 — meaning every city can be reached with at most one transfer. Using the Moore bound, the max is 10 vertices, achievable by the Petersen graph.

Explaining Petersen graph and construction

The Petersen graph is a 3-regular graph with 10 vertices, where each city connects to three

Thought for 11s

답변

Рассмотрим граф городов: города — вершины, дороги — рёбра. У каждого города ровно 3 дороги ⇒ граф 3-регулярный. Условие «из любого в любой не более чем с одной пересадкой» означает, что между любыми двумя вершинами есть путь длины ≤ 2, то есть диаметр графа ≤ 2.

Возьмём произвольный город $A$ .

На расстоянии 1 от него — ровно 3 города (его соседи).
Каждый из этих 3 соседей имеет ещё по 2 дороги “дальше” (кроме дороги обратно в $A$ ).
Значит, на расстоянии 2 от $A$ может быть не больше $3 \cdot 2 = 6$ городов (в лучшем случае все разные).

Итого максимум городов:

1\ (\text{сам }A) + 3\ (\text{на расстоянии 1}) + 6\ (\text{на расстоянии 2}) = 10.

Больше быть не может, потому что все города должны укладываться в радиус 2 вокруг $A$ , а мы уже посчитали абсолютный верхний предел.

Ответ: 10.
Причём это достижимо: существует 3-регулярный граф на 10 вершинах диаметра 2 (классический пример — граф Петерсена), значит 10 — действительно максимум.

질문

사고

Explaining the 3-regular graph with diameter 2

Explaining Petersen graph and construction

답변

이 Q&A 공유하기