Учитывая график (показанный ниже), существует ли алгоритм, позволяющий мне построить основу цикла с условием, что каждое ребро должно быть общим для не более 2 циклов?
То есть для приведенного выше графика алгоритм должен вернуть мне следующие 5 циклов в качестве решения:
C1=>e1,e2,e13,e3
C2=>e13,e4,e5
C3=>e5,e9,e6
C4=>e7,e6,e10,e8
C5=>e10,e9,e12,e11
Обратите внимание, что ни у одного ребра не более 2циклы на нем.Любой другой набор из 5 циклов - до тех пор, пока все ребра не имеют более 2 циклов - может быть принят в качестве решения.
Вопрос: существует ли такой алгоритм?
Я могу построить набор циклов, сначала найдя остовное дерево, а затем завершить циклы, добавив ребра, которые не находятся внутри остовного дерева, но я не могу гарантировать, что набор цикловБазис, построенный таким образом, имеет вышеуказанную особенность, которую я желал.
Кроме того, координаты каждой вершины не известны .