Független csúcshalmaz

A Wikipédiából, a szabad enciklopédiából
(Maximális elemszámú független halmaz szócikkből átirányítva)
Ugrás a navigációhoz Ugrás a kereséshez
A kilenc kék csúcs az általánosított Petersen-gráf GP(12,4) egy maximális független halmazát jelöli.

A matematika, azon belül a gráfelmélet területén egy független csúcshalmaz, független ponthalmaz, független halmaz (independent set) vagy stabil halmaz (stable set) egy gráf olyan csúcsainak halmaza, melyek közül semelyik kettő sem szomszédos egymással. Tehát a csúcsok olyan S halmaza, hogy bármelyik két S-beli csúcsot tekintve állítható, hogy nincs közöttük él. Ezzel ekvivalens állítás, hogy a gráf minden élének pontosan egy végpontja található S-ben. A független halmaz méretén az azt alkotó csúcsok számát értjük. A független halmazokat nevezik belsőleg stabil halmazoknak (internally stable sets) is.[1]

Egy maximális független halmaz (maximal independent set) olyan halmaz, melyhez vagy bármely csúcsot hozzáadva biztosan tartalmazni fog egy élet is, vagy az üres gráf összes csúcsát tartalmazza.

Egy adott G gráfhoz tartozó maximális független halmazok nevükkel ellentétben nagyon különböző méretűek lehetnek. A maximális független halmazok közül a maximális elemszámú független halmaz az adott G gráfhoz tartozó legnagyobb lehetséges méretű halmaz. Ezt a méretet nevezik G függetlenségi számának (independence number), jelölése α(G).[2] Az ilyen halmaz előállításának a problémája, a maximális elemszámú független csúcshalmaz-probléma (maximum independent set problem) NP-nehéz optimalizálási feladat. Így hát valószínűtlen, hogy létezik hatékony algoritmus egy gráf maximális elemszámú független csúcshalmazának meghatározására.

A maximális elemszámú független csúcshalmazok (maximum independent set) minden esetben maximális független csúcshalmazok is (maximal independent set), az állítás megfordítása azonban nem áll fenn.

Tulajdonságai[szerkesztés]

Más gráfparaméterekkel való kapcsolata[szerkesztés]

Egy csúcshalmaz akkor és csak akkor független, ha a gráf komplementerében klikket alkot, tehát a két fogalom egymás komplementerének tekinthető. Valójában azok az elegendően nagy gráfok, melyek nem rendelkeznek nagy klikkekkel, biztosan rendelkeznek nagy független csúcshalmazokkal, ami a Ramsey-elmélet egy fontos témája.

Egy csúcshalmaz akkor és csak akkor független, ha komplementere csúcslefedést alkot. Tehát az α(G) maximális elemszámú független halmaz és a β(G) minimális csúcslefedés összege éppen megegyezik a gráf csúcsainak számával.

Egy G gráf csúcsszínezésén annak csúcsainak független halmazokba való particionálását értjük. Tehát a csúcsszínezéshez minimálisan szükséges színek száma, azaz a χ(G) kromatikus szám nagyobb vagy egyenlő G csúcsai számának és α(G) függetlenségi számának hányadosával.

Egy izolált csúcsokat nem tartalmazó páros gráfban a maximális elemszámú független halmaz elemszáma megegyezik a minimális éllefedés éleinek számával; ez a König-tétellel ekvivalens állítás.

Maximális független halmaz[szerkesztés]

Egy maximális független halmaz olyan független halmaz, ami nem valódi részhalmaza egyetlen független halmaznak sem. Az ilyen halmazok minden esetben domináló halmazok. Egy gráf legfeljebb 3n/3 maximális független halmazt tartalmazhat,[3] de a legtöbb gráfnak ennél jóval kevesebb van. Az n-csúcsú körgráfok maximális független halmazainak számát a Perrin-számok sorozata adja meg, míg az n-csúcsú útgráfokét pedig a Padovan-sorozat.[4] Így tehát mindkét szám a „plasztikus szám”, azaz 1,324718 hatványaival arányosan növekszik.

Független halmazok keresése[szerkesztés]

A számítástudomány számos, a független csúcshalmazokhoz kapcsolódó számítási problémát tart számon.

  • A maximális elemszámú független halmaz-problémában (maximum independent set) a bemenet egy irányítatlan gráf, a kimenet pedig a gráf egy maximális elemszámú független csúcshalmaza. Ha több ilyen is létezik, elegendő egynek szerepelnie a kimenetben. A problémát néha csúcspakolásnak (vertex packing) is nevezik.
  • A maximális súlyú független halmaz-problémában (maximum-weight independent set) a bemenet egy irányítatlan, a csúcsain súlyozott gráf, a kimenet pedig egy maximális súlyú, független csúcshalmaz. Az előző probléma ennek egy speciális esete, ahol minden súly értéke 1.
  • A maximális független csúcshalmaz listázása-problémában (maximal independent set listing) a bemenet egy irányítatlan gráf, a kimenet pedig az összes maximális független csúcshalmazainak listája. A probléma megoldása közben természetes módon előáll a maximális elemszámú független halmaz-probléma megoldása is.
  • A független halmaz eldöntése-problémában (independent set decision) a bemenet egy irányítatlan gráf és egy k szám, a kimenet pedig egy logikai érték: igaz, ha a gráf tartalmaz k méretű független csúcshalmazt, egyébként hamis.

