дано: В стране 13 городов. Каждый город соединён авиасообщением с 6 другими.
найти: Доказать, что из любого города можно добраться в любой другой, возможно, с пересадками.
решение:
1. Мы представим города как вершины графа, а авиасообщения — как рёбра.
2. В таком графе каждый узел (город) имеет степень 6, то есть каждый город соединён с 6 другими.
3. Рассмотрим один произвольный город (вершину), обозначим его A. Он соединен с 6 городами (вершинами). Обозначим их B1, B2, B3, B4, B5 и B6.
4. Каждый из этих городов также соединён с 6 другими городами. Однако один из этих 6 городов может быть таким же, как тот, который мы уже рассмотрели (город A).
5. Таким образом, максимальное количество уникальных городов, с которыми можно связаться через 1 промежуточный город составляет:
Количество уникальных городов = 6 (соседей A) - 1 (город A) + 6 (соседей одного из соседей) = 11 уникальных городов.
6. Мы видим, что даже при самом неблагоприятном раскладе, начиная с одного города, через одного из его соседей можно достичь всех остальных городов.
7. Поскольку в стране всего 13 городов, получается, что от любого города можно добраться до другого по цепочке из соседних городов.
ответ: Из любого города можно добраться в любой другой, возможно, с пересадками.