Покрытие вершин циклами (или просто покрытие циклами) графа G — это набор циклов, которые являются подграфами графа G и содержат все вершины G.

Если покрывающие циклы не имеют общих вершин, покрытие называется вершинно непересекающимся или иногда просто покрытием непересекающимися циклами. В этом случае набор циклов составляет остовный подграф графа G. Покрытие непересекающимися циклами неориентированного графа (если такое существует) может быть найдено за полиномиальное время путём преобразования задачи в задачу поиска совершенного паросочетания в большем графе.

Если циклы покрытия не имеют общих рёбер, покрытие называется рёберно непересекающимся или просто покрытием непересекающимися циклами.

Аналогичные определения существуют для орграфов в терминах ориентированных циклов. Поиск покрытия вершинно непересекающимися циклами ориентированного графа может быть осуществлён за полиномиальное время путём аналогичного сведения к совершенному паросочетанию. Однако добавление условия, что каждый цикл должен иметь длину не менее 3, делает задачу NP-трудной.

Свойства и приложения

Перманент Перманент (0,1)-матрицы равен числу покрытий вершинно непересекающимися циклами ориентированного графа с этой матрицей смежности. Этот факт используется в упрощённом доказательстве того, что вычисление перманента .

Покрытия непересекающимися циклами Задачи поиска вершинно непересекающихся и рёберно непересекающихся покрытий циклами с минимальным числом циклов являются NP-полными. Задачи не принадлежат классу сложности APX. Варианты для орграфов также не принадлежат APX.

См. также Покрытие рёбер циклами

Примечания

Категория:Вычислительные задачи теории графов Категория:NP-полные задачи