Алгоритм нахождения циклов в ориентированном графе с некоторыми ограничениями

Question

У меня есть граф с заданными ограничениями:
1. Граф направлен
2. Максимум 2 ребра возникают из вершины
3. Максимум 2 ребра ведут в вершину

В этом графе я хочу найти циклы, чтобы:
a) каждая вершина была только частью одного цикла
b) каждая вершина была частью некоторого цикла

I ' Мы уже потратили некоторое время на эту проблему, но, как бы легко это ни звучало, она не кажется такой тривиальной.

Расширение вопроса таково:
Каждый ребро дополнительно имеет промежуток, два должны быть выбраны действительные числа и «ось», чтобы все ребра, заканчивающиеся циклами, могли «подогнать» ось в свой диапазон диапазона.
Т.е. для оси 100 можно использовать ребро [20, 100], потому что 100 в [20, 120]

Answer 1

Ваша проблема называется поиском вершины, не пересекающей вершину цикла . Его можно найти за полиномиальное время, как описано в этом ответе

Ваш расширенный вопрос мне не понятен. Вам дан разворот? Тогда вы просто удалите неприлегающие края. Вы должны выбрать один? Если вам повезет, вы сможете изменить поиск с идеальным соответствием, чтобы удовлетворить это. Но будьте осторожны, такие дополнительные условия легко делают разницу между полиномиальной и NP-трудной задачей.