Пређи на садржај

Независан скуп (теорија графова)

С Википедије, слободне енциклопедије

У теорији графова, независан скуп или стабилан скуп, представља скуп чворова у графу, тако да никоја два нису суседна. Тј., то је скуп I чворова тако да за свака два чвора из I, не постоји грана која их повезује. Еквивалентно, свака грана у графу има бар један крај у I. Величина независног скупа представља број чворова које тај скуп садржи. Независни скупови се такође зову и интерно стабилни скупови.[1] Максималан независан скуп је или независан скуп такав да ако му се дода неки други чвор он онда мора садржати и грану или је то скуп свих чворова празног графа. Максимум независан скуп је независан скуп највеће могуће величине за дати граф Г. Ова величина се назива независан број и обележава се са α(Г).[2] Проблем проналажења таквог скупа се назива проблем максимум независног скупа и он је НП-тежак проблем. Као такав, највероватније је да не постоји ефикасан алгоритам за проналажење максимум независног скупа.

Сваки максимум независан скуп је такође и максималан, али обрнуто не важи.


Карактеристике[уреди | уреди извор]

Веза са осталим параметрима графа[уреди | уреди извор]

Скуп је независан ако и само ако садржи клику у комплементу графа, тако да су та два концепта комплементарна. Заправо, довољно велики графови који немају велике клике имају велике независне скупове, ова тема је обрађена у Ремзијевој теорији.

Скуп је независан ако и само ако је његов комплемент покривач чворова .[3] Стога, сума највећег независног скупа α(Г) и најмањег покривача чворова β(Г) је једнака броју чворова у графу.

Бојење чворова у графу Г одговара партиционисању његовог скупа чворова на независне подскупове. Отуда је минималан број боја потребних да се обоје чворови, хроматски број χ(Г), барем количник броја чворова у графу Г и независног броја α(Г).

У бипартитном графу без изолованих чворова, број чворова у максимум независном скупу једнак је броју грана у минимум покривачу грана; ово је Кенигова теорема.

Максимални независни скуп[уреди | уреди извор]

Независан скуп који није подскуп другог независног скупа се назива максималним. Такви скупови представљају доминантне скупове. Сваки граф садржи највише 3н/3 максималних независних скупова,[4] али многи графови их имају далеко мање. Број максималних независних скупова је у циклусу са н цворова је дат Периновим бројевима,[5] а максимални независни скуп у стази са н чворова је дат Падовановим низом. Стога, оба броја су пропорционална квадрату од 1.324718, пластичном броју.

Проналажење независних скупова[уреди | уреди извор]

У рачунарству, неколико проблема повезаних са независним скуповима је проучено.

  • У проблему максимум независног скупа улаз је неусмерен граф, а излаз је максимум независни скуп графа. Ако постоји више максимум независних скупова, само један се враћа као излаз. Проблем се понекад зове „паковање графа”.
  • У проблему максимум-тежинама независном скупу' улаз је неусмерен граф са тежинама на својим чворовима, а излаз је независан скуп са максимум укупном тежином. Максимум независан скуп је специјалан случај овог проблема када су све тежине једнаке 1.
  • У проблему листе максималних независних скупова', улаз је неусмерен граф, а излаз је листа свих његових максималних независних скупова. Проблем максимум независног скупа може бити решен користећи подрутину алгоритма за листу максималних независних скупова, зато што се максимум независан скуп мора налазити међу свим максималним независним скуповима.
  • У проблему одређивања независног скупа, улаз је неусмерен граф и број к, а излаз је тачно ако граф садржи независан скуп величине к, а нетачно ако не садржи.

Прва три од ових поблема су битни због практичне примене,а проблем одређивања независног скупа није, али је неопходан да би се применила теорија о НП-комплетности на проблеме повезане са независним скуповима.

Максимум независни скупови и максимум клике[уреди | уреди извор]

Проблем независног скупа и проблем клике су комплементарни: клика у графу Г је независан скуп у комплементу графа Г и обрнуто. Стога, многи рачунарски резултати могу бити примењени на било који од два проблема. На пример, резултати везани за проблем клике имају следеће последице:

  • Проблем одређивања независног скупа је НП-комплетан и отуда се не верује да постоји ефикасан алгоритам за његово решавање.
  • Проблем максимум независног скупа је НП-тежак и такође је тежак за апроксимацију.

Без обзира на блиску повезаност проблема максимум клике и максимум независног скупа у произвољним графовима, ова два проблема могу доста да се разликују при примени на неке специјалне врсте графова. На пример, у ретким графовима , максимум клика је ограничене величине и може бити пронађена у линеарном времену;[6] међутим, за исту класу графова, или за чак ограниченије графове са ограниченим степеном, налажење максимум независног скупа је МАXСНП-комплетан , што значи да, за неку константу ц (у зависности од степена) НП-тешко је наћи солуцију која ће да апроксимира решење за константан фактор ц. [7]

Прецизни алгоритми[уреди | уреди извор]

Проблем максимум независног скупа је НП-тежак. Међутим, он може бити решен ефикасније од О(н2 2н)што би била сложеност наивног алгоритма грубе силе који испитује сваки подскуп чворова и проверава да ли је он независан скуп.

