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

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

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

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

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

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

Перманент

(Перманент) (0,1)-матриці дорівнює числу покриттів вершинно неперетинними циклами орієнтованого графа з цією матрицею суміжності. Цей факт використовують у спрощеному доведенні того, що обчислення перманента ^[en].

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

Задачі пошуку вершинно неперетинних і реберно неперетинних покриттів циклами з найменшим числом циклів є NP-повними. Задачі не належать до (класу складності) APX. Варіанти для орграфів також належать до APX.

Див. також

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

Примітки

David Eppstein. Partition a graph into node-disjoint cycles.
Tutte W. T. A short proof of the factor theorem for finite graphs // . — 1954. — Т. 6. — С. 347–352. — DOI:10.4153/CJM-1954-033-3..
http://www.cs.cmu.edu/~avrim/451f13/recitation/rec1016.txt [ 2018-04-27 у Wayback Machine.] (problem 1)
Garey M. R., Johnson D. S. Computers and intractability. — New York : W.H. Freeman and Company, 1979. — .
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.
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. — ., у книзі цитується Sartaj Sahni, Teofilo F. Gonzalez. P-complete approximation problems // . — 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 // . — 1954. — Т. 6. — С. 347–352. — DOI:10.4153/CJM-1954-033-3..

[CS-3] ttp://www.cs.cmu.edu/~avrim/451f13/recitation/rec1016.txt [ 2018-04-27 у Wayback Machine.] (problem 1)

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

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

[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. — ., у книзі цитується Sartaj Sahni, Teofilo F. Gonzalez. P-complete approximation problems // . — 1976. — Т. 23, вип. 3. — С. 555–565. — DOI:10.1145/321958.321975.