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

Давай разберемся с условием задачи. Чтобы двузначное число, составленное из двух цифр $a$ и $b$, делилось на 3, сумма этих цифр ($a+b$) должна делиться на 3 (по признаку делимости на 3). Распределим все наши города-цифры по остаткам от деления на 3: - Группа $R_0$ (остаток 0): ${3, 6, 9}$. Если мы возьмем любые два числа из этой группы, их сумма будет делиться на 3. Значит, внутри этой группы все города соединены друг с другом. - Группа $R_1$ (остаток 1): ${1, 4, 7}$. - Группа $R_2$ (остаток 2): ${2, 5, 8}$. Посмотрим, как они соединяются: 1. Число из $R_1$ и число из $R_2$: их сумма ($1+2=3$) делится на 3. Значит, каждый город из группы $R_1$ соединен с каждым городом из группы $R_2$. Это связная компонента. 2. Число из $R_1$ и другое число из $R_1$: их сумма ($1+1=2$) не делится на 3. 3. Число из $R_2$ и другое число из $R_2$: их сумма ($2+2=4$) не делится на 3. 4. Число из $R_0$ с числом из $R_1$ или $R_2$: их сумма ($0+1=1$ или $0+2=2$) не делится на 3. Итог: наш граф состоит из двух изолированных частей. В одной части города ${3, 6, 9}$, в другой — ${1, 2, 4, 5, 7, 8}$. Город 1 принадлежит второму множеству, а город 6 — первому. Путей между ними нет. **Ответ:** Нет, добраться из города 1 в город 6 нельзя.