Maximális független csúcshalmaz
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; 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. 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.

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

 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.

Vegyük észre, hogy minden összefüggő komponensben legalább egy, a legkisebb számot választó csúcs bekerül I-be, tehát mindig történik előrelépés. Az előző algoritmus legrosszabb esetének számító n/2 összefüggő komponens, mindegyikben pontosan 2 csúcs esetben az MFH-t egyetlen lépésben előállítjuk.

Analízis: 
 Egy  csúcs eltávolításának valószínűsége legalább . Bizonyítás: Cseréljünk le minden  csúcspárt összekötő élet két irányított éllel, az egyik legyen , a másik  irányú. Vegyük észre, hogy az  most éppen dupla méretű lett. Minden  irányított élpárhoz definiáljunk két eseményt: -t és -t, ahol  preemptíven eltávolítja -t és  preemptíven eltávolítja -t. A  esemény akkor következik be, ha  és , ahol  szomszédja -nek és  szomszédja -nek. Tudjuk, hogy minden csúcshoz tartozik egy [0, 1] intervallumbeli véletlenszám. Tekintsünk egy egyszerű, két különálló csúcsból álló példát, ekkor mindkettő  valószínűséggel lesz a legkisebb; három különálló csúcsnál mindhárom esetében ez a valószínűség . Ha  csúcsot vizsgálunk, a legkisebbnek levés valószínűsége legalább , hiszen elképzelhető, hogy  szomszédja egyben  szomszédja is, így pedig egy csúcsot kétszer számolnánk. Ugyanezen logika alapján a  esemény eltávolításának valószínűsége is legalább .
 Amikor a  és a  események történnek, , illetve  irányított kimenő éleket távolítják el. Bizonyítás: A  esemény bekövetkeztekor, amikor  eltávolításra kerül, valamennyi szomszédos  csúcsot is eltávolítjuk. A -ből kimenő, eltávolított élek száma . Hasonló logikát alkalmazva,  éppen  irányított kimenő élet távolít el.
 A második lépés minden iterációja során várható, hogy az élek fele eltávolításra kerül. Bizonyítás: Ha a  esemény következik be, akkor  minden szomszédját eltávolítjuk, ezért az eltávolított élek száma legalább . Ugyanez igaz a fordított,  eseményre is, tehát az eltávolított élek száma legalább . Így tehát, minden irányítatlan  él esetében a legkisebb értékű csúcs miatt eltávolított élek számának várható értéke . Ezt összegezve az éleken, , ami az egyes lépésben eltávolított élekre -t adna, de minden élet kétszer számoltunk (irányonként egyszer), ami az egy lépésben eltávolított élek várható értékére -t ad.
 Ebből következően, az algoritmus várható futási ideje , ami .

Véletlen permutáló párhuzamos algoritmus 

Ahelyett, hogy minden lépésben véletlenül választanánk, elegendő egyszer, az algoritmus kezdetén véletlenszerűen választani, megadva a csúcsok egy véletlenszerű rendezését. Ezt a véletlenszerű rendezést tekintve a következő párhuzamos algoritmus ugyanahhoz az MFH-hoz jut, mint a #Szekvenciális algoritmus (tehát az eredmény determinisztikus):

 Inicializáljuk I-t üres halmazként.
 Amíg V üres nem lesz:
 Legyen W azoknak a V-beli csúcsoknak a halmaza, amiknek nincsen korábbi szomszédjuk (a fix rendezést tekintve);
 Adjuk W-t I-hez;
 Vegyük ki V-ből a W-ben lévő csúcsokat és az összes szomszédjukat.
 Visszatérési érték: I.

