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