Question

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

Answer 1

Ответ:

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

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

Список всех двузначных чисел, делящихся на 3: 12, 15, 18, 21, 24, 27, 30, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99.

Теперь мы можем заполнить матрицу смежности:

| 1 2 3 4 5 6 7 8 9

--|------------------

1 | 0 0 1 0 0 1 0 0 1

2 | 0 0 0 0 0 0 0 0 1

3 | 1 0 0 1 0 0 1 0 0

4 | 0 0 1 0 0 1 0 0 1

5 | 0 0 0 0 0 0 0 0 1

6 | 1 0 0 1 0 0 1 0 0

7 | 0 0 1 0 0 1 0 0 1

8 | 0 0 0 0 0 0 0 0 1

9 | 1 1 0 1 1 0 1 1 0

Таким образом, граф имеет следующий вид:

```

3---6---9

/ / \ / \

1---4---7 2---9

|

5---9

```