Перегляд вихідного коду сторінки Задача про незалежну множину

'''Задача про незалежну множину''' належить до класу [[NP-повна задача|NP-повних задач]] в області [[Теорія графів|теорії графів]]. Еквівалентна задачі про [[Кліка (теорія графів)|кліку]].

== Визначення ==
[[Файл:Independent_set_graph.gif|right|frame|Незалежний набір з 9 блакитних вершин]]

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

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

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

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

=== Оптимальна підструктура задач ===

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

Неважко бачити, що якщо ми включаємо вершину ''u'' в максимальну незалежну множину, то її [[Потужність множини|потужність]] збільшується на 1, але його дітей ми брати не можемо (так як вони з'єднані ребром з вершиною ''u''); якщо ж ми не включаємо цю вершину, то потужність максимальної незалежної множини дорівнюватиме сумі розмірів незалежних множин дітей цієї вершини. Залишається тільки вибрати максимум з цих двох варіантів, щоб отримати рішення задачі:
: <math>I(u) = \max\left\{1\ +\  \sum_{\text{grandchild}\ w\  of\  u}I(w),\ \sum_{\text{child}\  w\  of\  u}I(w) \right\},</math>
де grandchild позначає всякого «онука» вершини, а child позначає всякого нащадка вершини.

=== Псевдокод ===
Вважаємо, що у вершині u зберігається <math>I(u)</math>:

   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|).

== Література ==
* {{cite book
  | last = Godsil
  | first = Chris
  | coauthors = Gordon Royle
  | title = Algebraic Graph Theory
  | publisher = [[Springer]]
  | origyear = 1949
  | year = 2004
  | location=New York
  | ref = godsil49
  | isbn = 0-387-95220-9 }}

* {{cite journal |author=Richard Karp |title=Reducibility Among Combinatorial Problems |journal=Proceedings of a Symposium on the Complexity of Computer Computations |year=1972}}

* {{cite book|author = Michael R. Garey, David S. Johnson | year = 1979 | title = Computers and Intractability: A Guide to the Theory of NP-Completeness |url = https://archive.org/details/computersintract0000gare | publisher = W.H. Freeman | id = ISBN 0-7167-1045-5}} A1.2: GT20, pg.194.

* {{citation
 | last1 = Moon | first1 = J. W. 
 | last2 = Moser | first2 = L.
 | title = On cliques in graphs
 | journal = Israel J. Math.
 | volume = 3
 | year = 1965
 | pages = 23–28
 | id = {{MathSciNet | id = 0182577}}}}

* {{книга 
|глава        = Chapter 6. Dynamic Programming
|автор        = Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani
|заголовок     = Algorithms
|посилання       = http://www.cs.berkeley.edu/~vazirani/algorithms.html
|видання      = 1-е вид 
|видавництво = McGraw-Hill Science/Engineering/Math
|рік          = 2006
|сторінки     = 336
|isbn         = 0073523402
}}
            

== Див. також ==

* [[Алгоритм Брона-Кербоша]] для знаходження максимальних по включенню незалежних множин вершин.

== Посилання ==
* {{MathWorld|urlname=MaximalIndependentVertexSet|title=Maximal Independent Vertex Set}}
* [http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring] {{Webarchive|url=https://web.archive.org/web/20130529163947/http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm |date=29 травня 2013 }}
* Полікарпова Н., Герасименко А. [https://web.archive.org/web/20130318015327/http://rain.ifmo.ru/cat/view.php/theory/unsorted/approx-2004 Метод рішення важкорозв'язуваних задач]
* [http://logic.pdmi.ras.ru/~kulikov/simplealgscourse/lecture7-slides.pdf Слайди лекції по динамічному програмуванні] {{Webarchive|url=https://web.archive.org/web/20090419062718/http://logic.pdmi.ras.ru/~kulikov/simplealgscourse/lecture7-slides.pdf |date=19 квітня 2009 }}

{{NP-повні задачі}}

[[Категорія:Теорія графів]]
[[Категорія:Алгоритми на графах]]
[[Категорія:Динамічне програмування]]