Az első három problémának fontos gyakorlati alkalmazásai vannak; az eldöntési problémának nincsen, de szükséges felvetni annak érdekében, hogy az NP-teljesség elméletét alkalmazni lehessen a független csúcshalmazokat érintő problémákban.

Maximális elemszámú független halmazok és maximális elemszámú klikkek[szerkesztés]

A maximális elemszámú független halmaz-probléma és a maximális elemszámú klikkek problémája egymás komplementerei: G egy klikkje G komplementer gráfjának független csúcshalmaza, és vice versa. Ezért sok számítástudományi eredmény egyformán jól alkalmazható mindkét problémára. Például a klikkproblémára érvényes eredmények az alábbi következményekkel is járnak:

  • A független halmaz eldöntése-probléma NP-teljes, ezért úgy gondoljuk, nem létezik hatékony algoritmus a megoldására.
  • A maximális elemszámú független halmaz-probléma NP-nehéz, ráadásul közelítő megoldást is nehéz találni rá.

Annak ellenére, hogy a maximális elemszámú független halmazok és a maximális elemszámú klikkek problémája általános gráfokban közeli rokonságban állnak, egyes speciális gráfosztályokban a két probléma nagyon különböző lehet. Például ritka gráfokban (ahol az élek száma bármely részgráfban legfeljebb konstansszorosa a csúcsok számának) a maximális elemszámú klikk mérete korlátos és lineáris időben megtalálható;[5] ugyanakkor a ritka gráfok, sőt a még speciálisabb korlátos fokszámú gráfok esetében a maximális elemszámú független halmazok megkeresése MAXSNP-teljes, ami azt jelenti, hogy adott c konstansra (a fokszámtól függően) NP-nehéz olyan közelítő megoldást találni, ami az optimálist c faktorral megközelíti.[6]

Maximális elemszámú független halmazok keresése[szerkesztés]

Lásd még: klikkprobléma

Pontos algoritmus[szerkesztés]

A maximális elemszámú független halmaz megkeresése NP-nehéz probléma. Mindazonáltal a naiv brute-force keresés O(n2 2n) idejénél (ti. ha minden csúcshalmazt egyenként megvizsgálunk, hogy az vajon független csúcshalmaz-e) hatékonyabb algoritmusok is léteznek a feladatra.

(Robson 1986) egy algoritmusa O(1,2108n) időben oldja meg, ha exponenciális tér áll rendelkezésre. Polinomiális térre korlátozva létezik egy O(1,2127n) algoritmus,[7] ami az egyszerűbb O(1,2209n) algoritmus továbbfejlesztése.[8]

Sok gráfosztály esetében a maximális súlyú független csúcshalmaz polinomiális időben megtalálható. Jellemző példák erre a karommentes gráfok,[9] a P5-mentes gráfok[10] és a perfekt gráfok.[11] A merevkörű gráfoknál a maximális súlyú független csúcshalmaz lineáris időben megtalálható.[12]

A moduláris dekompozíció hatékony eszköz a maximális súlyú független csúcshalmaz-probléma megoldására; jó példa erre a kográfokon lineáris idejű algoritmus. Másik fontos eszköz a Tarjan által leírt klikkszeparátor.[13]

Egy páros gráfban a minimális csúcslefedésben nem szereplő csúcsok hozzátehetők a maximális elemszámú független csúcshalmazhoz; lásd a König-tételt. Ezért a minimális csúcslefedés megtalálható a páros gráf párosítási algoritmusával.

Közelítő algoritmusok[szerkesztés]

Általában a maximális elemszámú független halmaz problémája nem approximálható konstans faktor erejéig sem polinomiális időben (kivéve, ha P = NP). Sőt, általánosságban Poly-APX-teljes, tehát olyan nehéz, mint bármely polinomiális faktorral approximálható probléma.[14] Egyes speciális gráfosztályokra azonban léteznek hatékony közelítési algoritmusok.

Síkgráfok maximális elemszámú független halmazai c < 1 approximációs faktorral polinomiális időben számíthatók; hasonló polinomiális approximációs sémák léteznek bármely gráfminorképzésre zárt gráfcsalád esetében.[15]

