Nezavisan skup (teorija grafova)

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

U teoriji grafova, nezavisan skup ili stabilan skup, predstavlja skup čvorova u grafu, tako da nikoja dva nisu susedna. Tj., to je skup I čvorova tako da za svaka dva čvora iz I, ne postoji grana koja ih povezuje. Ekvivalentno, svaka grana u grafu ima bar jedan kraj u I. Veličina nezavisnog skupa predstavlja broj čvorova koje taj skup sadrži. Nezavisni skupovi se takođe zovu i interno stabilni skupovi.[1] Maksimalan nezavisan skup je ili nezavisan skup takav da ako mu se doda neki drugi čvor on onda mora sadržati i granu ili je to skup svih čvorova praznog grafa. Maksimum nezavisan skup je nezavisan skup najveće moguće veličine za dati graf G. Ova veličina se naziva nezavisan broj i obeležava se sa α(G).[2] Problem pronalaženja takvog skupa se naziva problem maksimum nezavisnog skupa i on je NP-težak problem. Kao takav, najverovatnije je da ne postoji efikasan algoritam za pronalaženje maksimum nezavisnog skupa.

Svaki maksimum nezavisan skup je takođe i maksimalan, ali obrnuto ne važi.


Karakteristike[уреди | уреди извор]

Veza sa ostalim parametrima grafa[уреди | уреди извор]

Skup je nezavisan ako i samo ako sadrži kliku u komplementu grafa, tako da su ta dva koncepta komplementarna. Zapravo, dovoljno veliki grafovi koji nemaju velike klike imaju velike nezavisne skupove, ova tema je obrađena u Remzijevoj teoriji.

Skup je nezavisan ako i samo ako je njegov komplement pokrivač čvorova .[3] Stoga, suma najvećeg nezavisnog skupa α(G) i najmanjeg pokrivača čvorova β(G) je jednaka broju čvorova u grafu.

Bojenje čvorova u grafu G odgovara particionisanju njegovog skupa čvorova na nezavisne podskupove. Otuda je minimalan broj boja potrebnih da se oboje čvorovi, hromatski broj χ(G), barem količnik broja čvorova u grafu G i nezavisnog broja α(G).

U bipartitnom grafu bez izolovanih čvorova, broj čvorova u maksimum nezavisnom skupu jednak je broju grana u minimum pokrivaču grana; ovo je Kenigova teorema.

Maksimalni nezavisni skup[уреди | уреди извор]

Nezavisan skup koji nije podskup drugog nezavisnog skupa se naziva maksimalnim. Takvi skupovi predstavljaju dominantne skupove. Svaki graf sadrži najviše 3n/3 maksimalnih nezavisnih skupova,[4] ali mnogi grafovi ih imaju daleko manje. Broj maksimalnih nezavisnih skupova je u ciklusu sa n cvorova je dat Perinovim brojevima,[5] a maksimalni nezavisni skup u stazi sa n čvorova je dat Padovanovim nizom. Stoga, oba broja su proporcionalna kvadratu od 1.324718, plastičnom broju.

Pronalaženje nezavisnih skupova[уреди | уреди извор]

U računarstvu, nekoliko problema povezanih sa nezavisnim skupovima je proučeno.

  • U problemu maksimum nezavisnog skupa ulaz je neusmeren graf, a izlaz je maksimum nezavisni skup grafa. Ako postoji više maksimum nezavisnih skupova, samo jedan se vraća kao izlaz. Problem se ponekad zove „pakovanje grafa”.
  • U problemu maksimum-težinama nezavisnom skupu' ulaz je neusmeren graf sa težinama na svojim čvorovima, a izlaz je nezavisan skup sa maksimum ukupnom težinom. Maksimum nezavisan skup je specijalan slučaj ovog problema kada su sve težine jednake 1.
  • U problemu liste maksimalnih nezavisnih skupova', ulaz je neusmeren graf, a izlaz je lista svih njegovih maksimalnih nezavisnih skupova. Problem maksimum nezavisnog skupa može biti rešen koristeći podrutinu algoritma za listu maksimalnih nezavisnih skupova, zato što se maksimum nezavisan skup mora nalaziti među svim maksimalnim nezavisnim skupovima.
  • U problemu određivanja nezavisnog skupa, ulaz je neusmeren graf i broj k, a izlaz je tačno ako graf sadrži nezavisan skup veličine k, a netačno ako ne sadrži.

