Покриття ребер циклами
Покриття́ ре́бер ци́клами (іноді просто покриття́ циклами[1]) графа — це сімейство циклів, які є підграфами графа G і містять усі ребра графа G.
Якщо покривальні цикли не мають спільних вершин, покриття називають вершинно неперетинним або, іноді, просто покриттям циклами, що не перетинаються. У цьому випадку набір циклів утворює кістяковий підграф графа G.
Якщо цикли покриття не мають спільних ребер, покриття називають реберно неперетинним або просто покриттям циклами, що не перетинаються[2].
Властивості та застосування ред.
Покриття циклами найменшої ваги ред.
Для зважених графів задача про покриття циклами найменшої ваги (ЗПЦМВ, англ. Minimum-Weight Cycle Cover Problem, MWCCP) є задачею пошуку покриття з найменшою сумарною вагою за всіма циклами покриття.
Для планарних графів без мостів ЗПЦМВ можна розв'язати за поліноміальний час[3].
Циклічне k-покриття ред.
Циклічне k-покриття графа — це сімейство циклів, яке покриває кожне ребро графа G рівно k разів. Доведено, що будь-який граф без мостів має k-покриття циклами для будь-якого парного числа . Для випадку k=2 це відома гіпотеза про подвійне покриття циклами, що є відкритою проблемою в теорії графів. Вона стверджує, що в будь-якому графі без мостів існує набір циклів, який двічі накриває кожне ребро графа[4].
Див. також ред.
Примітки ред.
- ↑ 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.
- ↑ Очевидно, що зміст останнього терміна неоднозначний, і в контексті має бути зазначено, в якому сенсі термін використовується.
- ↑ Handbook in Graph Theory. — Boca Raton, London, New York, Washington D.C. : CRC PRESS, 2004. — С. 225. — ISBN 1-58488-090-2.
- ↑ «The Cycle Double Cover Conjecture». Архів оригіналу за 9 жовтня 2016. Процитовано 6 травня 2019.