A teljesen szekvenciális és a teljesen párhuzamosított algoritmus szélső esetei között elképzelhető egy kontinuum, amit részben szekvenciális, részben párhuzamos algoritmusok alkotnak. Ha veszünk egy fix rendezést a csúcsokon, és egy δ∈(0,1] faktort, a következő algoritmus ugyanazt az MFH-t adja vissza:

 Inicializáljuk I-t üres halmazként.
 Amíg V üres nem lesz:
 Válasszunk egy δ∈(0,1] faktort.
 Legyen P a rendezésben elöl álló, δn csúcs halmaza.
 Legyen W a P-n futtatott teljesen párhuzamos algoritmus által visszaadott MFH.
 Adjuk W-t I-hez;
 Vegyük ki V-ből a P-ben lévő csúcsokat és a W halmaz szomszédait.
 Visszatérési érték: I.

A δ=1/n a teljesen szekvenciális algoritmust adja, a δ=1 pedig a teljesen párhuzamos algoritmust.

Analízis: A részlegesen párhuzamos algoritmus esetében a δ paraméter értékének megfelelő megválasztásával garantálható, hogy a teljesen párhuzamos algoritmus legfeljebb log(n) meghívásával befejeződik, és minden hívás legfeljebb log(n) lépésben véget ér. Így a részlegesen párhuzamos algoritmus teljes futási ideje . Továbbá, a teljesen párhuzamos algoritmus futásideje szintén legfeljebb . A bizonyítás főbb lépései:
 Ha az i. lépésben -t választunk, ahol D a gráf maximális fokszáma, akkor nagy valószínűséggel minden i lépés után megmaradó csúcs fokszáma legfeljebb . Tehát log(D) lépés után minden megmaradó csúcs foka 0 (hiszen D<n) és egyetlen lépésben eltávolítható.
 Ha bármely lépésben minden csúcs fokszáma legfeljebb d, és -t választunk (bármely C konstansra), akkor nagy valószínűséggel az irányított gráfban a fix rendezés által meghatározott leghosszabb út hossza . Így a teljesen párhuzamos algoritmusnak legfeljebb  lépésre van szüksége (hiszen a leghosszabb út az algoritmus lépésszáma szempontjából a legrosszabb eset).
 Ezt a két tényt kombinálva, ha -t választjuk, akkor nagy valószínűséggel a részlegesen párhuzamos algoritmus futásideje .

Az összes maximális független csúcshalmaz listázása 

Lásd még: Klikkprobléma#Az összes maximális klikk listázása

Egy olyan algoritmust, ami megkeresi egy gráf összes MFH-ját vagy maximális klikkjét fel lehet használni számos NP-teljes gráfprobléma megoldásának szubrutinjaként. A legnyilvánvalóbb esetekben, tehát a maximális elemszámú független halmaz, a maximális elemszámú klikk, illetve a minimális független domináló halmaz keresése esetében a keresett halmaznak mindig MFH-nak vagy maximális klikknek kell lennie, tehát a keresés végrehajtható úgy is, hogy egy algoritmus listázza az összes maximális független halmazt vagy maximális klikket, és megtartja a legnagyobb vagy legkisebb méretűt. Hasonlóan, a minimális csúcslefedés is megkereshető, mint valamely MFH komplementere.  megfigyelése szerint az MFH-k listázása a gráfok 3-színezésének megtalálására is használható: egy gráf pontosan akkor színezhető 3 színnel, ha valamely MFH-jának komplementer gráfja páros. Ezt a megközelítést Lawler nem csak a 3-színezéshez használta fel, hanem egy általánosabb gráfszínező algoritmus részeként. Más szerzők azóta hasonló, egyre kifinomultabb gráfszínezési megközelítéseket dolgoztak ki. Más, komplex problémák szintén modellezhetők valamely specifikus típusú klikk vagy független halmaz kereséseként. Ezek motiválják annak az összes maximális független csúcshalmaz (vagy maximális klikk) listázásának algoritmikus problémájának hatékonyabb megoldását.

