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

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

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

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

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

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

Перманент

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

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

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

См. также

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

Примечания

↑ David Eppstein. Partition a graph into node-disjoint cycles (неопр.).
↑ 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..
↑ http://www.cs.cmu.edu/~avrim/451f13/recitation/rec1016.txt Архивная копия от 27 апреля 2018 на Wayback Machine (problem 1)
↑ Garey M. R., Johnson D. S. Computers and intractability. — New York: W.H. Freeman and Company, 1979. — ISBN 0-7167-1044-7.
↑ 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. Архивировано 29 февраля 2008 года.
↑ 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.

[Ep-1] David Eppstein. Partition a graph into node-disjoint cycles (неопр.).

[Tu-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..

[CS-3] ttp://www.cs.cmu.edu/~avrim/451f13/recitation/rec1016.txt Архивная копия от 27 апреля 2018 на Wayback Machine (problem 1)

[GJ-4] Garey M. R., Johnson D. S. Computers and intractability. — New York: W.H. Freeman and Company, 1979. — ISBN 0-7167-1044-7.

[BDH-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. Архивировано 29 февраля 2008 года.

[ACGK-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.

[1]

[2]

[3]

[4]

[5]

[6]