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

Покриття́ ре́бер ци́клами (іноді просто покриття́ циклами[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». Архів оригіналу за 9 жовтня 2016. Процитовано 6 травня 2019.