Prva tri od ovih poblema su bitni zbog praktične primene,a problem određivanja nezavisnog skupa nije, ali je neophodan da bi se primenila teorija o NP-kompletnosti na probleme povezane sa nezavisnim skupovima.

Maksimum nezavisni skupovi i maksimum klike[уреди | уреди извор]

Problem nezavisnog skupa i problem klike su komplementarni: klika u grafu G je nezavisan skup u komplementu grafa G i obrnuto. Stoga, mnogi računarski rezultati mogu biti primenjeni na bilo koji od dva problema. Na primer, rezultati vezani za problem klike imaju sledeće posledice:

  • Problem određivanja nezavisnog skupa je NP-kompletan i otuda se ne veruje da postoji efikasan algoritam za njegovo rešavanje.
  • Problem maksimum nezavisnog skupa je NP-težak i takođe je težak za aproksimaciju.

Bez obzira na blisku povezanost problema maksimum klike i maksimum nezavisnog skupa u proizvoljnim grafovima, ova dva problema mogu dosta da se razlikuju pri primeni na neke specijalne vrste grafova. Na primer, u retkim grafovima , maksimum klika je ograničene veličine i može biti pronađena u linearnom vremenu;[6] međutim, za istu klasu grafova, ili za čak ograničenije grafove sa ograničenim stepenom, nalaženje maksimum nezavisnog skupa je MAXSNP-kompletan , što znači da, za neku konstantu c (u zavisnosti od stepena) NP-teško je naći soluciju koja će da aproksimira rešenje za konstantan faktor c. [7]

Precizni algoritmi[уреди | уреди извор]

Problem maksimum nezavisnog skupa je NP-težak. Međutim, on može biti rešen efikasnije od O(n2 2n)što bi bila složenost naivnog algoritma grube sile koji ispituje svaki podskup čvorova i proverava da li je on nezavisan skup.

Robsonov algoritam rešava problem u vremenu O(1.2108n) koristeći eksponencijalni prostor. Kada se ograniči na polinomijalni prostor, njegova vremenska složenost je O(1.2127n)[8] što je bolje od običnog algoritma složenosti O(1.2209n).

Kod nekih vrsta grafova, uključujući grafove bez “kandže” i savršene grafove, maksimum nezavisni skup se može pronaći u polinomijalnom vremenu.

Kod bipartitnih grafova, svi čvorovi koji se ne nalaze u minimum pokrivaču čvorova se mogu uključiti u maksimum nezavisni skup; pogledati Kenigovu teoremu. Stoga, minimum pokrivač čvorova se može pronaći koristeći algoritam bipartitnog uparivanja.

Približni algoritmi[уреди | уреди извор]

Uglavnom, problem maksimum nezavisnog skupa ne može da se aproksimira na konstantan faktor u polinomijalnom vremenu (osim ako važi P=NP). Zapravo ovaj problem je Poly-APX kompletan , što ga čini teškim kao bilo koji problem koji može da se aproksimira na polinomijalni faktor.[9] Međutim, postoje efikasni približni algoritmi za određene vrste grafova.

Kod planarnih grafova, maksimum nezavisni skup se može aproksimirati sa odnosom aproksimacije 'c < 1 u polinomijalnom vremenu; .[10]

