Покриття́ верши́н ци́клами (або просто покриття́ ци́клами) графа G — це набір циклів, які є підграфами графа G і містять усі вершини G.
Якщо покривальні цикли не мають спільних вершин, покриття називають вершинно неперетинним або іноді просто покриттям циклами, що не перетинаються. У цьому випадку набір циклів утворює кістяковий підграф графа G. Покриття циклами, що не перетинаються, неорієнтованого графа (якщо таке існує) можна знайти за поліноміальний час, перетворивши задачу в задачу пошуку досконалого парування в більшому графі.
Якщо цикли покриття не мають спільних ребер, покриття називають реберно неперетинним або просто покриттям циклами, що не перетинаються.
Аналогічні визначення в термінах орієнтованих циклів існують для орграфів. Пошук покриття циклами орієнтованого графа, що вершинно не перетинаються, можна здійснити за поліноміальний час шляхом аналогічного зведення до досконалого парування. Проте додання умови, що кожен цикл повинен мати довжину принаймні 3, робить задачу NP-складною.
Властивості та застосування
Перманент Перманент (0,1)-матриці дорівнює числу покриттів вершинно неперетинними циклами орієнтованого графа з цією матрицею суміжності. Цей факт використовують у спрощеному доведенні того, що обчислення перманента .
Покриття циклами, що не перетинаються Задачі пошуку вершинно неперетинних і реберно неперетинних покриттів циклами з найменшим числом циклів є NP-повними. Задачі не належать до класу складності APX. Варіанти для орграфів також належать до APX.
Див. також Покриття ребер циклами
Примітки