Elég egyszerűen átültethető Moon and Moser az MFH-k számára vonatkozó 3n/3-as korlátja egy olyan algoritmusba, ami az összes MFH-t O(3n/3) idő alatt listázza. Ez az algoritmus a kimeneti halmazonként konstans időben lefut a lehető legnagyobb számú MFH-val rendelkező gráfokra. Sajnos azonban egy ilyen időkorláttal rendelkező algoritmus nagyon hatékonytalan tud lenni a kevesebb MFH-val rendelkező gráfokon. Így aztán számos kutató tanulmányozta a kimenetenként polinomális időben lefutó algoritmusokat. Az MFH-nként szükséges idő arányos a sűrű gráfok mátrixszorzásának idejével, illetve ritka gráfok egyes osztályainál ennél  gyorsabb is lehet.

A maximális elemszámú független halmazok keresésének párhuzamosítása

Története 
Eredetileg úgy gondolták, hogy az MFH-keresés problémáját nem triviális párhuzamosítani, hiszen a lexikografikus MFH-keresés P-teljesnek bizonyult; megmutatták azonban, hogy megadható egy determinisztikus párhuzamos megoldás akár a maximális halmazpakolás vagy a maximális párosítás problémájának -redukciójával, akár a 2-SAT kielégíthetőségi probléma -redukciójával. Jellemzően az algoritmus szerkezete hasonlít a többi párhuzamos gráfalgoritmuséhoz: felosztják a gráfot kisebb lokális problémákra, melyek aztán ugyanazt az algoritmust párhuzamos módon sok helyen futtatva megoldhatók.

Az MFH-probléma kezdeti kutatását a PRAM-modell szerint végezték, majd kiterjesztették a számítógépfürtökön futó elosztott algoritmusokra is. Az elosztott párhuzamos algoritmusok számos tervezési problémája az MFH-probléma esetében is előjön; különös tekintettel arra, hogy az algoritmus futásidő és adatkommunikáció szempontjából is hatékony legyen, miközben a gráfot felosztja és a független halmazba elemeket helyez.

Bonyolultságosztály 
1984-ben Karp és tsai megmutatták, hogy az MFH-probléma PRAM-on történő megoldása az NC bonyolultsági osztályon belül -be tartozik. Ez azt jelenti, hogy az algoritmusuknak egy MFH megkereséséhez  időre és  helyre van szüksége, ahol  a csúcshalmaz mérete. Ugyanebben a tanulmányukban egy randomizált párhuzamosított megoldást is leírtak, ami  idő alatt futott le  processzoron. Nem sokkal ezután Luby, Alon és tsai. Karpék eredményétől függetlenül javítottak ezen az eredményen, elérve az -t,  futási idővel  processzoron, ahol  a gráf éleinek számát jelöli. Az algoritmus  voltának igazolására először bemutattak egy randomizált algoritmust, aminek  processzorra van szükség, de a véletlenszerűség megszüntethető  processzor hozzáadásával. Jelenleg is nyitott kérdés, hogy az MFH-probléma vajon az  osztályban található-e..

Kommunikáció, adatcsere 
Az elosztott MFH-algoritmusok létrehozását jelentősen befolyásolták a korábban a PRAM-modellre készített algoritmusok. A Luby, Alon és tsai. által végzett kezdeti kutatások számos elosztott algoritmushoz vezettek. Bitek átvitele szempontjából ezek az algoritmusok körönként legalább  bitet igényelnek és a gráf egyéb karakterisztikájára is szükség van a működésükhöz. Például ismerni kell a gráf méretét vagy a szomszédos csúcsok maximális fokszámát le kell tudni kérdezni a működéshez. 2010-ben Métivier és tsai. sikeresen lecsökkentették a körönkénti üzenetek méretét az optimális  értékre, és megszabadították az algoritmust a gráf egyéb tulajdonságai ismeretének igényétől.

Jegyzetek 

.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.

.
.
.
.

Gráfelmélet
Gráfelméleti objektumok
Számítási problémák a gráfelméletben

