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