Разрезающее циклы множество вершин

Материал из testwiki
Перейти к навигации Перейти к поиску

В теории графов разрезающее циклы множество вершин графа — это множество вершин, удаление которых приводит к разрыву циклов. Другими словами, разрезающее циклы множество вершин содержит по меньшей мере по одной вершине из любого цикла графа. Задача о разрезающем циклы множестве вершинШаблон:Переход является в теории вычислительной сложности NP-полной задачей. Задача входит в список 21 NP-полных задач Карпа. Задача имеет широкое применение в операционных системах, базах данных и разработке СБИС.

Определение

Задача о разрезающем циклы множестве вершин — это следующая задача разрешимости:

Дано: (Неориентированный или ориентированный) граф G=(V,E) и положительное число k.
Вопрос: Существует ли подмножество X⊆V, для которого |X|≤k, такой, что G с удалёнными вершинами, принадлежащими X, не содержит циклов?

Граф G[V∖X], оставшийся после удаления из графа G вершин, принадлежащих множеству X, является порождённым лесом (для неориентированных графов, или порождённым направленным ациклическим графом для ориентированных графов). Таким образом, поиск минимального разрезающего циклы множества вершин в графе эквивалентен поиску максимального порождённого леса (соответственно, максимального порождённого ациклического графа в случае ориентированных графов).

NP-трудность

КарпШаблон:Sfn показал, что задача о разрезающем циклы множестве вершин для ориентированных графов является NP-полной. Задача остаётся NP-полной для направленных графов с максимальной степенью входящих и исходящих дуг, равной двум, и для ориентированных пленарных графов с максимальной степенью входящих и исходящих дуг, равной трём[1]. Из приведения Карпа также следует NP-полнота задачи о разрезающем циклы множестве вершин на неориентированных графах, и задача остаётся NP-трудной на графах с максимальной степенью четыре. Задача о разрезающем циклы множестве вершин может быть решена за полиномиального времени на графах с максимальной степенью, не превосходящей трёхШаблон:SfnШаблон:Sfn.

Заметим, что задача удаления как можно меньшего числа рёбер для разрыва циклов (в неориентированном графе) эквивалентна нахождению остовного дерева, и эта задача может быть выполнена за полиномиальное время. В противоположность этому задача удаления рёбер из ориентированного графа с целью сделать его ациклическим, то есть задача о разрезающем циклы наборе дуг, является NP-полнойШаблон:Sfn.

Точные алгоритмы

Соответствующая NP-полная оптимизационная задача нахождения размера минимального разрезающего циклы множества вершин может быть решена за время O(1,7347n), где n — число вершин в графе Шаблон:Sfn. Фактически этот алгоритм находит максимальный порождённый лес и дополнение этого леса будет искомым набором вершин. Число минимальных разрезающих циклы множеств вершин ограничено O(1,8638n)Шаблон:Sfn. Задача о минимальном разрезающем циклы множестве для ориентированного графа может быть решена за время O*(1,9977n), где n — число вершин в данном ориентированном графеШаблон:Sfn. Параметризованные версии ориентированной и неориентированной задач Шаблон:Не переведено 5Шаблон:Sfn.

Приближение

Задача является APX-полной, что прямо следует из APX-сложности задачи о вершинном покрытииШаблон:Sfn и существования аппроксимации, сохраняющей L-приведение из задачи о вершинном покрытии к этой задачеШаблон:Sfn. Лучший известный алгоритм для неориентированных графов имеет коэффициент два[2].

Границы

Согласно теореме Эрдёша — Поза размер минимального разрезающего циклы множества вершин ограничен логарифмическим множителем от максимального числа вершинно-непересекающихся циклов в заданном графеШаблон:Sfn.

Приложения

В операционных системах разрезающее циклы множество вершин играет заметную роль в обнаружении взаимных блокировок (deadlock). В графе ожидания операционной системы каждый ориентированный цикл соответствует взаимной блокировке. Чтобы выйти из всех взаимных блокировок, некоторые блокированные процессы должны быть прерваны. Минимальное разрезающее циклы множество вершин в графе соответствует минимальному числу процессов, которые следует прерватьШаблон:Sfn

Кроме того, разрезающее циклы множество вершин имеет приложение в разработке СБИСШаблон:Sfn.

Примечания

Шаблон:Примечания

Литература

Исследовательские статьи и книги

Шаблон:Refbegin2

Шаблон:Refend

Учебники и обзорные статьи

Шаблон:Rq

  1. ↑ Неопубликованный результат, принадлежащий Гарей и Джонсону (Garey, Johnson), см. Шаблон:Sfn0: GT7
  2. ↑ Шаблон:Sfn0. См. также Шаблон:Sfn0 для альтернативного аппроксимационного алгоритма с тем же коэффициентом.
Источник — https://ru.wiki.beta.math.wmflabs.org/w/index.php?title=Разрезающее_циклы_множество_вершин&oldid=17966