Для начала давайте разберемся с вопросом (а).
а) Может ли каждый город быть связан с другим ровно 5 маршрутами?
Сначала отметим, что трамвайные маршруты можно рассматривать как рёбра в графе, где города являются вершинами. Если каждый город (вершина) связан ровно с 5 маршрутами, это означает, что каждая вершина имеет степень 5.
Однако, здесь необходимо учитывать количество городов. У нас есть 11 городов, и значит, каждая пара городов может быть соединена максимум одним трамвайным маршрутом. Если каждый из 11 городов будет связан с 5 другими, то общее количество "отношений" (или рёбер) в графе можно будет вычислить следующим образом:
Каждое соединение учитывается для обоих городов, так что:
Общее количество рёбер = (\frac{(11 \times 5)}{2})
Проверим, сколько получится:
[
\frac{11 \times 5}{2} = \frac{55}{2} = 27.5
]
Так как количество рёбер должно быть целым числом, такая структура графа не может существовать. Следовательно, нельзя организовать систему, в которой каждый из 11 городов будет связан с ровно 5 другими городами.
Итак, ответ на вопрос (а) - Нет, это не возможно.
б) Если всего трамвайных маршрутов 30, причём каждый из 10 городов связан с 5 другими, со сколькими городами связан 11-й город?
Сначала обозначим ситуацию. У нас есть 10 городов, каждый из которых связан с 5 другими городами. Это также можно представить в виде графа, где 10 городов имеют степень 5. Поскольку каждого маршрута можно считать двусторонним, общее количество рёбер в графе можно также выразить как:
Общее количество рёбер = (\frac{(k \times n)}{2}), где (k) - степень вершин (количество городов, с которыми связан каждый город), а (n) - количество городов.
Таким образом:
[
\frac{10 \times 5}{2} = 25
]
Это значит, что при 10 городах мы имеем 25 рёбер (маршрутов), и осталось воспользоваться 5 маршрутами, чтобы достичь общего количества в 30 маршрутов.
Теперь мы рассматриваем 11-й город. В данной системе связи заметим, что у нас есть 30 маршрутов в общей сложности и 25 из них уже использованы для первых 10 городов. Таким образом, 11-й город может иметь связи:
[
30 - 25 = 5
]
Это значит, что 11-й город может быть связан с 5 городами.
Итак, ответ на вопрос (б) - 11-й город связан с 5 городами.