Робсонов алгоритам решава проблем у времену О(1.2108н) користећи експоненцијални простор. Када се ограничи на полиномијални простор, његова временска сложеност је О(1.2127н)[8] што је боље од обичног алгоритма сложености О(1.2209н).

Код неких врста графова, укључујући графове без “канџе” и савршене графове, максимум независни скуп се може пронаћи у полиномијалном времену.

Код бипартитних графова, сви чворови који се не налазе у минимум покривачу чворова се могу укључити у максимум независни скуп; погледати Кенигову теорему. Стога, минимум покривач чворова се може пронаћи користећи алгоритам бипартитног упаривања.

Приближни алгоритми[уреди | уреди извор]

Углавном, проблем максимум независног скупа не може да се апроксимира на константан фактор у полиномијалном времену (осим ако важи П=НП). Заправо овај проблем је Полy-АПX комплетан , што га чини тешким као било који проблем који може да се апроксимира на полиномијални фактор.[9] Међутим, постоје ефикасни приближни алгоритми за одређене врсте графова.

Код планарних графова, максимум независни скуп се може апроксимирати са односом апроксимације 'ц < 1 у полиномијалном времену; .[10]

У графовима са ограниченим степеном, познати су алгоритми ефективне апроксимације са односима апроксимације који су константни за фиксирану вредност максималног степена; на пример, похлепни алгоритам који формира максималан независан скуп бирајући у сваком кораку чвор са најмањим степеном у графу и уклањајући његове суседе, постиже однос апроксимације од (Δ+2)/3 у графовима са максималним степеном Δ.[10] Заиста, и максимум независан скуп на 3-регуларним и 3-обојивим графовима је АПX комплетан.[11]

Независни скупови у графовима са укрштајућим интервалима[уреди | уреди извор]

Интервални граф је граф чији су чворови једнодимензиони интервали ( временски интервали) и постоји грана између два интервала ако се преклапају. Независан скуп у интервалним графовима је само скуп интервала који се не преклапају. Проблем проналажења максимум независног скупа у интервалним графовима је проучаван, на пример, у контексту распореда активности: дат је скуп активности које треба да буду извршене на рачунару, пронаћи максимум скуп активности које могу да буду извршене без преплитања са другим активностима. Овај проблем може бити решен у полиномијалном времену користећи распоређивање по времену завршетка.


Независни скупови у геомтријским укрштајућим графовима[уреди | уреди извор]

Геометријски укрштајући граф је граф чији су сви чворови геометријски облици и постоји грана између два облика ако се преплићу. Независан скуп у овим графовима је само скуп облика који се не преплићу. Проблем проналажења независног скупа у овим графовима је, на пример, проучаван у контексту Аутоматске замене ознака: дат је скуп локација на мапи, пронаћи максимлан скуп раздвојених правоугаоних ознака у близини тих локација.

Проналажење максимум независног скупа у овим графовима је НП-комплетан, али је лакши за апроксимацију него проблем максимум независног скупа. Скорија истраживања могу бити пронађена у[12]

Проналажење максималног независног скупа[уреди | уреди извор]

Проблем проналажења максималног независног скупа може бити решен у полиномијланом времену[13] користећи тривијалан похлепни алгоритам. Сви максимални независни скупови могу бити пронађени у времену О(3н/3) = О(1.4423н).

Види још[уреди | уреди извор]

  • Независан скуп грана је скуп грана где никоје две гране немају заједнички чвор. Обично се назива упаривање.
  • Бојење чворова је партиционисање скупа чворова на независне скупове.

Референце[уреди | уреди извор]

  1. ^ Корсхунов 1974
  2. ^ Годсил & Роyле 2001. стр. 3.
  3. ^ ПРООФ: А сет V оф вертицес ис ан индепендент сет ИФФ еверy едге ин тхе грапх ис адјацент то ат мост оне мембер оф V ИФФ еверy едге ин тхе грапх ис адјацент то ат леаст оне мембер нот ин V ИФФ тхе цомплемент оф V ис а вертеx цовер.
  4. ^ Моон & Мосер 1965
  5. ^ Фüреди 1987
  6. ^ Цхиба & Нисхизеки 1985
  7. ^ Берман & Фујито 1995
  8. ^ Боургеоис ет ал. 2010
  9. ^ Базган, Цристина; Есцоффиер, Бруно; Пасцхос, Вангелис Тх. (2005). „Цомплетенесс ин стандард анд дифферентиал аппроxиматион цлассес: Полy-(D)АПX- анд (D)ПТАС-цомплетенесс”. Тхеоретицал Цомпутер Сциенце. 339 (2-3): 272—292. дои:10.1016/ј.тцс.2005.03.007. 
  10. ^ а б Бакер 1994; Грохе 2003
  11. ^ Цхлебíк, Мирослав; Цхлебíковá, Јанка (2003). „Аппроxиматион Харднесс фор Смалл Оццурренце Инстанцес оф НП-Хард Проблемс”. Процеедингс оф тхе 5тх Интернатионал Цонференце он Алгоритхмс анд Цомплеxитy. 
  12. ^ Цхан & Хар-Пелед 2012
  13. ^ Лубy 1986

Спољашње везе[уреди | уреди извор]

Преузето из „https://sr.wikipedia.org/w/index.php?title=Nezavisan_skup_(teorija_grafova)&oldid=27753893”