Question

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

Answer 1

Ответ:

Из города 9 в 1 нельзя добраться, так как 9+1=10, а 10 не делиться на 3.

Пошаговое объяснение:

1 и 2, 1 и 8, 1 и 5, 2 и 7, 2 и 8. Прости, все что смогла. Надеюсь хоть чем то помогла.

Answer 2

Ответ:

12 и 21 - делятся на 3.

18 и 81 - тоже

24 и 42 - тоже

27 и 72 - тоже

36 и 63 - тоже

39 и 93 - тоже

45 и 54 - тоже

48 и 84 - тоже

57 и 75 - тоже

69 и 96 -  тоже

78 и 87 - тоже

Пошаговое объяснение:

Из города 1 до города 9 нельзя добраться, потому что 19 не делится на 3, и 91 тоже.

Answer 3

Двузначные числа, которые делятся на 3, могут состоять только из цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 и иметь только следующие виды: 12, 15, 18, 21, 24, 27, 30, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99.

Теперь можно нарисовать граф, в котором вершины соответствуют городам, а ребра проводятся между двумя городами, соединенными авиалинией. Только в этом случае граф является графом с условием, заданным в задаче. Для удобства на графе будем обозначать только двузначные числа.



Теперь нужно понять, можно ли добраться из города 1 в город 9. Для этого можно использовать поиск в глубину или поиск в ширину.

Например, используя поиск в ширину, получаем следующие возможные пути от города 1 к городу 9:
- 1 → 78 → 42 → 96 → 69 → 93 → 39 → 9;
- 1 → 81 → 15 → 57 → 75 → 54 → 42 → 24 → 96 → 69 → 93 → 39 → 9;
- 1 → 12 → 27 → 78 → 42 → 96 → 69 → 93 → 39 → 9.

Ответ: Да, можно добраться из города 1 в город 9. Все возможные пути приведены выше.