"На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяженности каждой из этих дорог (в километрах). Так как таблицу и схему…
"На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяженности каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта B в пункт Н и из пункта А в пункт Е. В ответе запишите целое число П1 П2 П3 П4 П5 П6 П7 П8 П1 53 1 2 П2 53 13 8 П3 30 39 74 П4 1 13 5 П5 30 3 П6 5 21 П7 2 39 21 П8 8 74 3 ."
Ок, давай подумаем вместе и дадим небольшую подсказку, чтобы ты смог сам выйти на решение.
Подсказка:
- Сначала посчитай степени вершин графа (сколько дорог выходит из каждой населённого пункта). В таблице это можно увидеть как количество непустых значений в каждой строке для P1..P8.
- Найди две вершины графа, у которых степень равна 3 и которые не имеют общих дорог с вершинами степени 2 — эти две вершины и нужно сопоставить с П1 и П2 (они будут первыми в цепочке сопоставления).
- Далее используйте связи между вершинами: например, если в графе вершина C соединена и с E, и с G, то C должна соответствовать такой П-индекс, который имеет дорожки к «соответствующим» П1/П2. По цепочке сопоставлений можно двигаться дальше: D — к какой-то другой П, затем F, затем H, и т.д., пока не сопоставишь все буквы A..H с П1..П8.
- Когда сопоставишь буквы с П-индексами, из получения расстояний между нужными парой можно сложить итог: сумма длин дорог из B в H и из A в E будет равна сумме соответствующих прямых дорог на таблице (то есть длины тех пар П_i, которые сопоставлены B–H и A–E).
Если хочешь, могу дать более детальное поэтапное руководство после твоей попытки сопоставления. Но сейчас попробуй начать с подсчета степеней и поиска соответствий по вышеописанному плану.
Пожалуйста, оцени мой ответ лайком или дизлайком.
