Покриття́ ре́бер ци́клами (іноді просто покриття́ циклами) графа — це сімейство циклів, які є підграфами графа G і містять усі ребра графа G.
Якщо покривальні цикли не мають спільних вершин, покриття називають вершинно неперетинним або, іноді, просто покриттям циклами, що не перетинаються. У цьому випадку набір циклів утворює кістяковий підграф графа G.
Якщо цикли покриття не мають спільних ребер, покриття називають реберно неперетинним або просто покриттям циклами, що не перетинаютьсяОчевидно, що зміст останнього терміна неоднозначний, і в контексті має бути зазначено, в якому сенсі термін використовується..
Властивості та застосування
Покриття циклами найменшої ваги Для зважених графів задача про покриття циклами найменшої ваги (ЗПЦМВ, , MWCCP) є задачею пошуку покриття з найменшою сумарною вагою за всіма циклами покриття.
Для планарних графів без мостів ЗПЦМВ можна розв'язати за поліноміальний час.
Циклічне k-покриття Циклічне k-покриття графа — це сімейство циклів, яке покриває кожне ребро графа G рівно k разів. Доведено, що будь-який граф без мостів має k-покриття циклами для будь-якого парного числа . Для випадку k=2 це відома гіпотеза про подвійне покриття циклами, що є відкритою проблемою в теорії графів. Вона стверджує, що в будь-якому графі без мостів існує набір циклів, який двічі накриває кожне ребро графа.
Див. також Гіпотеза Алспаха Покриття вершин циклами
Примітки