A matematika, azon belül a gráfelmélet területén egy maximális független csúcshalmaz, maximális független ponthalmaz, maximális független halmaz (MFH) vagy maximális stabil halmaz (angol nyelvterületen: maximal independent set = MIS vagy maximal stable set) olyan független csúcshalmaz, ami nem valódi részhalmaza egyetlen független csúcshalmaznak sem. Más szavakkal, nincs olyan rajta kívül eső csúcs, amit a halmazhoz hozzá lehetne venni anélkül, hogy megszűnne független csúcshalmaznak lenni.
Például a három csúcsú útgráf esetén, melyet az , és csúcsok, valamint az és élek alkotnak, mind a , mind az maximális független csúcshalmaz. Az halmaz független, de nem maximális, mivel valódi részhalmaza a nagyobb független csúcshalmaznak. Ugyanennek a gráfnak a maximális klikkjei az és halmazok.
Egy MFH egyben a gráf domináló halmaza is, és minden domináló halmaz, ami független, egyben maximális független is, ezért a maximális független halmazokat gyakran független domináló halmazoknak (independent dominating sets) is nevezik.
Egy gráf nagyon különböző méretű MFH-kkal rendelkezhet; megmutatja, hogy egy n-csúcsú gráf különböző méretű MFH-inak száma akár n − log n − O(log log n) is lehet, de sohasem nagyobb n − log n-nél. közülük a legnagyobb MFH-t vagy MFH-kat maximális elemszámú független csúcshalmaznak (maximum independent set) nevezzük. Az olyan gráfok, melyekben a maximális független csúcshalmazok mind azonos méretűek, a jól fedett gráfok (well-covered graph).
Két algoritmikus probléma köthető az MFH-khoz: megtalálni adott gráf egyetlen, illetve az összes MFH-ját.
Definíció Egy gráf független csúcshalmaza akkor maximális független csúcshalmaz, ha bármely csúcsra a következők egyike igaz:
, ahol szomszédait jelöli. A fenti definíció úgy is megfogalmazható, hogy egy csúcs vagy a független csúcshalmazba tartozik, vagy legalább egy csúcs-szomszédja a független csúcshalmazba tartozik. Végeredményképpen a gráf minden élének legalább egy végpontja -en kívül esik. Ugyanakkor nem igaz, hogy a gráf bármely élének legalább egy végpontja -ben lenne.
Vegyük észre, hogy az független csúcshalmaz közvetlen szomszédságában lévő csúcs a független halmaz definíciója szerint nem lehet -ben.
Vonatkozó csúcshalmazok Ha S egy gráf maximális független csúcshalmaza, egyben a gráf komplementerének maximális klikkje vagy maximális teljes részgráfja. Egy maximális klikk olyan csúcshalmazt jelent, melyek feszített részgráfjai teljes gráfok, de maga nem valódi részhalmaza egyetlen teljes részgráfnak sem. Tehát egy olyan S csúcshalmaz, amiben minden S-beli csúcspárat él köt össze, és minden S-en kívüli csúcsra igaz, hogy legalább egy S-beli csúccsal nem köti össze él. Egy gráfnak több maximális klikkje is lehet, ezek közül a legnagyobb megkeresése a klikkprobléma.
Egyes szerzők a maximális jelleget a klikk alaptulajdonságának tekintik, és a maximális klikkekre egyszerűen klikkekként hivatkoznak.
Egy maximális független csúcshalmaz komplementere, tehát az MFH-ba nem tartozó csúcsok halmaza minimális csúcslefedést (minimal vertex cover) alkot. Tehát a komplementer halmaz egy csúcslefedés, azaz olyan csúcsok halmaza, melyek minden él legalább egy végpontját tartalmazzák, és olyan értelemben minimális, hogy egy csúcsot sem lehet belőle eltávolítani anélkül, hogy ne veszítse el csúcslefedés mivoltát. A minimális csúcslefedéseket a statisztikus mechanika területén a folyékony-szilárd halmazállapot-átmenetek egy matematikai absztrakciójával, a merev gömbök modelljével kapcsolatban tanulmányozzák..
Minden maximális csúcshalmaz egyben domináló halmaz, a gráf csúcsainak olyan halmaza, melyre igaz, hogy a gráf csúcsai vagy beletartoznak a halmazba vagy szomszédosak vele. Csúcsok egy halmaza pontosan akkor maximális független, ha független domináló.
Gráfcsalád-jellemzések Egyes gráfcsaládokat a maximális klikkszámuk vagy maximális független halmazuk kapcsán határoznak meg. Ilyenek például a maximal-clique irreducible és hereditary maximal-clique irreducible gráfok. Egy gráf akkor maximal-clique irreducible, ha minden maximális klikkjének van olyan éle, ami nem tartozik másik maximális klikkhez, míg a hereditary maximal-clique irreducible gráfoknak ez a tulajdonság minden feszített részgráfjára is igaz.Information System on Graph Class Inclusions: maximal clique irreducible graphs and hereditary maximal clique irreducible graphs . A Hereditary maximal-clique irreducible gráfok közé tartoznak a háromszögmentes gráfok, a páros gráfok és az intervallumgráfok is.
A kográfok egyik jellemzésük szerint olyan gráfok, melyekben minden maximális klikk metsz minden maximális független csúcshalmazt, és ez a tulajdonság minden feszített részgráfra is teljesül.
A csúcshalmazok számára vonatkozó korlátok megmutatták, hogy egy n csúcsú gráf legfeljebb 3n/3 maximális klikket tartalmaz. A komplementer esetben hasonló a helyzet, egy n csúcsú gráf legfeljebb 3n/3 maximális független csúcshalmazzal bír. Könnyű konstruálni olyan gráfot, aminek pontosan 3n/3 MFH-ja van: venni kell n/3 db háromszöggráf össze nem kötött unióját. Ebben a gráfban az MFH-kat úgy kaphatjuk meg, hogy minden háromszögből pontosan egy csúcsot választunk. A komplementer gráf, amiben pontosan 3n/3 maximális klikk van, a Turán-gráfok egy specifikus fajtája; a Moon and Moser-féle korláttal való kapcsolatuk miatt néha Moon–Moser-gráfoknak is nevezik őket. Az MFH-k méretét korlátozva szorosabb korlátok is elérhetők: egy n-csúcsú gráfban a k nagyságú MFH-k maximális száma
A korlátot beállító gráfok itt is Turán-gráfok.. Korábbi eredmények ezen a téren itt: és .
Egyes gráfcsaládok még erősebb korlátokkal bírnak az MFH-k számára, illetve a maximális klikkekre nézve. Ha egy család minden n-csúcsú gráfjának O(n) éle van, és a gráfcsalád minden gráfjának minden részgráfja is a családba tartozik, akkor a család minden gráfjának legfeljebb O(n) maximális klikkje lehet, melyek mérete O(1).. Chiba and Nishizeki az O(n) élek feltételét ezzel ekvivalens módon, a gráf arboricitásának konstansságával mondják ki. Ezek a feltételek igazak például a síkgráfokra: minden n-csúcsú síkgráfnak legfeljebb 3n − 6 éle van, és egy síkgráf részgráfja is mindig síkgráf, amiből az következik, hogy egy síkgráfnak legfeljebb O(n) maximális klikkje lehet (melyek mérete legfeljebb négy). A intervallumgráfok és húrgráfok szintén legfeljebb n maximális klikkel rendelkeznek, bár ezek nem mindig ritka gráfok.
Az n-csúcsú körgráfok MFH-inak számát a Perrin-számok adják meg, míg az n-csúcsú útgráfokét a Padovan-sorozat.; ; . Így tehát mindkét szám a plasztikszám, ~1,324718 hatványaival arányos.
Egyetlen maximális független csúcshalmaz megkeresése
Szekvenciális algoritmus Adott G(V,E) gráf egy MFH-ja könnyen megkereshető a következő algoritmussal:
Inicializáljuk I-t üres halmazként. Amíg V üres nem lesz: Válasszunk egy v∈V csúcsot; Adjuk v-t az I halmazhoz; Vegyük ki v-t és összes szomszédját V-ből. Visszatérési érték: I.
A futási idő O(n), mivel legrosszabb esetben minden csúcsot vizsgálni kell.
Az O(n) nyilvánvalóan az elérhető legjobb futási idő egy soros algoritmus számára. Egy párhuzamos algoritmussal azonban jóval gyorsabban megoldható a probléma.
Véletlen kiválasztásos párhuzamos algoritmus A következő algoritmus O(log n) időben talál egy MFH-t.Luby’s Algorithm, in: Lecture Notes for Randomized Algorithms, Last Updated by Eric Vigoda on February 2, 2006
Inicializáljuk I-t üres halmazként. Amíg V üres nem lesz: Válasszunk ki véletlenszerűen egy S ⊆ V csúcshalmazt úgy, hogy minden egyes v csúcsot egymástól függetlenül, 1/(2d(v)) valószínűséggel választunk ki, ahol d a v csúcs fokát (szomszédainak számát) jelöli. Minden E-beli élre, ha mindkét végpontja a véletlen S halmazban található, akkor a két végpont közül az alacsonyabb fokszámút távolítsuk el S-ből. Döntetlen esetekben tetszés szerint lehet választani, például a csúcsok neveinek lexikografikus sorrendjét figyelembe véve. Adjuk az S halmaz elemeit I-hez. Vegyük ki V halmaz elemeit és az összes velük szomszédos elemet az S halmazból. Visszatérési érték: I.
Analízis: Minden v csúcs esetében felosztjuk a szomszédokat „alacsonyakra” (melyek fokszáma kisebb v fokszámánál) és „magasakra” (melyek fokszáma magasabb v fokszámánál), a döntetlen eseteket valamilyen módon eldöntve.
Tekintsünk egy csúcsot „rossznak”, ha szomszédainak több mint ⅔-ad része a magasak közé tartozik. Tekintsünk egy élet „rossznak”, ha mindkét csúcsa rossz, egyébként az él legyen „jó”. Legalább az élek ½-e minden esetben jó. Bizonyítás: Alakítsunk ki irányított gráfot G-ből oly módon, hogy minden él a magasabb fokszámú csúcs felé mutasson (a döntetlen eseteket tetszőleges módon eldöntve). Így minden rossz csúcsnál a kimenő élek száma több mint kétszerese a bejövő élekének. Tehát minden v-be menő rossz élhez párosítható két másik él, ami v-ből kifelé irányul. Összegezve, az összes él száma legalább kétszerese a rossz élek számának. Minden jó u csúcs esetében annak valószínűsége, hogy egy szomszédot S tagjává választunk nagyobb egyenlő egy pozitív konstanssal. Bizonyítás: annak valószínűsége, hogy u egyetlen szomszédját sem választjuk S-be legfeljebb annak a valószínűségével egyezik meg, hogy u egyetlen „alacsony” szomszédját sem választjuk ki. Minden egyes alacsony szomszéd v csúcs esetében a nem kiválasztás valószínűsége (1-1/2d(v)), ami legfeljebb (1-1/2d(u)) lehet, mivel d(u)≤d(v). Az ilyen szomszédok száma legalább d(u)/3, mivel u jó csúcs. Ezért annak a valószínűsége, hogy egyetlen alacsony szomszéd sem lesz kiválasztva, legfeljebb 1-exp(-1/6). Bármely S-be választott u csúcs esetében annak valószínűsége, hogy u el lesz távolítva S-ből legfeljebb ½. Bizonyítás: ez a valószínűség legfeljebb annak a valószínűségét éri el, hogy u-nak egy magas szomszédját választjuk S-be. Minden egyes magas v szomszéd esetében a kiválasztás valószínűsége legfeljebb 1/2d(v), ami legfeljebb 1/2d(u), mivel d(v)≤d(u). A korlátok egyesítésével megkapjuk, hogy annak valószínűsége, hogy egyetlen magas szomszéd sem lesz kiválasztva, legfeljebb d(u)/2d(u) = 1/2. Így tehát, minden jó u csúcs esetén annak valószínűsége, hogy egy szomszédját S-be választják és benne is marad, egy bizonyos pozitív konstansnak felel meg. Ebből következik, hogy annak a valószínűsége, hogy u eltávolításra kerül, bármely lépésben, szintén nagyobb egyenlő egy pozitív konstansnál. Továbbá, minden jó e él esetében az e eltávolításának valószínűsége minden lépésben nagyobb egyenlő egy pozitív konstansnál. Tehát a jó élek száma minden lépésben legalább egy konstans faktorral csökken. Mivel legalább az élek fele jó, az össz-élszám is minden lépésben legalább egy konstans faktorral csökken. Így tehát, a szükséges lépések száma O(log m), ahol m az élek száma. Ennek korláta .
Az algoritmus számára a legrosszabb eset, ahol lépésre van szükség, egy n/2 összefüggő komponensből álló gráf, melynek minden komponensét két csúcs alkotja. A csúcsok fokszáma 1, tehát minden csúcs ½ valószínűséggel lesz kiválasztva, és ¼ valószínűséggel nem választjuk ki egy komponens mindkét csúcsát. Tehát a csúcsok száma minden lépésben 4-edére csökken, a várható lépésszám tehát .
Véletlen prioritásos párhuzamos algoritmus
A következő algoritmus annyival jobb az előzőleg leírtnál, hogy minden lépésben legalább egy új csúcsot hozzáadunk minden összefüggő komponenshez:
Inicializáljuk I-t üres halmazként. Amíg V üres nem lesz, minden v csúcs a következőket végezze el: Válasszon egy r(v) véletlen számot a [0,1] intervallumban és küldje el az összes szomszédjának; Ha r(v) kisebb mint bármely szám, amit a szomszédaitól kapott, akkor v behelyezi magát I-be, eltávolítja magát V-ből és erről értesíti szomszédait; Ha v megtudja, hogy valamely szomszédja I-be jutott, akkor v eltávolítja magát V-ből. Visszatérési érték: I.