U grafovima sa ograničenim stepenom, poznati su algoritmi efektivne aproksimacije sa odnosima aproksimacije koji su konstantni za fiksiranu vrednost maksimalnog stepena; na primer, pohlepni algoritam koji formira maksimalan nezavisan skup birajući u svakom koraku čvor sa najmanjim stepenom u grafu i uklanjajući njegove susede, postiže odnos aproksimacije od (Δ+2)/3 u grafovima sa maksimalnim stepenom Δ.[10] Zaista, i maksimum nezavisan skup na 3-regularnim i 3-obojivim grafovima je APX kompletan.[11]

Nezavisni skupovi u grafovima sa ukrštajućim intervalima[уреди | уреди извор]

Intervalni graf je graf čiji su čvorovi jednodimenzioni intervali ( vremenski intervali) i postoji grana između dva intervala ako se preklapaju. Nezavisan skup u intervalnim grafovima je samo skup intervala koji se ne preklapaju. Problem pronalaženja maksimum nezavisnog skupa u intervalnim grafovima je proučavan, na primer, u kontekstu rasporeda aktivnosti: dat je skup aktivnosti koje treba da budu izvršene na računaru, pronaći maksimum skup aktivnosti koje mogu da budu izvršene bez preplitanja sa drugim aktivnostima. Ovaj problem može biti rešen u polinomijalnom vremenu koristeći raspoređivanje po vremenu završetka.


Nezavisni skupovi u geomtrijskim ukrštajućim grafovima[уреди | уреди извор]

Geometrijski ukrštajući graf je graf čiji su svi čvorovi geometrijski oblici i postoji grana između dva oblika ako se prepliću. Nezavisan skup u ovim grafovima je samo skup oblika koji se ne prepliću. Problem pronalaženja nezavisnog skupa u ovim grafovima je, na primer, proučavan u kontekstu Automatske zamene oznaka: dat je skup lokacija na mapi, pronaći maksimlan skup razdvojenih pravougaonih oznaka u blizini tih lokacija.

Pronalaženje maksimum nezavisnog skupa u ovim grafovima je NP-kompletan, ali je lakši za aproksimaciju nego problem maksimum nezavisnog skupa. Skorija istraživanja mogu biti pronađena u [12]

Pronalaženje maksimalnog nezavisnog skupa[уреди | уреди извор]

Problem pronalaženja maksimalnog nezavisnog skupa može biti rešen u polinomijlanom vremenu[13] koristeći trivijalan pohlepni algoritam. Svi maksimalni nezavisni skupovi mogu biti pronađeni u vremenu O(3n/3) = O(1.4423n).

Vidi još[уреди | уреди извор]

  • Nezavisan skup grana je skup grana gde nikoje dve grane nemaju zajednički čvor. Obično se naziva uparivanje.
  • Bojenje čvorova je particionisanje skupa čvorova na nezavisne skupove.

Reference[уреди | уреди извор]

  1. ^ Korshunov 1974
  2. ^ Godsil & Royle 2001. стр. 3.
  3. ^ PROOF: A set V of vertices is an independent set IFF every edge in the graph is adjacent to at most one member of V IFF every edge in the graph is adjacent to at least one member not in V IFF the complement of V is a vertex cover.
  4. ^ Moon & Moser 1965
  5. ^ Füredi 1987
  6. ^ Chiba & Nishizeki 1985
  7. ^ Berman & Fujito 1995
  8. ^ Bourgeois et al. 2010
  9. ^ Bazgan, Cristina; Escoffier, Bruno; Paschos, Vangelis Th. (2005). „Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness”. Theoretical Computer Science. 339 (2-3): 272—292. doi:10.1016/j.tcs.2005.03.007. 
  10. ^ а б Baker 1994; Grohe 2003
  11. ^ Chlebík, Miroslav; Chlebíková, Janka (2003). „Approximation Hardness for Small Occurrence Instances of NP-Hard Problems”. Proceedings of the 5th International Conference on Algorithms and Complexity. 
  12. ^ Chan & Har-Peled 2012
  13. ^ Luby 1986

Spoljašnje veze[уреди | уреди извор]

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