Покрытие вершин циклами

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

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

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

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

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

Перманент

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

Покрытия непересекающимися циклами

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

См. также

Примечания
  1. David Eppstein. Partition a graph into node-disjoint cycles.
  2. Tutte W. T. A short proof of the factor theorem for finite graphs // Canadian Journal of Mathematics. — 1954. — Т. 6. — С. 347–352. — doi:10.4153/CJM-1954-033-3..
  3. http://www.cs.cmu.edu/~avrim/451f13/recitation/rec1016.txt (problem 1)
  4. Garey M. R., Johnson D. S. Computers and intractability. — New York: W.H. Freeman and Company, 1979. — ISBN 0-7167-1044-7.
  5. Amir Ben-Dor, Shai Halevi. Zero-one permanent is #P-complete, a simpler proof // Proceedings of the 2nd Israel Symposium on the Theory and Computing Systems. — 1993. — С. 108-117.
  6. G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. — 1999. — С. 378, 379. — ISBN 3-540-65431-3., В книге цитируется Sartaj Sahni, Teofilo F. Gonzalez. P-complete approximation problems // Journal of the ACM. — 1976. — Т. 23, вып. 3. — С. 555–565. — doi:10.1145/321958.321975.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.