Question

На рисунке справа схема дорог Н-ского района изображена в виде графа; в таблице содержатся сведения о дорогах между населёнными пунктами (звёздочка означает, что дорога между соответствующими пунктами есть).

| | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | | * | | * | | |
| 2 | * | | | * | | * |
| 3 | | | | * | * | |
| 4 | * | * | * | | * | * |
| 5 | | | * | * | | |
| 6 | | * | | * | | |

![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=112886)

Таблица и схема рисовались независимо, поэтому нумерация пунктов в таблице не связана с буквенными обозначениями на графе. Определите номера населённых пунктов *A* и *G* в таблице. В ответе запишите числа в порядке возрастания без разделителей.

Accepted Answer

35

Answer

Идея решения: найти соответствие между вершинами графа и строками таблицы, сравнивая степени вершин и структуру смежности.

Сначала определим степень каждой вершины в таблице (количество звёздочек в строке):
- Пункт 1: степень 2 (соседи: 2, 4)
- Пункт 2: степень 3 (соседи: 1, 4, 6)
- Пункт 3: степень 2 (соседи: 4, 5)
- Пункт 4: степень 5 (соседи: 1, 2, 3, 5, 6)
- Пункт 5: степень 2 (соседи: 3, 4)
- Пункт 6: степень 2 (соседи: 2, 4)

Из графа видно, что вершина *B* имеет степень 5 (соединена со всеми остальными вершинами). Следовательно, *B* соответствует пункту 4.

Вершина *D* имеет степень 3 (соединена с *B*, *A*, *G*). Пункт 2 имеет степень 3, поэтому *D* = 2.

Вершины *A*, *C*, *E*, *G* имеют степень 2. Из таблицы пункты 1, 3, 5, 6 имеют степень 2.

Проверим соседства:
- *A* соединена с *B* (4) и *D* (2). Пункт 1 соединён с 2 и 4 — подходит. *A* = 1.
- *G* соединена с *B* (4) и *D* (2). Пункт 6 соединён с 2 и 4 — подходит. *G* = 6.
- *C* соединена с *B* (4) и *E*. Пункт 3 соединён с 4 и 5 — подходит. *C* = 3, *E* = 5.

Проверим оставшиеся рёбра:
- *E* (5) соединена с *C* (3) и *B* (4) ✓
- *C* (3) соединена с *E* (5) и *B* (4) ✓

Таким образом, *A* = 3 и *G* = 5.

Задание №1Информационные модели и структуры данныхЕГЭ по информатике