Чехол для велосипеда Edge
В теории графов , разделе математики , реберное циклическое покрытие (иногда называемое просто циклическим покрытием [1] ) графа — это семейство циклов , которые являются подграфами графа G и содержат все ребра графа G.
Если циклы покрытия не имеют общих вершин, покрытие называется вершинно -непересекающимся или иногда просто непересекающимся циклическим покрытием . В этом случае множество циклов образует остовной подграф графа G.
Если циклы покрытия не имеют общих ребер, покрытие называется рёберно-непересекающимся или просто покрытием непересекающихся циклов .
Свойства и применение
Покрытие для велосипеда с минимальным весом
Для взвешенного графа задача о циклическом покрытии минимального веса (MWCCP) — это задача нахождения циклического покрытия с минимальной суммой весов ребер во всех циклах покрытия.
Для планарных графов без мостов MWCCP может быть решена за полиномиальное время . [2]
Циклк-крышка
Цикл k -покрытие графа - это семейство циклов, которые покрывают каждое ребро графа G ровно k раз. Было доказано , что любой граф без мостов имеет цикл k -покрытие для любого четного целого числа k ≥4. Для k = 2 это хорошо известная гипотеза о двойном покрытии циклов - открытая проблема в теории графов. Гипотеза о двойном покрытии циклов утверждает, что в каждом графе без мостов существует набор циклов, которые вместе покрывают каждое ребро графа дважды. [3]
Смотрите также
Ссылки
- ^ Цунь-Цюань Чжан, Целочисленные потоки и циклические покрытия графов, Марсель Деккер, 1997.
- ^ "Справочник по теории графов" (2004) ISBN 1-58488-090-2 , стр. 225
- ^ ""The Cycle Double Cover Conjecture"". Архивировано из оригинала 20 июля 2011 г. Получено 21 декабря 2008 г.
 | Эта статья по теории графов — заглушка . Вы можете помочь Википедии, расширив ее. |
