Алгоритмы, дискретная математика и пр.'s Journal (original) (raw)

6:34p

Задача. Уважаемые участники что известно о такой задаче:

дан (ор)граф. В каждой вершине находится метка. Для каждой метки известна вершина, в которую данная метка хочет попасть. За один ход по каждому ребру может двигаться ровно одна метка. При этом в один момент времени может двигаться несколько меток, при условии, что они двигаются по разным ребрам.
Вопрос - за какое минимальное количество ходов все метки могут достигнуть своих пунктов назначения?

Я подозреваю, что это известная задача. Есть ли у задач этого класса какое-то название? Ссылки, статьи приветствуются, спасибо.