de:Glossar Graphentheorie#Stabile Menge
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 ; 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 . 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/3 maximális klikket tartalmaz . A komplementer esetben hasonló a helyzet , egy n csúcsú gráf legfeljebb/3 maximális független csúcshalmazzal bír . Könnyű konstruálni olyan gráfot , aminek pontosan/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/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 . 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) . Ezek a feltételek igazak például a síkgráfokra : minden n-csúcsú síkgráfnak legfeljebb − 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,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 . 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,( 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ége2d ( v ) ) , ami legfeljebb2d ( 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 , legfeljebbexp( -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 legfeljebb2d ( v ) , ami legfeljebb2d ( 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 ) =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 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ésbenedé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. Vegyük észre , hogy minden összefüggő komponensben legalább egy , a legkisebb számot választó csúcs bekerül I-be , tehát mindig történik előrelépés . Az előző algoritmus legrosszabb esetének számító n/2 összefüggő komponens , mindegyikben pontosancsúcs esetben az MFH-t egyetlen lépésben előállítjuk . Analízis : Egy csúcs eltávolításának valószínűsége legalább\ . Bizonyítás : Cseréljünk le minden csúcspárt összekötő élet két irányított éllel , az egyik legyen , a másik irányú . Vegyük észre , hogy az most éppen dupla méretű lett . Minden irányított élpárhoz definiáljunk két eseményt : -t és -t , ahol preemptíven eltávolítja -t és preemptíven eltávolítja -t . A esemény akkor következik be , ha és , ahol szomszédja -nek és szomszédja -nek . Tudjuk , hogy minden csúcshoz tartozik egy [ 0 , intervallumbeli véletlenszám . Tekintsünk egy egyszerű , két különálló csúcsból álló példát , ekkor mindkettő valószínűséggel lesz a legkisebb ; három különálló csúcsnál mindhárom esetében ez a valószínűség \ . Ha csúcsot vizsgálunk , a legkisebbnek levés valószínűsége legalább , hiszen elképzelhető , hogy szomszédja egyben szomszédja is , így pedig egy csúcsot kétszer számolnánk . Ugyanezen logika alapján a esemény eltávolításának valószínűsége is legalább \ . Amikor a és a események történnek , , illetve irányított kimenő éleket távolítják el . Bizonyítás : A esemény bekövetkeztekor , amikor eltávolításra kerül , valamennyi szomszédos csúcsot is eltávolítjuk . A -ből kimenő , eltávolított élek száma \ . Hasonló logikát alkalmazva , éppen irányított kimenő élet távolít el . A második lépés minden iterációja során várható , hogy az élek fele eltávolításra kerül . Bizonyítás : Ha a esemény következik be , akkor minden szomszédját eltávolítjuk , ezért az eltávolított élek száma legalább \ . Ugyanez igaz a fordított , eseményre is , tehát az eltávolított élek száma legalább \ . Így tehát , minden irányítatlan él esetében a legkisebb értékű csúcs miatt eltávolított élek számának várható értéke \ . Ezt összegezve az éleken , , ami az egyes lépésben eltávolított élekre -t adna , de minden élet kétszer számoltunk ( irányonként egyszer ) , ami az egy lépésben eltávolított élek várható értékére -t ad . Ebből következően , az algoritmus várható futási ideje , ami \ . Véletlen permutáló párhuzamos algoritmus Ahelyett , hogy minden lépésben véletlenül választanánk , elegendő egyszer , az algoritmus kezdetén véletlenszerűen választani , megadva a csúcsok egy véletlenszerű rendezését . Ezt a véletlenszerű rendezést tekintve a következő párhuzamos algoritmus ugyanahhoz az MFH-hoz jut , mint a # Szekvenciális algoritmus ( tehát az eredmény determinisztikus ) : Inicializáljuk I-t üres halmazként . Amíg V üres nem lesz : Legyen W azoknak a V-beli csúcsoknak a halmaza , amiknek nincsen korábbi szomszédjuk ( a fix rendezést tekintve ) ; Adjuk W-t I-hez ; Vegyük ki V-ből a W-ben lévő csúcsokat és az összes szomszédjukat . Visszatérési érték : I. A teljesen szekvenciális és a teljesen párhuzamosított algoritmus szélső esetei között elképzelhető egy kontinuum , amit részben szekvenciális , részben párhuzamos algoritmusok alkotnak . Ha veszünk egy fix rendezést a csúcsokon , és egy δ∈( 0,1 ] faktort , a következő algoritmus ugyanazt az MFH-t adja vissza : Inicializáljuk I-t üres halmazként . Amíg V üres nem lesz : Válasszunk egy δ∈( 0,1 ] faktort . Legyen P a rendezésben elöl álló , δn csúcs halmaza . Legyen W a P-n futtatott teljesen párhuzamos algoritmus által visszaadott MFH. Adjuk W-t I-hez ; Vegyük ki V-ből a P-ben lévő csúcsokat és a W halmaz szomszédait . Visszatérési érték : I. A δ=1/n a teljesen szekvenciális algoritmust adja , a δ=1 pedig a teljesen párhuzamos algoritmust . Analízis : A részlegesen párhuzamos algoritmus esetében a δ paraméter értékének megfelelő megválasztásával garantálható , hogy a teljesen párhuzamos algoritmus legfeljebb log ( n ) meghívásával befejeződik , és minden hívás legfeljebb log ( n ) lépésben véget ér . Így a részlegesen párhuzamos algoritmus teljes futási ideje \ . Továbbá , a teljesen párhuzamos algoritmus futásideje szintén legfeljebb \ . A bizonyítás főbb lépései : Ha az i. lépésben -t választunk , ahol D a gráf maximális fokszáma , akkor nagy valószínűséggel minden i lépés után megmaradó csúcs fokszáma legfeljebb \ . Tehát log ( D ) lépés után minden megmaradó csúcs foka( hiszen D<n ) és egyetlen lépésben eltávolítható . Ha bármely lépésben minden csúcs fokszáma legfeljebb d , és -t választunk ( bármely C konstansra ) , akkor nagy valószínűséggel az irányított gráfban a fix rendezés által meghatározott leghosszabb út hossza \ . Így a teljesen párhuzamos algoritmusnak legfeljebb lépésre van szüksége ( hiszen a leghosszabb út az algoritmus lépésszáma szempontjából a legrosszabb eset ) . Ezt a két tényt kombinálva , ha -t választjuk , akkor nagy valószínűséggel a részlegesen párhuzamos algoritmus futásideje \ . Az összes maximális független csúcshalmaz listázása Lásd még : Klikkprobléma#Az összes maximális klikk listázása Egy olyan algoritmust , ami megkeresi egy gráf összes MFH-ját vagy maximális klikkjét fel lehet használni számos NP-teljes gráfprobléma megoldásának szubrutinjaként . A legnyilvánvalóbb esetekben , tehát a maximális elemszámú független halmaz , a maximális elemszámú klikk , illetve a minimális független domináló halmaz keresése esetében a keresett halmaznak mindig MFH-nak vagy maximális klikknek kell lennie , tehát a keresés végrehajtható úgy is , hogy egy algoritmus listázza az összes maximális független halmazt vagy maximális klikket , és megtartja a legnagyobb vagy legkisebb méretűt . Hasonlóan , a minimális csúcslefedés is megkereshető , mint valamely MFH komplementere. megfigyelése szerint az MFH-k listázása a gráfokszínezésének megtalálására is használható : egy gráf pontosan akkor színezhetőszínnel , ha valamely MFH-jának komplementer gráfja páros . Ezt a megközelítést Lawler nem csak aszínezéshez használta fel , hanem egy általánosabb gráfszínező algoritmus részeként . Más szerzők azóta hasonló , egyre kifinomultabb gráfszínezési megközelítéseket dolgoztak ki . Más , komplex problémák szintén modellezhetők valamely specifikus típusú klikk vagy független halmaz kereséseként . Ezek motiválják annak az összes maximális független csúcshalmaz ( vagy maximális klikk ) listázásának algoritmikus problémájának hatékonyabb megoldását . Elég egyszerűen átültethető Moon and Moser az MFH-k számára vonatkozó/3-as korlátja egy olyan algoritmusba , ami az összes MFH-t O( 3n/3 ) idő alatt listázza . Ez az algoritmus a kimeneti halmazonként konstans időben lefut a lehető legnagyobb számú MFH-val rendelkező gráfokra . Sajnos azonban egy ilyen időkorláttal rendelkező algoritmus nagyon hatékonytalan tud lenni a kevesebb MFH-val rendelkező gráfokon . Így aztán számos kutató tanulmányozta a kimenetenként polinomális időben lefutó algoritmusokat . Az MFH-nként szükséges idő arányos a sűrű gráfok mátrixszorzásának idejével , illetve ritka gráfok egyes osztályainál ennél gyorsabb is lehet . A maximális elemszámú független halmazok keresésének párhuzamosítása Története Eredetileg úgy gondolták , hogy az MFH-keresés problémáját nem triviális párhuzamosítani , hiszen a lexikografikus MFH-keresés P-teljesnek bizonyult ; megmutatták azonban , hogy megadható egy determinisztikus párhuzamos megoldás akár a maximális halmazpakolás vagy a maximális párosítás problémájának -redukciójával , akár aSAT kielégíthetőségi probléma -redukciójával . Jellemzően az algoritmus szerkezete hasonlít a többi párhuzamos gráfalgoritmuséhoz : felosztják a gráfot kisebb lokális problémákra , melyek aztán ugyanazt az algoritmust párhuzamos módon sok helyen futtatva megoldhatók . Az MFH-probléma kezdeti kutatását a PRAM-modell szerint végezték , majd kiterjesztették a számítógépfürtökön futó elosztott algoritmusokra is . Az elosztott párhuzamos algoritmusok számos tervezési problémája az MFH-probléma esetében is előjön ; különös tekintettel arra , hogy az algoritmus futásidő és adatkommunikáció szempontjából is hatékony legyen , miközben a gráfot felosztja és a független halmazba elemeket helyez . Bonyolultságosztály 1984-ben Karp és tsai megmutatták , hogy az MFH-probléma PRAM-on történő megoldása az NC bonyolultsági osztályon belül -be tartozik . Ez azt jelenti , hogy az algoritmusuknak egy MFH megkereséséhez időre és helyre van szüksége , ahol a csúcshalmaz mérete . Ugyanebben a tanulmányukban egy randomizált párhuzamosított megoldást is leírtak , ami idő alatt futott le processzoron . Nem sokkal ezután Luby , Alon és tsai . Karpék eredményétől függetlenül javítottak ezen az eredményen , elérve az -t , futási idővel processzoron , ahol a gráf éleinek számát jelöli . Az algoritmus voltának igazolására először bemutattak egy randomizált algoritmust , aminek processzorra van szükség , de a véletlenszerűség megszüntethető processzor hozzáadásával . Jelenleg is nyitott kérdés , hogy az MFH-probléma vajon az osztályban található-e . . Kommunikáció , adatcsere Az elosztott MFH-algoritmusok létrehozását jelentősen befolyásolták a korábban a PRAM-modellre készített algoritmusok . A Luby , Alon és tsai. által végzett kezdeti kutatások számos elosztott algoritmushoz vezettek . Bitek átvitele szempontjából ezek az algoritmusok körönként legalább bitet igényelnek és a gráf egyéb karakterisztikájára is szükség van a működésükhöz . Például ismerni kell a gráf méretét vagy a szomszédos csúcsok maximális fokszámát le kell tudni kérdezni a működéshez.ben Métivier és tsai. sikeresen lecsökkentették a körönkénti üzenetek méretét az optimális értékre , és megszabadították az algoritmust a gráf egyéb tulajdonságai ismeretének igényétől . Jegyzetek . . . . . . . . . . . . . . . . . . . . . Gráfelmélet Gráfelméleti objektumok Számítási problémák a gráfelméletben de: Glossar Graphentheorie#Stabile Menge