Покрытие рёбер циклами (иногда просто покрытие циклами) графа — это семейство циклов, которые являются подграфами графа G и содержат все рёбра графа G.
Если покрывающие циклы не имеют общих вершин, покрытие называется вершинно непересекающимся или, иногда, просто покрытием непересекающимися циклами. В этом случае набор циклов составляет остовный подграф графа G.
Если циклы покрытия не имеют общих рёбер, покрытие называется рёберно непересекающимся или просто покрытием непересекающимися цикламиЛегко видеть, что имеется двоякий смысл последнего термина и по контексту должно быть указано, в каком смысле термин употребляется..
Свойства и приложения
Покрытие Циклами Минимального Веса Для взвешенных графов Задача о Покрытии Циклами Минимального Веса (ЗПЦМВ, , MWCCP) является задачей поиска покрытия с минимальным суммарным весом по всем циклам покрытия.
Для планарных графов без мостов задача ЗПЦМВ может быть решена за полиномиальное время.
Циклическое k-покрытие Циклическое k-покрытие графа — это семейство циклов, которое покрывает каждое ребро графа G ровно k раз. Было доказано, что любой граф без мостов имеет k-покрытие циклами для любого чётного числа . Для случая k=2 это известная гипотеза о двойном покрытии циклами, являющаяся открытой проблемой в теории графов. Гипотеза о двойном покрытии циклами утверждает, что в любом графе без мостов существует набор циклов, который дважды накрывает каждое ребро графа.
См. также Гипотеза Алспаха Покрытие вершин циклами
Примечания
Категория:Объекты теории графов Категория:Комбинаторная оптимизация