Максимальна незалежна множина

Граф куба має шість різних незалежних множин, позначені червоними вершинами

Максимальна незалежна множина або максимальна стабільна множина — незалежна множина, яка не є підмножиною будь-якої іншої незалежної множини. Тобто, це множина S така, що кожне ребро графа має один кінець не в S і кожна вершина не з S має щонайменше одного сусіда в S. Максимальна незалежна множина також є домінівною множиною графа, і кожна домінівна множина, що також незалежна повинна бути максимальною незалежною, отже максимальні незалежні множини також називають незалежними домінівними множинами. Граф може мати багато максимальних множин дуже відмінних розмірів;^[1] a якнайбільшу з максимальних незалежних множин називають найбільшою незалежною множиною.

Наприклад, у графі P₃, шлях з трьох вершин a, b і c і двох ребер ab і bc, обидві множини {b} і {a,c} максимальні незалежні. Множина {a} незалежна, але не максимальна, бо це підмножина більшої незалежної множини {a,c}. У цьому ж графі, максимальні кліки це множини {a,b} і {b,c}.

Фраза «максимальна незалежна множина» також використовується для опису максимальних підмножин незалежних елементів не тільки в графах, зокрема у векторних просторах і матроїдах.

Пов'язані множини вершин

Якщо S це максимальна незалежна множина деякого графа, то вона також і максимальна кліка або ж максимальний повний підграф у доповненні графа. Максимальна кліка це множина вершин, які породжують повний підграф і також, яка не міститься в якомусь більшому повному графі. Тобто, це множина S така, що кожна двійка вершин з S зв'язана ребром і кожній вершині не з S не вистачає щонайменше одного ребра до однієї з вершин в S. Граф може мати багато найбільших клік, різних розмірів; знаходження якнайбільшої з них є задачею максимальної кліки.

Деякі автори включають максимальність як частину визначення кліки, і називають максимальні кліки просто кліками.

Доповнення максимильної незалежної множини, тобто набір вершин, що не належать до неї, утворюють мінімальне вершинне покриття. Тобто, доповнення це вершинне покриття, множина вершин така, яка включає щонайменше по одному кінцю кожного ребра, і мінімальна в розумінні того, що жодну з цих вершин не можна видалити, щоб властивість покриття збереглась. Мінімальні вершинні покриття вивчались у статистичній механіці у зв'язку з моделями твердокулькових газових ґраток, математична абстракція для переходів плин-тверде тіло.^[2]

Кожна максимальна незалежна множина також і домінівна, тобто така множина вершин, що кожна вершина графа або належить до цієї множини або є суміжною з нею. Множина вершин є максимальною незалежною множиною тоді і тільки тоді коли вона є незалежною домінівною множиною.

Характеризація сімей графів

Певні сім'ї графів також можна характеризувати в термінах максимальних клік або максимальних незалежних підмножин. Приклади включають графи з незвідними максимальними кліками і спадково незвідними кліками. Кажуть, що граф має незвідні максимальні кліки, якщо кожна максимальна кліка містить ребро яке не належить до жодної іншої максимальної кліки, і що граф має спадково незвідні максимальні кліки, якщо ця ж властивість виконується в будь-якому вершинно-породженому підграфі, тобто такому графі, що утворюється підмножиною вершин разом з усіма ребрами обидва кінці яких належать до цієї підмножини.

Кографи можна характеризувати як графи, в яких кожна максимальна кліка перетинає кожну максимальну незалежну множину і в яких ця властивість додержується в усіх вершинно-породжених підграфах.

Обмеження на кількість множин

Moon та Moser, (1965) показали, що будь-який граф з n вершинами має не більше 3^n/3 максимальних клік. Аргументуючи через доповнення графа маємо, будь-який граф з n вершинами також має не більше 3^n/3 максимальних незалежних множин. Легко побудувати граф із саме 3^n/3 максимальними незалежними множинами: просто взяти неперетинну множину з n/3 трикутних графів. Усяка максимальна незалежна множина в цьому графі утворюється вибиранням однієї вершини з кожного трикутника. Доповнення графа має саме 3^n/3 максимальних клік і є особливим типом графа Турана; через зв'язок таких графів з обмеженням Муна і Мозера, ці графи іноді також називають графами Муна-Мозера. Тісніша межа можлива за умови обмеження розміру максимальної незалежної множини: кількість максимальних незалежних множин розміру k в кожному n-вершинному графі є щонайбільше

\lfloor n/k\rfloor ^{k-(n{\bmod {k}})}\lfloor n/k+1\rfloor ^{n{\bmod {k}}}.

Графи, що досягли цієї межі знов-таки є графами Турана.^[3]

Деякі сім'ї графів, однак, мають набагато суворіші обмеження на кількість максимальних незалежних множин або максимальних клік. Якщо всі n-вершинні графи у сім'ї графів мають O(n) ребер, і якщо кожний підграф графа в цій сім'ї також належить до цієї сім'ї, тоді кожний граф у сім'ї має щонайбільше O(n) максимальних клік, і всі вони мають розмір O(1).^[4] Наприклад, ці умови істинні для планарного графа: кожен n-вершинний планарний граф має щонайбільше 3n − 6 ребер і підграф планарного графа завжди планарний, з цього випливає, що кожен планарний граф має O(n) максимальних клік (розміром не більше чотирьох). Проміжкові графи і хордові графи також мають не більше ніж n максимальних клік, навіть хоча вони не завжди насичені.

