2. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, составленное из цифр-названий этих городов, делится на 3. Постройте граф и ответьте на вопрос, можно ли добраться из города 1 в город 9?

Решение:

Два города \( A \) и \( B \) соединены авиалинией, если двузначное число, составленное из их названий (например, \( AB \) или \( BA \)), делится на 3.

Число делится на 3, если сумма его цифр делится на 3.

Проверим возможные соединения для города 1:

• \( 12 \) — сумма цифр \( 1+2=3 \), делится на 3. Соединение \( 1 \leftrightarrow 2 \).
• \( 13 \) — сумма цифр \( 1+3=4 \), не делится на 3.
• \( 14 \) — сумма цифр \( 1+4=5 \), не делится на 3.
• \( 15 \) — сумма цифр \( 1+5=6 \), делится на 3. Соединение \( 1 \leftrightarrow 5 \).
• \( 16 \) — сумма цифр \( 1+6=7 \), не делится на 3.
• \( 17 \) — сумма цифр \( 1+7=8 \), не делится на 3.
• \( 18 \) — сумма цифр \( 1+8=9 \), делится на 3. Соединение \( 1 \leftrightarrow 8 \).
• \( 19 \) — сумма цифр \( 1+9=10 \), не делится на 3.

Построим граф, где вершины — города, а ребра — авиалинии.

Граф:

Вершины: 1, 2, 3, 4, 5, 6, 7, 8, 9.

Ребра (примеры соединений):

• Из 1: \( 1-2, 1-5, 1-8 \)
• Из 2: \( 2-1, 2-4, 2-7 \) (например, \( 24 \) -> \( 2+4=6 \), \( 27 \) -> \( 2+7=9 \))
• Из 3: \( 3-3 \) (самосоединение, но задача про двузначные числа), \( 3-6, 3-9 \) (например, \( 36 \) -> \( 3+6=9 \), \( 39 \) -> \( 3+9=12 \))
• Из 4: \( 4-2, 4-5, 4-8 \)
• Из 5: \( 5-1, 5-4, 5-7 \)
• Из 6: \( 6-3, 6-9 \)
• Из 7: \( 7-2, 7-5, 7-8 \)
• Из 8: \( 8-1, 8-4, 8-7 \)
• Из 9: \( 9-3, 9-6 \)

Для того чтобы проверить, можно ли добраться из города 1 в город 9, нужно найти путь в графе.

Пример пути:

1 \(\rightarrow\) 2 \(\rightarrow\) 4 \(\rightarrow\) 8 \(\rightarrow\) 7 \(\rightarrow\) 5 \(\rightarrow\) 1 ... (это не ведет к 9)

Рассмотрим соединения, которые могут привести к 9. Город 9 соединяется с городами, названия которых в двузначном числе с 9 дают сумму, кратную 3:

• \( 93 \) → \( 9+3=12 \) (делится на 3) → \( 9 \leftrightarrow 3 \)
• \( 96 \) → \( 9+6=15 \) (делится на 3) → \( 9 \leftrightarrow 6 \)

Чтобы добраться из 1 в 9, нужно найти путь.

Путь: \( 1 \rightarrow 8 \rightarrow 4 \rightarrow 5 \rightarrow 7 \rightarrow 2 \rightarrow ... \)

Ищем путь, который ведет к 3 или 6, чтобы потом попасть в 9.

Рассмотрим соединения:

• Город 1 соединен с 2, 5, 8.
• Город 8 соединен с 1, 4, 7.
• Город 4 соединен с 2, 5, 8.
• Город 7 соединен с 2, 5, 8.
• Город 2 соединен с 1, 4, 7.
• Город 5 соединен с 1, 4, 7.

Это означает, что города {1, 2, 4, 5, 7, 8} образуют одну компоненту связности.

Теперь посмотрим на города {3, 6, 9}.

• Город 3 соединен с 6, 9 (т.к. 36, 39 делятся на 3).
• Город 6 соединен с 3, 9 (т.к. 63, 69 делятся на 3).
• Город 9 соединен с 3, 6 (т.к. 93, 96 делятся на 3).

Итак, города {3, 6, 9} образуют отдельную компоненту связности.

Поскольку города 1 и 9 находятся в разных компонентах связности, добраться из города 1 в город 9 невозможно.

Ответ: Нет, нельзя. Города 1 и 9 находятся в разных компонентах связности графа.