Обложка вершинного цикла

В математике покрытие вершинного цикла (обычно называемое просто покрытием цикла ) графа G это набор циклов которые являются подграфами G , и содержат все вершины G. —

Если циклы покрытия не имеют общих вершин, то покрытие называют вершинно-непересекающимся или иногда просто непересекающимся цикловым покрытием . Иногда это называют точным покрытием вершинного цикла. В этом случае множество циклов образует подграф G остовный . Непересекающееся циклическое покрытие неориентированного графа (если оно существует) можно найти за полиномиальное время , превратив задачу в задачу поиска идеального паросочетания в большем графе. ^{[ 1 ]}^{[ 2 ]}

Если циклы покрытия не имеют общих ребер, то покрытие называется реберно-непересекающимся или просто непересекающимся цикловым покрытием .

Аналогичные определения существуют для орграфов в терминах направленных циклов. Нахождение вершинно-непересекающегося циклического покрытия ориентированного графа также может быть выполнено за полиномиальное время путем аналогичного сведения к идеальному сопоставлению . ^{[ 3 ]} Однако добавление условия, согласно которому каждый цикл должен иметь длину не менее 3, делает задачу NP-трудной . ^{[ 4 ]}

Свойства и применение

Постоянный

Перманент ориентированного равен (0,1)-матрицы числу вершинно-непересекающихся цикловых покрытий графа с данной матрицей смежности . Этот факт используется в упрощенном доказательстве, показывающем, что вычисление перманента является #P-полным . ^{[ 5 ]}

Накрытия минимального непересекающегося цикла

Задачи нахождения вершинно-непересекающихся и рёберно-непересекающихся цикловых покрытий с минимальным числом циклов NP-полны . Проблемы не в классе сложности APX . Вариантов орграфов также нет в APX. ^{[ 6 ]}

См. также

Покрытие реберного цикла — набор циклов, покрывающий все ребра G.

Ссылки

^ Дэвид Эппштейн . «Разбить граф на непересекающиеся по узлам циклы» .
^ Тутте, WT (1954), «Краткое доказательство факторной теоремы для конечных графов» (PDF) , Canadian Journal of Mathematics , 6 : 347–352, doi : 10.4153/CJM-1954-033-3 , MR 0063008 , S2CID 123221074 .
^ https://www.cs.cmu.edu/~avrim/451f13/recitation/rec1016.txt (проблема 1)
^ Гэри и Джонсон, Компьютеры и несговорчивость , GT13
^ Бен-Дор, Амир и Халеви, Шай. (1993). « Постоянный нуль-один #P -полный, более простое доказательство ». Труды 2-го Израильского симпозиума по теории и вычислительным системам , 108-117.
^ Сложность и аппроксимация: задачи комбинаторной оптимизации и их свойства аппроксимации (1999) ISBN 3-540-65431-3 стр.378, 379 , со ссылкой на Сахни, Сартадж ; Гонсалес, Теофило (1976), « P Задачи -полной аппроксимации» (PDF) , Journal of the ACM , 23 (3): 555–565, doi : 10.1145/321958.321975 , MR 0408313 , S2CID 207548581 .

[1] Дэвид Эппштейн . «Разбить граф на непересекающиеся по узлам циклы» .

[2] Тутте, WT (1954), «Краткое доказательство факторной теоремы для конечных графов» (PDF) , Canadian Journal of Mathematics , 6 : 347–352, doi : 10.4153/CJM-1954-033-3 , MR 0063008 , S2CID 123221074 .

[3] ttps://www.cs.cmu.edu/~avrim/451f13/recitation/rec1016.txt (проблема 1)

[4] Гэри и Джонсон, Компьютеры и несговорчивость , GT13

[5] Бен-Дор, Амир и Халеви, Шай. (1993). « Постоянный нуль-один #P -полный, более простое доказательство ». Труды 2-го Израильского симпозиума по теории и вычислительным системам , 108-117.

[6] Сложность и аппроксимация: задачи комбинаторной оптимизации и их свойства аппроксимации (1999) ISBN 3-540-65431-3 стр.378, 379 , со ссылкой на Сахни, Сартадж ; Гонсалес, Теофило (1976), « P Задачи -полной аппроксимации» (PDF) , Journal of the ACM , 23 (3): 555–565, doi : 10.1145/321958.321975 , MR 0408313 , S2CID 207548581 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]