Кількість максимальних незалежних множин у n-вершинному граф-циклі дорівнює числу Перріна, а кількість максимальних незалежних множин у n-вершинному шляху дорівнює послідовності Падована.^[5] Отже, обидві кількості пропорційні степеням 1.324718, пластичного числа.

Алгоритми перелічення множин

Алгоритм для перелічування всіх максимальних незалежних множин або максимальних клік у графі можна використати як підпрограму для розв'язання багатьох NP-повних задач на графах. Найочевидніші — задачі про максимальну незалежну множину, мінімальну незалежну домінівну множину і максимальну кліку. Кожну з них можна розв'язати із використанням алгоритму, який перелічує максимальні незалежні множини або максимальні кліки і обирає ті з них, які мають найбільший або найменший розмір. Схожим чином, найменше вершинне покриття можна знайти як доповнення до однієї з максимальних незалежних множин. Lawler, (1976) спостеріг, що перелік максимальних незалежних множин можна використати для знаходження 3-фарбування графа: граф можна 3-фарбувати тоді і тільки тоді, якщо доповнення до одної з його максимальних незалежних множин є двочастковим. Він використовував цей підхід не тільки для 3-фарбування, але й як частину загальнішого алгоритму фарбування графа, в наступному, подібні підходи до фарбування графа були вдосконалені іншими авторами.^[6] Інші, складніші задачі також можна змоделювати як знаходження кліки або незалежної множини певного типу. Це спонукає до розв'язання алгоритмічної проблеми перелічення всіх максимальних незалежних множин (або тотожно, всіх максимальних клік) ефективно.

Досить просто перетворити доведення 3^n/3 обмеження на кількість максимальних незалежних множин Муна і Мозера в алгоритм, що перелічує всі такі множини за час O(3^n/3).^[7] Для графів, що мають якнайбільшу можливу кількість максимальних незалежних множин, цей алгоритм потребує константного часу на одну множину на виході. Однак, алгоритм з такими часовими характеристиками може бути надто неефективним для графів більш обмеженою кількістю незалежних множин. Через це, багато дослідників вивчали алгоритми, які перебирають усі максимальні незалежні множини за поліноміальний час на одну множину на виході.^[8] Час потрібний на одну незалежну множину пропорційний до часу на множення матриць у насичених графах або швидше в різних класах розріджених графів.^[9]

Примітки

↑ Erdős, (1966) показує, що кількість різних розмірів максимальних незалежних множин у графі з n вершинами може бути завбільшки як n - log n - O(log log n) і ніколи не більше ніж n - log n.
↑ Weigt та Hartmann, (2001).
↑ Byskov, (2003). Для пов'язаних попередніх результатів Croitoru, (1979) і Eppstein, (2003).
↑ Chiba та Nishizeki, (1985). Виразили умову мати O(n) ребер еквівалентно через константність деревності графа.
↑ Bisdorff та Marichal, (2007); Euler, (2005); Füredi, (1987).
↑ Eppstein, (2003); Byskov, (2003).
↑ Eppstein, (2003). Для відповідних границь у широко використовному алгоритмі Брона-Кербоша, див. Tomita, Tanaka та Takahashi, (2006).
↑ Bomze та ін., (1999); Eppstein, (2005); Jennings та Motycková, (1992); Johnson, Yannakakis та Papadimitriou, (1988); Lawler, Lenstra та Rinnooy Kan, (1980); Liang, Dhall та Lakshmivarahan, (1991); Makino та Uno, (2004); Mishra та Pitt, (1997); Stix, (2004); Tsukiyama та ін., (1977); Yu та Chen, (1993).
↑ Makino та Uno, (2004); Eppstein, (2005).

Посилання

Граф зі спадково незвідними максимальними кліками [Архівовано 29 листопада 2014 у Wayback Machine.] на Graphclass (англ.)
Граф з незвідними максимальними кліками [Архівовано 29 листопада 2014 у Wayback Machine.] на Graphclass (англ.)

[1] Erdős, (1966) показує, що кількість різних розмірів максимальних незалежних множин у графі з n вершинами може бути завбільшки як n - log n - O(log log n) і ніколи не більше ніж n - log n.

[2] Weigt та Hartmann, (2001).

[3] Byskov, (2003). Для пов'язаних попередніх результатів Croitoru, (1979) і Eppstein, (2003).

[4] Chiba та Nishizeki, (1985). Виразили умову мати O(n) ребер еквівалентно через константність деревності графа.

[5] Bisdorff та Marichal, (2007); Euler, (2005); Füredi, (1987).

[6] Eppstein, (2003); Byskov, (2003).

[7] Eppstein, (2003). Для відповідних границь у широко використовному алгоритмі Брона-Кербоша, див. Tomita, Tanaka та Takahashi, (2006).

[8] Bomze та ін., (1999); Eppstein, (2005); Jennings та Motycková, (1992); Johnson, Yannakakis та Papadimitriou, (1988); Lawler, Lenstra та Rinnooy Kan, (1980); Liang, Dhall та Lakshmivarahan, (1991); Makino та Uno, (2004); Mishra та Pitt, (1997); Stix, (2004); Tsukiyama та ін., (1977); Yu та Chen, (1993).

[9] Makino та Uno, (2004); Eppstein, (2005).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]