Крышка цикла Edge - Edge cycle cover
В математика, крышка цикла края (иногда называют просто крышка цикла[1]) из график это семья циклы которые подграфы из грамм и содержат все ребра грамм.
Если циклы покрытия не имеют общих вершин, покрытие называется вершинно-непересекающийся а иногда просто непересекающееся покрытие цикла. В этом случае набор циклов составляет охватывающий подграф из грамм.
Если циклы покрытия не имеют общих ребер, покрытие называется непересекающийся по краям или просто непересекающееся покрытие цикла.
Свойства и приложения
Крышка цикла минимального веса
Для взвешенный график Задача о минимальном весе покрытия цикла (MWCCP) - это задача найти покрытие цикла с минимальной суммой весов ребер во всех циклах покрытия.
За без моста планарные графы MWCCP может быть решена в полиномиальное время. [2]
Цикл k-cover
А цикл k-крышка графа - это семейство циклов, покрывающих каждое ребро графа. грамм точно k раз. Было доказано, что каждый граф без мостов имеет цикл k-крышка для любого целого четного числа k≥4. За k = 2, это хорошо известный Гипотеза о двойном покрытии цикла - открытая проблема теории графов. В Гипотеза о двойном покрытии цикла заявляет, что в каждом без моста В графе существует набор циклов, которые вместе покрывают каждое ребро графа дважды.[3]