Задание 7. В стране Цифромании есть б городов с названиями 1, 2, 3, 4, 5, 6, Руководство страны сообщило, что организует железнодорожное сообщение между городами в том и только в…
Задание 7. В стране Цифромании есть б городов с названиями 1, 2, 3, 4, 5, 6, Руководство страны сообщило, что организует железнодорожное сообщение между городами в том и только в том случае, если двузначное число, составленное из цифр-названий этих городов, делится на 2. Постройте граф, соответствующий проекту железнодорожного сообщения между городами Цифромании.
Рассмотрим задание шаг за шагом.
Задача:
В стране Цифромании есть 6 городов с названиями 1, 2, 3, 4, 5, 6.
Руководство организует железнодорожное сообщение между двумя городами, если и только если число, составленное из их названий, двузначное и делится на 2.
Что это значит?
- Каждые два города можно связать железной дорогой, если число, образованное их номерами, делится на 2.
- Двузначное число из цифр городов: например, для городов 1 и 3 — число 13, для 4 и 5 — число 45.
Важно:
- Для делимости на 2 двузначного числа достаточно, чтобы его последняя цифра была чётной.
- Следовательно, двузначное число, составленное из номеров городов, делится на 2, если последний город (цифра) — 2, 4 или 6.
Теперь построим граф:
- Вершины графа — города {1, 2, 3, 4, 5, 6}.
- Ребра есть только между городами, номера которых позволяют составить подходящее двузначное число (то есть число, оканчивающееся на чётную цифру).
Рассмотрим все возможные пары:
Пары, оканчивающиеся на 2:
- (1, 2) — число 12, делится на 2
- (3, 2) — число 32
- (4, 2) — число 42
- (5, 2) — число 52
- (6, 2) — число 62
Также обратные пары — так как граф не ориентированный, добавим и их:
- (2, 1), (2, 3), (2, 4), (2, 5), (2, 6)
Пары, оканчивающиеся на 4:
- (1, 4) — 14
- (3, 4) — 34
- (5, 4) — 54
- (6, 4) — 64
Обратные:
- (4, 1), (4, 3), (4, 5), (4, 6)
Пары, оканчивающиеся на 6:
- (1, 6)
- (3, 6)
- (4, 6)
- (5, 6)
Обратные:
- (6, 1), (6, 3), (6, 4), (6, 5)
Итоговый список рёбер:
- (1, 2), (2, 1)
- (1, 4), (4, 1)
- (1, 6), (6, 1)
- (2, 3), (3, 2)
- (2, 4), (4, 2)
- (2, 5), (5, 2)
- (2, 6), (6, 2)
- (3, 4), (4, 3)
- (3, 6), (6, 3)
- (4, 5), (5, 4)
- (4, 6), (6, 4)
- (5, 6), (6, 5)
Ответ:
Граф содержит 6 вершин (города 1, 2, 3, 4, 5, 6) и рёбра, соответствующие перечисленным парным соединениям.
Если нужно, я могу помочь нарисовать схему графа или объяснить ещё подробнее.
