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

Покриття́ ре́бер ци́клами (іноді просто покриття́ циклами) графа — це сімейство циклів, які є підграфами графа G і містять усі ребра графа G.

Якщо покривальні цикли не мають спільних вершин, покриття називають вершинно неперетинним або, іноді, просто покриттям циклами, що не перетинаються. У цьому випадку набір циклів утворює кістяковий підграф графа G.

Якщо цикли покриття не мають спільних ребер, покриття називають реберно неперетинним або просто покриттям циклами, що не перетинаються.

Властивості та застосування

Покриття циклами найменшої ваги

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

Для планарних графів без мостів ЗПЦМВ можна розв'язати за (поліноміальний час).

Циклічне k-покриття

Циклічне k-покриття графа — це сімейство циклів, яке покриває кожне ребро графа G рівно k разів. Доведено, що будь-який граф без мостів має k-покриття циклами для будь-якого парного числа ${\displaystyle k\geqslant 4}$. Для випадку k=2 це відома , що є відкритою проблемою в теорії графів. Вона стверджує, що в будь-якому графі без мостів існує набір циклів, який двічі накриває кожне ребро графа.

Див. також

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

Примітки

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