Korlátos fokszámú gráfokban léteznek hatékony approximációs algoritmusok, melyek a maximális fokszámtól függő konstans approximációs rátával rendelkeznek; például egy mohó algoritmus, ami úgy találja meg a maximális elemszámú független halmazt, hogy minden lépésben kiválaszt egy minimális fokszámú csúcsot a gráfban és eltávolítja a szomszédait, Δ maximális fokszámú gráfban (Δ+2)/3 approximációs rátát ér el.[16] Az ilyen esetek approximációjának a nehézségére (Berman & Karpinski 1999) határozott meg korlátokat. Még a 3-reguláris, 3 színnel színezhető gráfokra is APX-teljes a probléma.[17]

Intervallumgráfok független csúcshalmazai[szerkesztés]

Egy intervallumgráf olyan gráf, melynek csúcsai 1 dimenziós intervallumok (pl. időintervallumok), melyek között akkor van él, ha a két intervallum metszi egymást. Egy intervallumgráf független csúcshalmaza egyszerűen egymást nem átfedő intervallumokból áll. Az intervallumgráfok független csúcshalmazai keresésének problémáját például a feladatütemezés kontextusában vizsgálták: ha adott futtatandó feladatok egy halmaza, keressük meg azt a maximális halmazt ezek közül, melyek az egymással való interferálás veszélye nélkül lefuttathatók. Ez a probléma pontosan polinomiális időben megoldható a legkorábbi határidő szerinti ütemezés (wd) alkalmazásával.

Mértani metszetgráfok független csúcshalmazai[szerkesztés]

Egy mértani metszetgráf esetében a csúcsok mértani alakzatok, és két mértani alakzatot reprezentáló csúcs között pontosan akkor van él, ha az alakzatoknak van közös pontjuk. Egy mértani metszetgráf esetén tehát a független csúcshalmaz át nem fedő mértani alakzatok összessége. Ezek keresését tanulmányozták többek közt a térképek automatikus címkézésének kontextusában: ha adott a térképen helyek egy halmaza, keressük a környezetükben egymást át nem fedő téglalap alakú címkék elhelyezésének maximális lehetőségét.

A metszetgráfok maximális elemszámú független csúcshalmazának megtalálása NP-teljes, de még mindig könnyebb probléma, mint az általános gráfok esetében. A témát körüljárják a (Chan & Har-Peled 2012) előszavában.

Maximális független csúcshalmaz megkeresése[szerkesztés]

A maximális (nem maximális elemszámú!) független csúcshalmaz megkeresése polinomiális időben végrehajtható egy triviális mohó algoritmussal.[18] Az összes maximális független csúcshalmaz O(3n/3) = O(1,4423n) időben megkereshető.

Maximális elemszámú független csúcshalmazokat kereső programok[szerkesztés]

Név Licenc API nyelve Rövid leírás
igraph GPL C, Python, R, Ruby Pontos megoldás. "The current implementation was ported to igraph from the Very Nauty Graph Library by Keith Briggs and uses the algorithm from the paper S. Tsukiyama, M. Ide, H. Ariyoshi and I. Shirawaka. A new algorithm for generating all the maximal independent sets. SIAM J Computing, 6:505–517, 1977".
NetworkX BSD Python Közelítő megoldás a következő rutinnal: maximum_independent_set
OpenOpt BSD Python Pontos és közelítő megoldások, megadhatók a csomópontok, amiket feltétlenül
tartalmaznia / kihagyni kell; lásd STAB további példákért és részletekért

Kapcsolódó szócikkek[szerkesztés]

  • A független élhalmaz élek olyan halmaza a gráfban, melyek nem rendelkeznek közös csúccsal. Általában párosításnak nevezik.
  • Egy csúcsszínezés a gráf csúcsainak független halmazokba való particionálása.

Jegyzetek[szerkesztés]

  1. (Korshunov 1974)
  2. (Godsil & Royle 2001), p. 3.
  3. (Moon & Moser 1965).
  4. (Füredi 1987).
  5. (Chiba & Nishizeki 1985).
  6. (Berman & Fujito 1995).
  7. (Bourgeois et al. 2010)
  8. (Fomin, Grandoni & Kratsch 2009)
  9. (Minty 1980),(Sbihi 1980),(Nakamura & Tamura 2001),(Faenza, Oriolo & Stauffer 2014),(Nobili & Sassano 2015)
  10. (Lokshtanov, Vatshelle & Villanger 2014)
  11. (Grötschel, Lovász & Schrijver 1988)
  12. (Frank 1976)
  13. (Tarjan 1985)
  14. (2005. november 17.) „Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness”. Theoretical Computer Science 339 (2–3), 272–292. o. DOI:10.1016/j.tcs.2005.03.007.  
  15. (Baker 1994); (Grohe 2003).
  16. (Halldórsson & Radhakrishnan 1997).
  17. (2003. november 17.) „Approximation Hardness for Small Occurrence Instances of NP-Hard Problems”. Proceedings of the 5th International Conference on Algorithms and Complexity.  
  18. (Luby 1986).

Fordítás[szerkesztés]

További információk[szerkesztés]

Jegyzetek[szerkesztés]