Какое название этой структуры данных?
При решении одной задачи возникла структура данных, являющаяся ориентированным графом, но с оговорками. Каждой вершине vi приписано некоторое натуральное число ni. Далее будет ясно, что оно означает:
Выберем некоторую вершину. Она соединена ориентированными рёбрами с некоторыми другими вершинами. Выберем любое ребро и пойдём по нему. Будем повторять эту процедуру пока не зайдём в "тупик" (далее станет более ясно, почему процесс прекратиться и что такое "тупик"). Таким образом, образовался некий путь от начальной вершины до "тупика", но со следующими правилами:
- Через точку vi можно проходить не более, чем ni раз
- Точка называется "тупиком", если из неё нельзя больше попасть ни в одну вершину графа. Причём это может быть по двум причинам:
- либо из этой точки не исходит ни одного ребра
- либо в какую-бы следующую вершину vi мы не направились, её соответствующее число ni уже исчерпалось по пути (то есть vi уже встретилась в пути ni раз) (также ясно, что из-за этого свойства, является точка тупиком или нет вообще зависит от пройденного нами пути)
- Если есть возможность продолжить путь в какую-нибудь вершину, то ею обязательно нужно воспользоваться (то есть последней точкой любого пути всегда является "тупик")
В итоге такой путь, удовлетворяющий этим трём правилам, думаю, можно назвать тупиковым
Изначальная моя задача такая: для заданного ориентированного графа из заданной вершины построить все тупиковые пути. Эту задачу я уже решил, но мне интересно изучить эту структуру данных. И мои вопросы: как она называется? можно ли о ней где-то найти информацию для изучения?