Решение: Протяжённости дорог района
На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта В в пункт Г и из пункта Д в пункт Е.
| Номер пункта | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 1 | — | 9 | 8 | — | — | — | — |
| 2 | 9 | — | 7 | — | 6 | — | — |
| 3 | 8 | 7 | — | 5 | 4 | 3 | 10 |
| 4 | — | — | 5 | — | — | 11 | — |
| 5 | — | 6 | 4 | — | — | — | 12 |
| 6 | — | — | 3 | 11 | — | — | 13 |
| 7 | — | — | 10 | — | 12 | 13 | — |
Решение по шагам
4 шагаПредставим таблицу как матрицу смежности взвешенного графа: ненулевое значение в строке и столбце означает наличие дороги, а само значение — её протяжённость.
Сравниваем степени вершин на рисунке со степенями пронумерованных пунктов в таблице и восстанавливаем соответствие между буквенными обозначениями и номерами пунктов.
По восстановленному соответствию длина дороги из пункта В в пункт Г равна 13 км, а длина дороги из пункта Д в пункт Е равна 6 км.
Складываем найденные протяжённости.
$$13 + 6 = 19$$Где здесь ошибаются
Считать номера пунктов в таблице совпадающими с буквенными обозначениями на графе.
Использовать только число соседей и не проверять взаимное расположение соседних вершин.
Сложить длины других рёбер после неверного сопоставления вершин.