Есть задача
| Код |
Дан ориентированный мультиграф. По его вершинам и рёбрам перемещаются фишки. Две фишки не могут одновременно находиться на одном ребре или в
одной вершине. Фишка перемещается по графу из вершины в ребро, выходящее из этой вершины; либо из ребра в вершину, в которую входит данное
ребро. Изначально все фишки находятся в вершинах. Дано некое второе расположение фишек, все фишки также в вершинах. Требуется определить,
возможен ли на данном графе переход фишек из первого положения во второе.
|
Пытаюсь найти/понять является ли эта задача типичной задачей на графах, т.е. решение которой уже описано в книгах, или может быть это обобщенная задача, или наоборот урезанный вариант какой то общейзвестной проблемы.
Наиболее похожее что смог найти это задача пятнашки15. Сейчас пытаюсь сообразить эквивалентны ли эти задача.
|