Покрытие вершин циклами (или просто покрытие циклами) графа G — это набор циклов, которые являются подграфами графа G и содержат все вершины G.
Если покрывающие циклы не имеют общих вершин, покрытие называется вершинно непересекающимся или иногда просто покрытием непересекающимися циклами. В этом случае набор циклов составляет остовный подграф графа G. Покрытие непересекающимися циклами неориентированного графа (если такое существует) может быть найдено за полиномиальное время путём преобразования задачи в задачу поиска совершенного паросочетания в большем графе.
Если циклы покрытия не имеют общих рёбер, покрытие называется рёберно непересекающимся или просто покрытием непересекающимися циклами.
Аналогичные определения существуют для орграфов в терминах ориентированных циклов. Поиск покрытия вершинно непересекающимися циклами ориентированного графа может быть осуществлён за полиномиальное время путём аналогичного сведения к совершенному паросочетанию. Однако добавление условия, что каждый цикл должен иметь длину не менее 3, делает задачу NP-трудной.
Свойства и приложения
Перманент Перманент (0,1)-матрицы равен числу покрытий вершинно непересекающимися циклами ориентированного графа с этой матрицей смежности. Этот факт используется в упрощённом доказательстве того, что вычисление перманента .
Покрытия непересекающимися циклами Задачи поиска вершинно непересекающихся и рёберно непересекающихся покрытий циклами с минимальным числом циклов являются NP-полными. Задачи не принадлежат классу сложности APX. Варианты для орграфов также не принадлежат APX.
См. также Покрытие рёбер циклами
Примечания
Категория:Вычислительные задачи теории графов Категория:NP-полные задачи