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

Покриття́ верши́н ци́клами (або просто покриття́ ци́клами) графа G — це набір циклів, які є підграфами графа G і містять усі вершини G.

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

Якщо цикли покриття не мають спільних ребер, покриття називають реберно неперетинним або просто покриттям циклами, що не перетинаються.

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

Властивості та застосування

Перманент

Перманент (0,1)-матриці дорівнює числу покриттів вершинно неперетинними циклами орієнтованого графа з цією матрицею суміжності. Цей факт використовують у спрощеному доведенні того, що обчислення перманента #P-повне[en][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 [Архівовано 2018-04-27 у Wayback Machine.] (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.