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

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

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

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

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

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

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

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

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

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

Див. також

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