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

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

Если покрывающие циклы не имеют общих вершин, покрытие называется вершинно непересекающимся или, иногда, просто покрытием непересекающимися циклами. В этом случае набор циклов составляет остовный подграф графа G.

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

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

Покрытие Циклами Минимального Веса

Для взвешенных графов Задача о Покрытии Циклами Минимального Веса (ЗПЦМВ, англ. Minimum-Weight Cycle Cover Problem, MWCCP) является задачей поиска покрытия с минимальным суммарным весом по всем циклам покрытия.

Для планарных графов без мостов задача ЗПЦМВ может быть решена за полиномиальное время^[3].

Циклическое k-покрытие

Циклическое k-покрытие графа — это семейство циклов, которое покрывает каждое ребро графа G ровно k раз. Было доказано, что любой граф без мостов имеет k-покрытие циклами для любого чётного числа ${\displaystyle k\geqslant 4}$. Для случая k=2 это известная гипотеза о двойном покрытии циклами, являющаяся открытой проблемой в теории графов. Гипотеза о двойном покрытии циклами утверждает, что в любом графе без мостов существует набор циклов, который дважды накрывает каждое ребро графа^[4].

См. также

• Гипотеза Алспаха
• Покрытие вершин циклами