В математике циклическое покрытие вершин (обычно называемое просто циклическим покрытием ) графа G — это набор циклов , которые являются подграфами G и содержат все вершины G.
Если циклы покрытия не имеют общих вершин, покрытие называется вершинно-непересекающимся или иногда просто непересекающимся циклическим покрытием . Иногда это известно как точное вершинно-циклическое покрытие. В этом случае набор циклов составляет остовной подграф графа G. Непересекающееся циклическое покрытие неориентированного графа (если оно существует) может быть найдено за полиномиальное время путем преобразования задачи в задачу поиска идеального паросочетания в большем графе. [1] [2]
Если циклы покрытия не имеют общих ребер, покрытие называется рёберно-непересекающимся или просто покрытием непересекающихся циклов .
Аналогичные определения существуют для орграфов в терминах направленных циклов. Поиск вершинно-непересекающегося циклического покрытия направленного графа также может быть выполнен за полиномиальное время с помощью аналогичного сведения к идеальному совпадению . [3] Однако добавление условия, что каждый цикл должен иметь длину не менее 3, делает задачу NP-трудной . [4]
Перманент (0,1)-матрицы равен числу вершинно-непересекающихся циклических покрытий ориентированного графа с этой матрицей смежности . Этот факт используется в упрощенном доказательстве, показывающем, что вычисление перманента является #P-полным . [5]
Задачи нахождения вершинно-непересекающихся и реберно-непересекающихся циклических покрытий с минимальным числом циклов являются NP-полными . Задачи не входят в класс сложности APX . Варианты для орграфов также не входят в APX. [6]