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

Для решения этой задачи нужно построить граф, где вершины – города, а ребра – авиалинии между ними. Авиалиния существует, если двузначное число, образованное номерами городов, делится на 3. Двузначные числа, делящиеся на 3, которые можно составить из цифр от 1 до 9: 12, 15, 18, 21, 24, 27, 33, 36, 39, 42, 45, 48, 51, 54, 57, 63, 66, 69, 72, 75, 78, 81, 84, 87, 93, 96, 99. Теперь построим граф: * Город 1 связан с городами: 2, 5, 8 * Город 2 связан с городами: 1, 4, 7 * Город 3 связан с городами: 3, 6, 9 * Город 4 связан с городами: 2, 5, 8 * Город 5 связан с городами: 1, 4, 7 * Город 6 связан с городами: 3, 6, 9 * Город 7 связан с городами: 2, 5, 8 * Город 8 связан с городами: 1, 4, 7 * Город 9 связан с городами: 3, 6, 9 Проверим, можно ли добраться из города 1 в город 9: 1 -> 2 -> 4 -> 5 -> 7 -> 2 -> 1 -> 8 -> 4 -> ... (нельзя найти путь) 1 -> 8 -> 7 -> 2 -> 4 -> 5 -> 1 -> 8 -> ... (нельзя найти путь) 1 -> 5 -> 4 -> 2 -> 7 -> 5 -> 1 -> 8 -> ... (нельзя найти путь) Путь из города 1 в город 9 не существует. Ответ: Нет, нельзя добраться из города 1 в город 9.