" На рисунке схема дорожек парка им. Кинга изображена в виде графа, в таблице содержатся сведения о путях между памятниками (звездочка означает, что путь между…
" На рисунке схема дорожек парка им. Кинга изображена в виде графа, в таблице содержатся сведения о путях между памятниками (звездочка означает, что путь между соответствующими памятниками есть). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите названия всех памятников П1-П9. Например, ABCDEFGHI. "
Классно, давай разберёмся вместе. Это задача на сопоставление вершин графа с номерами памятников П1…П9 через степени вершин и структуру связей. Вот подсказка, как двигаться по шагам.
Подсказка по шагам
- Шаг 1. Найди вершину графа с наибольшей степенью. По условию в ней указано 6 дорог — это соответствует П5.
- Шаг 2. Посмотри на соседей этой вершины (6 соседей). Среди них найдутся две вершины, у которых степень больше остальных (у них по 4 дороги). Эти две вершины должны соответствовать П1 и П4 (но пока не зная, какая из них какая).
- Шаг 3. Возьми одну из двух вершин с 4 дорогами и помести её на роль либо П1, либо П4 (сделай выбор произвольным для начала, скажем — пусть одна из них будет П4, а другая — П1). Плюс к этому — другая версия решения будет получаться при противоположном выборе.
- Шаг 4. У этих вершин с 4 дорогами есть свои остальные соседи. Среди соседей найдутся две вершины, из которых выходит ровно две дороги в целом — именно они соответствуют П7 и П9 (поскольку у П7 и П9 две дороги). Это поможет зафиксировать, какие две графовые вершины соответствуют П7 и П9.
- Шаг 5. Далее идём по цепи от выбранной вершины с 4 дорогами: остальные памятники будут размещаться последовательно через соседей, и по каждому шагу сравнивай количество и точное соединение дорог, чтобы не противоречить уже найденным соответствиям.
- Шаг 6. Аналогично в симметричном ходе по другой вершине с 4 дорогами (той, что была помечена как П1 или П4) ты сможешь закрепить ещё пары П2, П3, П6, П8 и так далее.
- Шаг 7. В итоге получится две допустимые нумерации П1…П9 на графе, полученные в результате разности выбора между двумя вершинами с 4 дорогами (перестановка П1 и П4). Именно поэтому возможны две корректные последовательности букв для П1…П9 (они соответствуют двум правдоподобным разным разметкам графа). Примерно это приводит к двум строкам-ответам, которые выдают разные варианты, но обе верны.
Если хочешь, могу разобрать одну из ветвей подробно по шагам и проверить, что получается на каждом этапе. После того, как сам попробуешь, скажи, какая ветвь у тебя выходит.
Пожалуйста, оцени мой ответ лайком или дизлайком.
