Független csúcshalmaz
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 legfeljebb 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.

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

Más gráfparaméterekkel való kapcsolata
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

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, 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. Í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

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
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ó; 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.

Maximális elemszámú független halmazok keresése

Lásd még: klikkprobléma

Pontos algoritmus
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.

 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, ami az egyszerűbb O(1,2209n) algoritmus továbbfejlesztése.

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, a
P5-mentes gráfok
és a perfekt gráfok.
A merevkörű gráfoknál a maximális súlyú független csúcshalmaz lineáris időben megtalálható.

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.

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

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. Az ilyen esetek approximációjának a nehézségére  határozott meg korlátokat. Még a 3-reguláris, 3 színnel színezhető gráfokra is APX-teljes a probléma.

Intervallumgráfok független csúcshalmazai 

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  alkalmazásával.

Mértani metszetgráfok független csúcshalmazai 

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  előszavában.

Maximális független csúcshalmaz megkeresése

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

Kapcsolódó szócikkek 
 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

.
.

.
.
.
.
.
.
.
.
.
 .
.
.
.
.
.
.
.
.
.

.
.
.

Fordítás

További információk 
 
 Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring 
 Independent Set and Vertex Cover, Hanan Ayad.
 Maximum Independent Sets in Graphs – an interactive demo in JavaScript

Jegyzetek

Gráfelmélet
Gráfelméleti objektumok
Számítási problémák a gráfelméletben
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 legfeljebb 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 . 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 ) . 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 Más gráfparaméterekkel való kapcsolata 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 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/3 maximális független halmazt tartalmazhat , 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 . Így tehát mindkét szám a „ plasztikus szám” , azaz324718 hatványaival arányosan növekszik . Független halmazok keresése 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 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 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ó ; 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 . Maximális elemszámú független halmazok keresése Lásd még : klikkprobléma Pontos algoritmus 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. 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 , ami az egyszerűbb O( 1,2209n ) algoritmus továbbfejlesztése . 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 , a P5-mentes gráfok és a perfekt gráfok . A merevkörű gráfoknál a maximális súlyú független csúcshalmaz lineáris időben megtalálható . 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 . 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 Á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 . 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 . 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 . Az ilyen esetek approximációjának a nehézségére határozott meg korlátokat . Még areguláris, színnel színezhető gráfokra is APX-teljes a probléma . Intervallumgráfok független csúcshalmazai Egy intervallumgráf olyan gráf , melynek csúcsaidimenzió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 alkalmazásával . Mértani metszetgráfok független csúcshalmazai 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 előszavában . Maximális független csúcshalmaz megkeresése 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 . 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 Kapcsolódó szócikkek 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 . . . . . . . . . . . \ . . . . . . . . . . . . . Fordítás További információk Challenging Benchmarks for Maximum Clique , Maximum Independent Set , Minimum Vertex Cover and Vertex Coloring Independent Set and Vertex Cover , Hanan Ayad . Maximum Independent Sets in Graphs – an interactive demo in JavaScript Jegyzetek Gráfelmélet Gráfelméleti objektumok Számítási problémák a gráfelméletben