Задача про незалежну множину

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Задача про незалежну множину відноситься до класу NP-повних задач в області теорії графів. Еквівалентна задачі про кліку.

Визначення[ред.ред. код]

Незалежний набір з 9 блакитних вершин

Множина вершин графа називається незалежною, якщо ніякі дві вершини цієї множини не з'єднані ребром. Іншими словами, індукований цією множиною підграф складається з ізольованих вершин. Іноді також говорять, що кожне ребро графа інцидентне не більше ніж одній вершині з незалежної множини. Задача розпізнавання (Проблема вибору) виглядає так: чи існує в заданому графі G незалежна множина розміру k? Відповідна їй оптимізаційна задача, вона ж задача про незалежну множину, формулюється таким чином: в заданому графі G потрібно знайти незалежну множину максимального розміру. Цей размір називають числом незалежності або числом внутрішньої стійкості і позначають як α(G).

Іноді цю задачу називають пошуком незалежної множини максимального розміру або максимальної (за розміром) незалежної множини. Не варто плутати це поняття з максимальною (по включенню) незалежною множиною, яка визначається як така незалежна множина вершин, що при додаванні до неї ще однієї (будь-якої) вершини початкового графа вона перестає бути незалежною. Зрозуміло, що таких множин, взагалі кажучи, може бути декілька і різних розмірів. Максимальною по включенню незалежна множина аж ніяк не завжди є максимальною за розміром. У той же час, кожна незалежна множина максимального розміру за визначенням є також і максимальною по включенню. Для знаходження (якоїсь) максимальної по включенню незалежної множини можна скористатися жадібним алгоритмом, який виконується за поліноміальний час, тоді як задача про незалежну множину максимального розміру належить до класу NP-повних задач.

Максимальна незалежна множина в дереві[ред.ред. код]

Якщо даний граф є деревом, то завдання про незалежну множину ефективно вирішується методом динамічного програмування.

Оптимальна підструктура задачи[ред.ред. код]

Структура дерева сама підказує рішення задачі: Позначимо коренем дерева будь-яку вершину і назвемо її r. Нехай I(u) позначає розмір максимальної незалежної множини вершин піддерева, коренем якого є вершина u. Тоді відповіддю на задачу буде I(r).

Неважко бачити, що якщо ми включаємо вершину u в максимальну незалежну множину, то її потужність збільшується на 1, але його дітей ми брати не можемо (так як вони з'єднані ребром з вершиною u); якщо ж ми не включаємо цю вершину, то потужність максимальної незалежної множини дорівнюватиме сумі розмірів незалежних множин дітей цієї вершини. Залишається тільки вибрати максимум з цих двох варіантів, щоб отримати рішення задачі:

I(u) = \max\left\{1\ +\  \sum_{\text{grandchild}\ w\  of\  u}I(w),\ \sum_{\text{child}\  w\  of\  u}I(w) \right\},

де grandchild позначає всякого «онука» вершини, а child позначає всякого нащадка вершини.

Псевдокод[ред.ред. код]

Вважаємо, що у вершині u зберігається I(u):

  function get_independent_set(Node u)
  {       
      якщо I(u) вже пораховане, то повернути I(u)
      //потужність множини, яку можна отримати, якщо не брати вершину u
      children_sum = 0
      //потужність множини, яку можна отримати, якщо взяти вершину u
      grandchildren_sum = 0
      //цикл по всім дітям
      for i := 1 to child_num do
         children_sum = children_sum + get_independent_set(children[i])
      //цикл по всіх онукам
      for i:= 1 to grandchildren_num
         grandchildren_sum = grandchildren_sum + get_independent_set(grandchildren[i])
      //запам'ятовуємо, щоб не перераховувати ще раз
      I(u) = max(1 + grandchildren_sum, children_sum)
     повернути I(u)
  }

Виклик get_independent_set(r) дасть відповідь на завдання. Час виконання алгоритму, очевидно, O(|V| + |E|).

Література[ред.ред. код]

  • Richard Karp Reducibility Among Combinatorial Problems // Proceedings of a Symposium on the Complexity of Computer Computations, (1972).
  • Michael R. Garey, David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5.  A1.2: GT20, pg.194.
  • Moon, J. W.; Moser, L. (1965), «On cliques in graphs», Israel J. Math. 3: 23–28, MR0182577 
  • Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani Algorithms. — 1-е вид. — McGraw-Hill Science/Engineering/Math, 2006. — С. 336. — ISBN 0073523402.


Див. також[ред.ред. код]

Посилання[ред.ред. код]