На схеме дорог Н-ского района некоторые пункты обозначены буквами, а другие — цифрами. В таблице указана информация о наличии дорог между пунктами, обозначенными цифрами. Определите, каким цифрам соответствуют пункты A и G. | | 1 | 2 | 3 | 4

18 ноября 2025
Логика

Условие:

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о дорогах между населенными пунктами (звездочка означает, что дорога между соответствующими городами есть).
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline & 1 & 2 & 3 & 4 & 5 & 6 \\
\hline 1 & & \( * \) & & \( * \) & & \\
\hline 2 & \( * \) & & & \( * \) & & \( * \) \\
\hline 3 & & & & \( * \) & \( * \) & \\
\hline 4 & \( * \) & \( * \) & \( * \) & & \( * \) & \( * \) \\
\hline 5 & & & \( * \) & \( * \) & & \\
\hline 6 & & \( * \) & & \( * \) & ege.splamga.ru \\
\hline
\end{tabular}

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

Решение:

Найдём сначала связи между населенными пунктами согласно таблице. Пронумеруем вершины графа, соответствующие пунктам, числами от 1 до 6. Из таблицы видно: • пункт 1 соединён с пунктами 2 и 4; • пункт 2 – с пунктами 1, 4 и 6; • пункт 3 – с пунктами 4 и 5; • пункт 4 – с пунктами 1, 2, 3, 5 и 6; • пункт 5 – с пунктами 3 и 4; • пункт 6 – с пунктами 2 и 4 (ячейка, где записан подозрительный текст, по смыслу должна быть пустой, то есть звёздочка отсутствует). Таким образом, степени вершин таковы: 1 – 2 ребра, 2 – 3 ребра, 3 – 2 ребра, 4 – 5 ребер (максималь...