Покрытие рёбер циклами (Hktjdmny j~Qyj entlgbn)

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

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

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

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

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

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

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

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

Циклическое k-покрытие графа — это семейство циклов, которое покрывает каждое ребро графа G ровно k раз. Было доказано, что любой граф без мостов имеет k-покрытие циклами для любого чётного числа $k\geqslant 4$ . Для случая 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 года.

[CQZ-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] Легко видеть, что имеется двоякий смысл последнего термина и по контексту должно быть указано, в каком смысле термин употребляется.

[HGT-3] Handbook in Graph Theory. — Boca Raton, London, New York, Washington D.C.: CRC PRESS, 2004. — С. 225. — ISBN 1-58488-090-2.

[DCC-4] «The Cycle Double Cover Conjecture» (неопр.). Дата обращения: 6 мая 2019. Архивировано 9 октября 2016 года.

[1]

[2]

[3]

[4]