Покрытие рёбер циклами (иногда просто покрытие циклами[1]) графа — это семейство циклов, которые являются подграфами графа G и содержат все рёбра графа G.
Если покрывающие циклы не имеют общих вершин, покрытие называется вершинно непересекающимся или, иногда, просто покрытием непересекающимися циклами. В этом случае набор циклов составляет остовный подграф графа G.
Если циклы покрытия не имеют общих рёбер, покрытие называется рёберно непересекающимся или просто покрытием непересекающимися циклами[2].
Свойства и приложения
Покрытие Циклами Минимального Веса
Для взвешенных графов Задача о Покрытии Циклами Минимального Веса (ЗПЦМВ, англ. Minimum-Weight Cycle Cover Problem, MWCCP) является задачей поиска покрытия с минимальным суммарным весом по всем циклам покрытия.
Для планарных графов без мостов задача ЗПЦМВ может быть решена за полиномиальное время[3].
Циклическое k-покрытие
Циклическое k-покрытие графа — это семейство циклов, которое покрывает каждое ребро графа G ровно k раз. Было доказано, что любой граф без мостов имеет k-покрытие циклами для любого чётного числа . Для случая k=2 это известная гипотеза о двойном покрытии циклами, являющаяся открытой проблемой в теории графов. Гипотеза о двойном покрытии циклами утверждает, что в любом графе без мостов существует набор циклов, который дважды накрывает каждое ребро графа[4].
См. также
Примечания
- ↑ 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.
- ↑ Легко видеть, что имеется двоякий смысл последнего термина и по контексту должно быть указано, в каком смысле термин употребляется.
- ↑ Handbook in Graph Theory. — Boca Raton, London, New York, Washington D.C.: CRC PRESS, 2004. — С. 225. — ISBN 1-58488-090-2.
- ↑ «The Cycle Double Cover Conjecture». Дата обращения: 6 мая 2019. Архивировано 9 октября 2016 года.
Эта страница в последний раз была отредактирована 26 июля 2022 в 06:38.
Обычно почти сразу, изредка в течении часа.