Условие:
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о дорогах между населенными пунктами (звездочка означает, что дорога между соответствующими городами есть).
| 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
| 1 | ||||||
| 2 | ||||||
| 3 | ||||||
| 4 | ||||||
| 5 | ||||||
| 6 | ege.splamga.ru |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите номера населенных пунктов 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 ребер (максималь...