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