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

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

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

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

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

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

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

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

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

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

См. также

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

Примечания

1. Cun-Quan Zhang. Integer flows and cycle covers of graphs. — New York, Basel, Hong Kong: Marcel Dekker, 1997. — Т. 205. — (Pure and Applied Mathematics). — ISBN 978-0-8247-9790-4.
2. Легко видеть, что имеется двоякий смысл последнего термина и по контексту должно быть указано, в каком смысле термин употребляется.
3. Handbook in Graph Theory. — Boca Raton, London, New York, Washington D.C.: CRC PRESS, 2004. — С. 225. — ISBN 1-58488-090-2.
4. «The Cycle Double Cover Conjecture»  (неопр.). Дата обращения: 6 мая 2019. Архивировано 9 октября 2016 года.