Síkgráf-elválasztási tétel

gráfelméleti állítás

A matematika, azon belül a gráfelmélet területén a síkgráf-elválasztási tétel, síkgráf-felbontási tétel, síkgráf-szeparációs tétel vagy Lipton–Tarjan-szeparátortétel (planar separator theorem) a síkbarajzolható gráfokra vonatkozó egyfajta izoperimetrikus egyenlőtlenség, ami kimondja, hogy bármely síkbarajzolható gráf kis számú csúcs eltávolításával kisebb darabokra szedhető szét. Pontosabban, egy n csúcsú gráfból O(√n) csúcsot eltávolítva (ahol O a nagy Ordó jelölésre utal) a gráfot olyan diszjunkt részgráfokra bontja fel, melyek mindegyikében legfeljebb 2n/3 csúcs található.

A szeparációs tételnek először egy gyengébb változatát sikerült bizonyítania (Ungar 1951)-nak, melyben a szeparátor O(√n) helyett O(√n log n) csúcsból áll; az éles aszimptotikus korlátot elsőként (Lipton & Tarjan 1979) igazolta. Azóta a szeparátortételt sokféleképpen sikerült bizonyítani, a tételben szereplő O(√n) tagot javították és a tételt kiterjesztették a nem síkbarajzolható gráfok egyes osztályaira is.

A síkgráf-elválasztási tétel ismételt alkalmazása egy szeparátorhierarchiát hoz létre, ami a gráf fafelbontásának vagy elágazás-felbontásának (branch-decomposition) formáját öltheti. Ezek a szeparátorhierarchiák felhasználhatók síkgráfokon futtatott hatékony „oszd meg és uralkodj”-algoritmusok létrehozására, és az ezeken a hierarchiákon végzett dinamikus programozás segítségével ezen gráfok általában NP-nehéz optimalizációs problémáit exponenciális időben megoldó vagy rögzített paraméter mellett kezelhető algoritmusok előállítására. A szeparátorhierarchiákat használják a nested dissection (kb. „egymásba ágyazott boncolás”) módszerében is, ami a végeselemes módszerben fellépő ritka lineáris egyenletrendszerek megoldásának hatékony, Gauss-eliminációs variánsa.

Demaine, Fomin, Hajiaghayi és Thilikos bidimenzionalitás-elmélete a síkgráf-elválasztási tételt általánosítja és nagyban kiterjeszti az alkalmazási területét a síkbarajzolható gráfok rengeteg minimalizálási problémája mellett az egy-egy tiltott minort nem tartalmazó gráfokra.

A tétel kimondása

szerkesztés

A tétel leggyakoribb megfogalmazásában úgy hangzik, hogy bármely G = (V,E) n csúcsú síkbarajzolható gráfhoz létezik G csúcsainak olyan három, A, S és B csúcshalmazba való particionálása, hogy akár A, akár B legfeljebb 2n/3 csúcsot tartalmaz, S-ben O(√n) csúcs van, és egyetlen A-beli csúcs sincs összekötve egyetlen B-beli csúccsal sem. Nem szükséges, hogy akár A, akár B a G gráf összefüggő részgráfjai legyenek. S-et a partíció szeparátorának nevezzük.

Egy ekvivalens megfogalmazás szerint bármely n csúcsú G síkbarajzolható gráf élei szétoszthatók a két éldiszjunkt részgráf, G1 és G2 között oly módon, hogy mindkét részgráf legalább n/3 csúcsot tartalmaz és a két részgráf csúcshalmazainak metszetében O(√n) csúcs található. Az ilyen szétosztást szeparációnak nevezzük.[1] Ha adott egy szeparáció, a csúcshalmazok metszete szeparátort alkot, és az egyik részgráfba tartozó csúcsok, amik nem tartoznak a másik részgráfhoz alkotják a legfeljebb 2n/3 csúcsból álló szeparált csúcshalmazokat. A másik irányból tekintve, ha meg van adva a tételnek megfelelő A, S és B csúcshalmazba történő szeparálás, akkor létrehozható olyan szeparáció, melyben az A-ból kiinduló élek G1-hez, a B-ből kiinduló élek G2-höz tartoznak, a maradék éleket (melyeknek mindkét végpontja S-ben található) pedig tetszés szerint szétosztjuk.

A szeparátortételben szereplő 2/3 konstans önkényesen választott, bármely más számmal helyettesíthető az (1/2,1) nyílt intervallumban a tétel további megváltoztatása nélkül: egy nem annyira kiegyenlített felosztásból létrehozható egyenlőbb méretű részhalmazokra felosztás oly módon, hogy a kiegyenlítetlen felosztás nagyobbik halmazát ismételten felvagdossuk, majd átcsoportosítjuk az eredményül kapott összefüggő komponenseket.[2]

 
Egy rácsgráf síkszeparátora.

Tekintsünk egy r sorból és c oszlopból álló rácsgráfot; a csúcsok n száma megegyezik rc-vel. Például az ábrán szereplő esetben r = 5, c = 8 és n = 40. Ha r páratlan, egyetlen középső sor van, egyébként két, a középponthoz egyformán közeli sor; hasonlóan, ha c páratlan, egyetlen középső oszlop van, egyébként pedig két, a középponthoz egyformán közeli oszlop. Ha az S-t ezen középső helyzetű sor(ok) vagy oszlop(ok) bármelyikének választjuk, S gráfból való eltávolításával két kisebb, összefüggő A és B részgráfot kapunk, melyek mindegyikében legfeljebb n/2 csúcs található. Ha, mint az ábrán, r ≤ c akkor a középső oszlop S szeparátora r ≤ √n csúcsból fog állni, hasonlóan, ha c ≤ r, akkor a középső sor szeparátorában legfeljebb √n csúcs lesz. Tehát minden rácsgráfnak van legfeljebb √n méretű S szeparátora, melynek eltávolítása a gráfot két, legfeljebb n/2 méretű összefüggő komponensre bontja.[3]

A síkgráf-felbontási tétel állítása szerint ilyen felbontás bármely síkbarajzolható gráfhoz előállítható. Tetszőleges síkbarajzolható gráfot választva annyi különbséget találunk, hogy a szeparátor mérete O(√n), ami nagyobb lehet √n-nél, az A és B részhalmazok méretének korlátja (a tétel leggyakoribb verzióiban) n/2 helyett 2n/3, és az A és B részhalmazok nem feltétlenül alkotnak összefüggő részgráfokat.

Konstrukciók

szerkesztés

Mélységi rétegzés

szerkesztés

(Lipton & Tarjan 1979) adott síkbarajzolható gráfot szükség esetén további élekkel egészít ki, hogy maximális legyen (síkbarajzolásának minden tartománya háromszög). Ekkor tetszőleges v csúcsból kiindulva mélységi keresést folytat, és v-től való távolságuk alapján rétegekre particionálja a gráfot. Ha l1 a medián szint (az a szint, amelynél lejjebb és följebb is legfeljebb n/2 csúcs található), akkor léteznie kell olyan l0 és l2 szinteknek O(√n) lépéssel l1 alatt, illetve fölött, melyek O(√n)-O(√n) csúcsot tartalmaznak, különben több mint n csúcs lenne az l1-közeli szinteken. Megmutatják, hogy léteznie kell egy S szeparátornak, ami előáll az l0 és l2 uniójából, egy G-beli e él végpontjaiból, melyek nem tartoznak a mélységi keresési fához és két szint között húzódnak, valamint az e-ből vissza az l0 szintre húzódó két mélységi keresési fa-útvonal csúcsaiból. Az így kapott S szeparátor mérete legfeljebb √8√n, azaz körülbelül 2,83√n. A szeparátor csúcsai és két diszjunkt részgráf lineáris idő alatt előállítható.

A szeparátortétel ezen bizonyítása alkalmazható olyan súlyozott síkbarajzolható gráfokra is, melyek minden csúcsa nemnegatív költségű. A gráf particionálható A, S és B csúcshalmazokra oly módon, hogy A-ra és B-re külön-külön legfeljebb a teljes költség ⅔-a esik, S csúcsainak száma O(√n) és nem húzódik A és B között él.[4] Egy hasonló szeparátor-konstrukció részletesebb vizsgálatával (Djidjev 1982) kimutatta, hogy S mérete √6√n-re, azaz körülbelül 2,45√n-re redukálható.

(Holzer et al. 2009) egyszerűsített megközelítést javasolnak: az előzővel megegyező módon kiegészítik a gráfot maximális síkgráffá és kialakítják a mélységi keresési fát. Ekkor minden, a fa részét nem képező e élhez kialakítanak egy kört oly módon, hogy e-t kombinálják a végpontjait összekötő útvonallal a fában. Bár ez a megközelítés nem garantálja, hogy nagy átmérőjű síkbarajzolható gráfokban kis szeparátort találjunk, a kísérletek szerint számos fajta síkgráfon jobb teljesítményt nyújt mind a Lipton–Tarjan-féle, mind a Djidjev-féle mélységi keresési módszereknél.

Egyszerű körszeparátorok

szerkesztés

Olyan gráf esetében, ami eleve maximális síkbarajzolható, létezik egy erősebb konstrukció, az egyszerű körszeparátor (simple cycle separator), egy olyan nem túl nagyméretű kör, melynél a kör belső, illetve külső részén (a gráf egyedi síkba ágyazását tekintve) egyaránt legfeljebb 2n/3 csúcs található. Ezt az állítást (Miller 1986) igazolja (√8√n méretű szeparátorral), olyan, módosított Lipton–Tarjan-jellegű mélységi kereséssel, melyben a keresés szintjeiben egyszerű körök szerepelnek.

(Alon, Seymour & Thomas 1994) az egyszerű körszeparátorok létezését közvetlenebb módon igazolja: kiválasztanak egy olyan C kört, ami legfeljebb √8√n csúcsból áll, és amin kívül legfeljebb 2n/3 csúcs található, és a lehető legkiegyenlítettebb módon választja szét a külső és belső csúcsokat, majd megmutatják, hogy az előfeltételezésekből következik, hogy C szeparátor legyen. Máskülönben a C-n belüli távolságoknak meg kellene egyeznie a C által körülzárt korongban lévő távolságokkal (a korongon belüli rövidebb útvonalból ugyanis egy jobb kört lehetne alkotni). Ráadásul C hosszúságának pontosan √8√n-nek kell lennie, egyébként javítani lehetne valamely élének a háromszög két másik oldalára történő kicserélésével. Ha C csúcsait az óramutató járása szerint 1-től √8√n-ig megszámozzuk, és az i csúcsot a √8√ni + 1 csúccsal párosítjuk, akkor ezek a párok a korongon belül csúcsdiszjunkt úttal összeköthetők, a Menger-tétel egy síkgráf-változata alapján. Az ilyen utak hossza azonban szükségképpen meghaladná n-et, amivel ellentmondásra jutunk. Egy hasonló módszer segítségével kimutatják, hogy létezik legfeljebb (3/√2)√n, azaz körülbelül 2,12√n méretű egyszerű körszeparátor.

(Djidjev & Venkatesan 1997) az egyszerű körszeparátor-tételben szereplő konstans faktort tovább javították 1,97√n-re. Módszerük szintén képes nemnegatív csúcs-súlyozott gráfokban egyszerű körszeparátorokat találni legfeljebb 2√n méretű szeparátorral, és kisebb szeparátorok előállítására is képes, a gráf kiegyensúlyozotlanabb particionálása árán. Kétszeresen összefüggő, nem maximális síkbarajzolható gráfokban léteznek olyan, közel lineáris időben megtalálható, egyszerű körszeparátorok, melyek mérete a tartományhosszúságok vektorának euklideszi normájával arányos.[5]

Geometriai körszeparátorok

szerkesztés

A körpakolási tétel szerint minden síkbarajzolható gráf reprezentálható diszjunkt belső részű korongok síkba elhelyezésével úgy, hogy a gráf két csúcsa akkor szomszédos, ha a nekik megfelelő korongok érintik egymást. Ahogy azt (Miller et al. 1997) megmutatta, minden ilyen pakoláshoz létezik olyan kör, ami a korongok közül legfeljebb 3n/4-et érint, vagy található azokon belül, a korongok közül legfeljebb 3n/4-et érint vagy található azokon kívül, és O(√n) korongon megy át.

Ennek bizonyításához Miller és tsai. sztereografikus projekcióval a körpakolást egy háromdimenziós egységgömbre vetítik. A projekció jó megválasztásával elérhető, hogy a gömb középpontja a felületén lévő korongok középpontjainak térbeli mediánja legyen, és így bármely, a középponton átmenő sík a gömböt két olyan féltérre bontsa, melyek bármelyike legfeljebb a korongok közül 3n/4-et foglal magába vagy metsz. Ha egyenlő valószínűséggel véletlenszerűen választunk egy középponton átmenő síkot, adott korong metszésének valószínűsége a korong sugarával lesz arányos. Így tehát a metszett korongok számának várható értéke a korongok sugarainak szummájával arányos. A sugarak négyzetösszege azonban a korongok teljes területével arányos, ami legfeljebb az egységgömb felszínével egyezhet meg, ami állandó. A Jensen-egyenlőtlenséget segítségül hívva megmutathatjuk, hogy amikor n nemnegatív valós szám négyzetösszegének egy konstans a korlátja, a számok összege O(√n). Tehát egy véletlenszerű síkkal elmetszett korongok számának várható értéke O(√n) és létezik olyan sík, ami legfeljebb ennyi korongot metsz. Ez a sík a gömböt egy főkörén metszi, ami visszavetíthető a síkba, mint egy a kívánt tulajdonságokkal rendelkező kör. A kör által metszett O(√n) korong azoknak a szeparátor csúcsoknak felel, amik elválasztják a kör belsejében található korongoknak megfelelő csúcsokat azoktól a csúcsoktól, amik a körön kívül lévő korongoknak felelnek meg, és mindkét halmazba legfeljebb 3n/4 csúcs tartozik.[6][7]

Ez a módszer egy olyan véletlen algoritmushoz vezet, ami képes lineáris időben megtalálni egy szeparátort,[6] és egy kevésbé praktikus determinisztikus algoritmushoz, ami ugyanúgy lineáris idejű.[8] A körpakolások sűrűségére ismert korlátok analizálásával megmutatható, hogy lehetséges olyan szeparátorokat találni, melyek mérete legfeljebb

 [9]

Bár ez a javított szeparátorméret a gráf particionálása kiegyenlítettségének rovására megy, (Spielman & Teng 1996) szerint így is javított konstans faktort tartalmaz az algoritmus idejét tekintve (Alon, Seymour & Thomas 1990) szeparátoraihoz képest. A gyakorlatban az algoritmus által előállított szeparátorok méretén lehet javítani, például a véletlenszerű vágó síkok esetében nem egyenletes eloszlást használva.[10]

A Miller és tsai. módszerében szereplő sztereografikus projekció elkerülhető, ha vesszük a legkisebb kör, ami a korongok középpontjainak valamely konstans hányadát tartalmazza, majd kiterjesztjük egy az [1,2] intervallumból véletlenszerűen választott konstanssal. Könnyen beláthatók hogy épp úgy mint Miller és tsainál, a kiterjesztett kört metsző korongok érvényes szeparátort alkotnak, ami várhatóan a megfelelő méretű szeparátor. Az eredményül kapott konstansok azonban valamivel rosszabbak.[11]

Spektrális particionálás

szerkesztés

A spektrális klaszterezési technikákat, melyekben egy gráf csúcsait a gráfból nyert mátrix sajátvektorainak koordinátai szerint csoportosítják, jó ideje alkalmazzák nem síkbarajzolható gráfok felbontási problémái heurisztikájának.[12] (Spielman & Teng 2007) megmutatta, hogy a spektrális klaszterezés alkalmas lehet a síkgráf-elválasztási tétel egy gyengébb, korlátos fokszámú változatának bizonyítására. Módszerük szerint az adott síkbarajzolható gráf csúcsait a gráf Laplace-mátrixa sajátvektorai második koordinátája szerint állítják sorba, és ezt a sorbaállítást azon a ponton particionálják, amely minimalizálja a partíció kisebbik felén lévő csúcsok által elvágott élek arányát. Megmutatják, hogy minden korlátos fokszámú síkbarajzolható gráfban létezik olyan, az előzőek szerinti particionálás, melyben az arány O(1/√n). Bár ez a felbontás nem feltétlenül kiegyensúlyozott, a két oldal közül a nagyobbikkal megismételve a felbontást és az ismétlések során létrejött vágások unióját képezve végül egy O(√n) élből álló kiegyensúlyozott partícióhoz jutunk. Ezen élek végpontjai O(√n) méretű szeparátort alkotnak.

Élszeparátorok

szerkesztés

A síkgráf-elválasztási tétel egy változatában élszeparátorok szerepelnek, azaz olyan kis élhalmazok, melyek egy vágást alkotnak a gráf csúcsainak A és B részhalmazai között. A két halmaz, A és B egyike sem lehet nagyobb a gráf n csúcsának valamely konkrét hányadánál (hagyományosan mindkét halmaz legfeljebb 2n/3 méretű lehet) és a gráf minden csúcsa vagy az A, vagy a B halmazhoz tartozik. A szeparátor azokból az élekből áll, melyek egyik végpontja az A, másik végpontja a B halmazban van. Az élszeparátor méretére vonatkozó korlátok általában a gráf csúcsainak számától és a csúcsok fokszámától is függnek: az olyan síkbarajzolható gráfoknak – például a kerékgráfoknak és a csillaggráfoknak –, melyekben van egy n − 1 fokszámú csúcs (domináló csúcs), nincs szublineáris élből álló élszeparátoruk, hiszen bármely élszeparátornak tartalmaznia kellene az összes, az univerzális csúcsból a vágás másik részébe futó élt. Elmondható azonban, hogy minden, Δ maximális fokszámú síkbarajzolható gráfnak van O(√(Δn)) méretű élszeparátora.[13]

Egy síkgráf duálisának egyszerű körszeparátora megfelel az eredeti gráf élszeparátorának.[14] A (Gazit & Miller 1990)-féle egyszerű körszeparátor-tételt adott síkgráf duálisára alkalmazva megerősíthető az élszeparátor méretére vonatkozó O(√(Δn)) korlát, annak megmutatásával, hogy minden síkbarajzolható gráfnak van olyan élszeparátora, aminek mérete egyenesen arányos csúcsai fokszámai vektorainak euklideszi normájával.

(Papadimitriou & Sideri 1996) leír egy polinom idejű algoritmust a legkisebb élszeparátor megkeresésére; az algoritmus G-t két azonos méretű részgráfra osztja, feltéve, hogy G egy (legfeljebb konstans számú lyukkal tűzdelt) rácsgráf feszített részgráfja. Sejtésük szerint a probléma általános síkbarajzolható gráfokra NP-teljes, és megmutatják, hogy a probléma bonyolultsága ugyanakkora tetszőleges számú lyukkal tűzdelt rácsgráf feszített részgráfjaira, mint tetszőleges síkbarajzolható gráfokra.

Alsó korlátok

szerkesztés
 
Egy ikozaéder lapjainak 100 háromszögből álló rácsra cserélésével kapott poliéder, (Djidjev 1982) alsó korlátot célzó konstrukciójának egy példája.

Egy √n × √n-es rácsgráfban az s < √n pontból álló S halmaz legfeljebb s(s − 1)/2 rácspontot tud közrefogni, ahol a maximum úgy érhető el, hogy a rács sarkához közel kiinduló átlóban helyezzük el S csúcsait. Tehát egy olyan szeparátor esetén, ami legalább n/3 pontot választ le a megmaradó rácsból, s-nek legalább √(2n/3)-nak, azaz kb. 0,82√n-nek kell lennie.

Léteznek olyan n-csúcsú síkbarajzolható gráfok (tetszőlegesen nagy n értékekre), melyekben bármely olyan S szeparátor, ami a maradék gráfot legfeljebb 2n/3 csúcsot tartalmazó részgráfokra bontja vertices, legalább √(4π√3)√n, azaz mintegy 1,56√n csúcsból áll.[2] A konstrukcióban szerepet játszik egy gömbfelület konvex poliéderrel való közelítése, majd a poliéder lapjainak háromszögekből álló ráccsal való helyettesítése után a gömb felületére izoperimetrikus egyenlőtlenségek alkalmazása.

Szeparátorhierarchiák

szerkesztés

Egy síkbarajzolható gráf szeparátorai egyfajta szeparátorhierarchiává állnak össze, ami egy kisebb gráfokra történő rekurzív felbontás. Egy szeparátorhierarchia előállhat egy bináris fa formájában, melynek gyökere reprezentálja magát a gráfot, a gyökér két közvetlen „gyerek” csúcsa pedig annak a két rekurzívan megkonstruált szeparátorhierarchiának a két gyökere, melyeket egy szeparátor A és B részhalmazának feszített részgráfjaiból kapunk.

Egy ilyen jellegű szeparátorhierarchia adja adott gráf fafelbontásának alapját, melyben a fa adott csomópontjához tartozó csúcshalmaz éppen a csomóponttól a fa gyökeréig vezető út szeparátorainak uniójával egyezik meg. Mivel a gráfok mérete a fa minden szintjén konstans faktorral csökken, a szeparátorok méretére vonatkozó felső korlátok szintén minden egyes szinten konstans faktorral csökkennek, így ezeken az útvonalakon a szeparátorok méretei mértani sort alkotnak O(√n)-ig. Tehát az így kialakított szeparátor szélessége O(√n), és alkalmas annak megmutatására, hogy minden síkbarajzolható gráf favastagsága (minimális fafelbontás szélessége) O(√n).

Ha a szeparátorhierarchiát közvetlenül állítanánk elő a bináris fán felülről lefelé haladva, a fa minden egyes csomópontjához tartozó feszített részgráfon lineáris idejű szeparátoralgoritmust futtatva, az összesen O(n log n) időt venne igénybe. Lehetséges azonban a teljes szeparátorhierarchia lineáris idejű előállítása is: a Lipton–Tarjan mélységi keresési megközelítést alkalmazva, megfelelő adatszerkezetek segítségével minden particionáló lépést szublineáris időben elvégezve.[15]

Ha egy hasonló jellegű hierarchiát szerkesztünk, ami a szeparátorok helyett a szeparációkon alapul, és melyben a gyökér csomópont két gyereke annak a két rekurzívan megkonstruált hierarchiának a két gyökere, melyeket egy szeparáció G1 és G2 részgráfjaiból kapunk, akkor a teljes struktúra fafelbontás helyett elágazás-felbontást vagy ágfelbontást (branch-decomposition) alkot. Ebben a felbontásban bármely szeparációnak a szélességét a csomóponttól a fa gyökeréig vezető út szeparátorméreteinek összege korlátozza, tehát bármely így kapott elágazás-felbontás szélessége O(√n) és bármely síkbarajzolható gráf fafelbontásának szélessége O(√n). Bár sok kapcsolódó gráffelbontási probléma NP-teljes még síkbarajzolható gráfokra is, egy síkbarajzolható gráf minimális szélességű elágazás-felbontása polinom időben elvégezhető.[16]

(Alon, Seymour & Thomas 1994) módszereit közvetlenebb módon alkalmazva az elágazás-felbontás konstrukciója során (Fomin & Thilikos 2006a) megmutatta, hogy egy síkbarajzolható gráf fafelbontásának szélessége legfeljebb 2,12√n, ugyanaz a konstans, ami Alon és tsai egyszerű körszeparátor-tételében is szerepel. Mivel minden gráfra igaz, hogy favastagsága legfeljebb a fafelbontás másfélszerese, ezért a síkbarajzolható gráfok favastagsága legfeljebb 3,18√n.

Más gráfosztályok

szerkesztés

Egyes ritka gráfoknak nincsen szublineáris méretű szeparátoruk: egy expander gráfban a csúcsok valamely konstans hányadát törölve még mindig egyetlen összefüggő komponens marad.[17]

Talán a legkorábbi ismert szeparátorokkal kapcsolatos tétel (Jordan 1869) eredménye, miszerint bármely fa egyetlen csúcs eltávolításával egyenként legfeljebb n/2 csúcsot tartalmazó részfákra bontható.[6] Pontosabban az a csúcs rendelkezik ezzel a tulajdonsággal, ami minimalizálja a maximális komponensméretet; hiszen, ha nem rendelkezne vele, akkor az egyedi nagy részfában lévő szomszédja egy még jobb particionálást alkotna. Ugyanezt a technikát tetszőleges gráf fafelbontására alkalmazva megmutatható, hogy bármely gráfnak van olyan szeparátora, aminek mérete legfeljebb a favastagságával egyenlő.

Ha egy G gráf nem síkbarajzolható, de beágyazható egy g génuszú felületbe, akkor létezik O((gn)1/2) csúcs nagyságú szeparátora. (Gilbert, Hutchinson & Tarjan 1984) ezt (Lipton & Tarjan 1979) érveléséhez hasonlóan bizonyítja. Mélységi keresési szintekre csoportosítják a gráf csúcsait, majd keresnek két olyan szintet, melynek eltávolításával legfeljebb egy, kis számú szintből álló, nagyméretű komponens marad. Ez a megmaradó komponens síkbarajzolhatóvá alakítható a génuszával arányos számú mélységi keresési útvonal eltávolításával, ami után a már ismert Lipton–Tarjan-módszer alkalmazható a megmaradt síkbarajzolható gráfra. Ez az eredmény az eltávolított két szint és a köztük lévő szintek száma közötti óvatos egyensúlyozásból következik. Ha bemenetként meg van adva egy gráfbeágyazás, a hozzá tartozó szeparátor lineáris időben előállítható. A g génuszú gráfoknak továbbá létezik legfeljebb O((gΔn)1/2) méretű élszeparátora.[18]

A korlátos génuszú gráfok a minorképzés műveletére zárt gráfcsaládot alkotnak, és bármely, minorzárt gráfcsaládra vonatkoznak szeparátortételek. Pontosabban, ha egy gráfcsaládnak h csúcs méretű tiltott minora van, akkor létezik O(hn) csúcs méretű szeparátora, ami O(n1 + ε) időben megtalálható tetszőleges ε > 0-ra.[19]

 
Korongok metszetgráfja, ahol legfeljebb k = 5 korong fedi a sík bármely pontját.

A (Miller et al. 1997)-féle körszeparátor módszer általánosítható tetszőleges d-dimenziós gömbökből álló metszetgráfokra, melyek rendelkeznek azzal a tulajdonsággal, hogy a tér bármely pontja legfeljebb valamely konstans k számú gömbbel van fedésben, továbbá d-dimenziós k-legközelebbi szomszéd-gráfra,[6] valamint a végeselemes hálók gráfjaira.[20] Az így megszerkesztett gömbszeparátorok a bemeneti gráfot legfeljebb n(d + 1)/(d + 2) csúcs méretű részgráfokra particionálják. A szeparátorok mérete a k-szoros gömbmetszetgráfokra és a k-legközelebbi szomszéd-gráfokra O(k1/dn1 − 1/d).[6]

Alkalmazások

szerkesztés

„Oszd meg és uralkodj”-algoritmusok

szerkesztés

A szeparátorfelbontások jó szolgálatot tesznek a síkbarajzolható gráfok problémái hatékony megoldását szolgáló „oszd meg és uralkodj”-algoritmusok előállításában. Ilyen eset például egy síkbarajzolható súlyozott irányított gráfban a legrövidebb kör megkeresése. Ez a következő lépésekben elvégezhető:

  • Particionáljuk az adott G gráfot a síkgráf-elválasztási tétel szerint S, A és B részgráfokba
  • Rekurzívan keressük meg A és B legrövidebb köreit
  • A Dijkstra-algoritmussal minden S-beli s csúcsra keressük meg a G-ben s-en keresztülhaladó legkisebb kört.
  • Adjuk vissza a fenti lépésekben talált legrövidebb kört.

Az algoritmus A-hoz és B-hez tartozó rekurzív hívásainak idejét főleg a Dijkstra-algoritmus O(√n)-szer történő meghívása dominálja, így tehát az algoritmus a legrövidebb kört O(n3/2 log n) időben találja meg.

Ugyanennek a legrövidebb kör problémának egy gyorsabb, O(n log3n) időben futó megoldását adja (Wulff-Nilsen 2009). Az ő algoritmusa ugyanezt a szeparátor-alapú „oszd meg és uralkodj”-struktúrát használja, de tetszőlegesen választott szeparátorok helyett egyszerű körszeparátorokat alkalmaz, így az S csúcsai a körszeparátoron belül, illetve kívül található gráfok egyetlen tartományához tartoznak. Ekkor a Dijkstra-algoritmus O(√n)-szeri meghívása helyett körmönfontabb algoritmusokkal keresi meg a síkgráf egyetlen tartományának összes csúcsából kiinduló legrövidebb utakat, majd kombinálja őket a két részgráftól való távolságokkal. Súlyozott, de irányítatlan síkbarajzolható gráfok legrövidebb köre ekvivalens a duális gráf minimális vágásával, így O(n log log n) időben megtalálható,[21] a súlyozatlan és irányítatlan síkbarajzolható gráf legrövidebb köre (azaz girthparamétere) pedig O(n) időben.[22] (A súlyozatlan gráfoknál azonban a leggyorsabb algoritmus nem a szeparátortételen alapul.)

Frederickson 1986-ban egy másik gyorsabb algoritmussal állt elő az egyetlen forrásból kiinduló legrövidebb utak keresésére síkbarajzolható gráfokban a szeparátortételt felhasználva.[23] Ez Dijkstra algoritmusának javított változata, ami csúcsok egy gondosan kiválasztott részhalmazán végez iteratív keresést. Ez a változat O(n √(log n)) időt vesz igénybe egy n-csúcsú gráf esetén. Szeparátorok segítségével megkeresi egy gráf „divízióját”, azaz az élhalmaz két vagy több részhalmazra, „régiókra” osztását. Egy csomópontot (csúcsot) akkor tartalmaz egy régió, ha a régió valamely éle illeszkedik a csúcsra. Az olyan csúcs, amit több régió tartalmaz, az őt tartalmazó régiók határhelyzetű csúcsa. A módszer az n csomópontú gráf r-divízióját taglalja, ami a gráf O(n/r) régióra történő felosztása, melyek mindegyike O(r) csomópontot tartalmaz, közöttük O(√r) határhelyzetű csomóponttal. Frederickson megmutatta, hogy egy r-divízió O(n log n) időben előállítható a szeparátortétel rekurzív alkalmazásával.

A problémát megoldó algoritmusának vázlatos működése a következő.

1. Előfeldolgozó fázis: a gráfot gondosan kiválasztott (csúcs-)részhalmazokra osztjuk, majd meghatározzuk az egyes részhalmazok elemei közötti legrövidebb utakat, ahol van az út köztes csúcsai között az adott részhalmazon kívül eső. Ebben a fázisban megtörténik a G0  síkbarajzolható gráf átalakítása egy 3-nál nagyobb fokszámmal nem rendelkező G gráffá. Az Euler-formula egyik következményeként az eredményül kapott gráf csúcsainak száma n ≤ 6n0 -12, ahol n0  a G0  csúcsainak száma. Ez a fázis garantálja továbbá az r-divízió a megfelelő tulajdonságait, a következők szerint. A síkbarajzolható gráf olyan r-divíziójáról van szó, melyben

  • minden határhelyzetű csúcsot legfeljebb három régió tartalmaz;
  • minden, nem összefüggő régió olyan összefüggő komponensekből áll, melyek mindegyikének pontosan ugyanazzal az egy vagy két összefüggő régióval vannak közös határhelyzetű csúcsai.

2. Keresési fázis:

  • Fő löket („Main Thrust”): megkeressük a forrás és a részhalmaz egyes csúcsai közötti legrövidebb utak hosszát. Amikor a részhalmaz egy v csúcsát lezárjuk, d(w) értékét minden w csúcsra frissíteni kell abban a részhalmazban, melyben létezik v és w közötti út.
  • Takarítás („Mop-up”): az összes többi csúcshoz vezető legrövidebb út hosszának meghatározása.

Henzinger és tsai. a Frederickson által a síkbarajzolható gráfokon „single source shortest path” (egy kezdőpontból az összes többi pontba vezető legrövidebb út) algoritmussal futtatott r-divíziós technikát kiterjesztették nemnegatív élhosszakra, és lineáris idejű algoritmust adtak meg.[24] Módszerük a Frederickson-féle gráfdivízió fogalmának általánosítása oly módon, hogy egy n-csúcsú gráf (r,s)-divíziója a gráf felosztása O(n/r) régióra, melyek mindegyike r{O(1)}  csúcsot tartalmaz és legfeljebb s határhelyzetű csúcsot. Ha egy (r, s)-divíziót ismételten kisebb régiókra osztunk, rekurzív divízióról beszélhetünk. Ez az algoritmus körülbelül log*n rekurziós szintet használ. A rekurzív divízió gyökeres faként jelenik meg, melynek levelei G egyes éleivel vannak címkézve. A fa gyökere jelképezi a teljes G-t tartalmazó régiót, a gyökér közvetlen leszármazottai a teljes G alrégióit és így tovább. Minden levél, avagy atomi régió pontosan egy élt tartalmaz.

A nested dissection (kb: „egymásba ágyazott boncolás”) a síkgráf-struktúrájú ritka, szimmetrikus lineáris egyenletrendszerek (melyek például a végeselemes módszerben jelennek meg) Gauss-eliminációs megoldására szolgáló, szeparátorhierarchiákon alapuló „oszd meg és uralkodj”-variáns. Alkalmazása során az egyenletrendszert leíró gráfban keresni kell egy szeparátort, majd a szeparátorral elválasztott két alprobléma változóit rekurzívan eliminálni kell, majd magának a szeparátornak a változóit is.[3] Ennek a módszernek a feltöltődési értéke („fill-in”, a mátrix kapott Cholesky-felbontásában az újonnan keletkezett nemnulla elemek száma) alacsony, O(n log n),[25] ami versenyképessé teszi a nested dissectiont az ugyanezen a problémán alkalmazott többi iteratív módszerrel.[3]

Klein, Mozes és Weimann [26] megadtak egy O(n log2 n)-idejű, lineáris terű algoritmust, ami képes síkbarajzolható irányított gráfban egy s forrásból az összes csúcsba menő legrövidebb utak megállapítására, ahol a gráfban pozitív és negatív irányított élhosszúságok is megengedettek, de negatív értékű körök nem. Algoritmusuk síkgráf-szeparátorok segítségével keres egy C Jordan-görbét, ami O(√n) csúcson megy át (de egyetlen élt sem metsz) úgy, hogy n/3 és 2n/3 közötti csúcsot foglal magába. A csúcsok, amiken C átmegy, határhelyzetű csúcsok. Az eredeti G gráfot ekkor a G0  és G1  gráfokba választja ketté, a síkba ágyazást C mentén elvágva és a határhelyzetű csúcsokat megkettőzve. Az i = 0 és 1 értékekre Gi -ben a határhelyzetű csúcsok egyetlen Fi  tartomány határán helyezkednek el.

A Klein, Mozes és Weimann által alkalmazott megközelítés nagy vonalakban a következő:

  • Rekurzív hívás: az első fokozat rekurzívan kiszámítja az r-től való távolságokat Gi-ben  i = 0, 1-re.
  • Részen belüli határtávolságok (Intra-part boundary-distances): Minden G i  gráfban kiszámítja a Gi  határhelyzetű csúcsai közötti összes távolságot. Ez O(n log n) időt vesz igénybe.
  • Egy kezdőpontból mért részek közötti határtávolságok (Single-source inter-part boundary distances): Egy G-beli legrövidebb út váltakozik G0  és G1  között, hogy megállapíthassuk a G-beli, r-től az összes határhelyzetű csúcsig vezető távolságokat. Váltakozó iterációk során felhasználjuk a $G0  és $G1 -beli összes határhelyzetű távolságot. Az iterációk száma O(√n), így a fokozat teljes időigénye O(n α(n)), ahol α(n) az inverz Ackermann-függvény.
  • Egy kezdőpontból mért részek közötti távolságok (Single-source inter-part distances): a korábbi fokozatokban kiszámított távolságokat használja fel egy Dijkstra-számításban minden egyes Gi  egy módosított változatán, ezzel kiszámítva a G-ben r-től az összes csúcsig a távolságokat. Ez a fokozat O(n log n) időt vesz igénybe.
  • A kezdőponti távolságok új kezdőpontba helyezése (Rerooting single-source distances): a G-beli, r-től mért távolságok nemnegatív hosszokra transzformálása, majd Dijkstra algoritmusának ismételt felhasználásával az s-től való távolságok kiszámítása. Ez a fokozat O(n log n) időt vesz igénybe.

Az algoritmus fontos részét képezi az árfüggvények (price functions) és redukált hosszak (reduced lengths) használata. Egy ι(·),irányított élhosszakkal rendelkező G irányított gráfbeli árfüggvény olyan φ függvény, ami a G csúcsait a valós számokhoz rendeli. Egy uv irányított él φ szerinti redukált hossza, ιφ(uv) = ι(uv) + φ(u) − φ(v). Egy alkalmas árfüggvény olyan árfüggvény, ami G minden irányított élére nemnegatív redukált hosszakat állít elő. Haszna abban mutatkozik meg, hogy a pozitív és negatív hosszakat is tartalmazó legrövidebb út problémát kizárólag nemnegatív hosszakat tartalmazóra lehet vele konvertálni, ami aztán a Dijkstra-algoritmussal már megoldható.

A szeparátor-alapú „oszd meg és uralkodj”-paradigmát felhasználták dinamikus gráfalgoritmusok[27] és pont helyzetének meghatározását szolgáló algoritmusok[28] adatstruktúrájának tervezésében, sokszög háromszögekre bontására,[15] illetve legrövidebb utak keresésére[29] szolgáló algoritmusok tervezésében, legközelebbi szomszéd-gráfok konstruálásában,[30] továbbá síkbarajzolható gráf maximális elemszámú független halmazát előállító közelítő algoritmusokban.[28]

NP-nehéz optimalizálási problémák egzakt megoldása

szerkesztés

Egy síkbarajzolható gráf fafelbontásán vagy ágfelbontásán dinamikus programozást alkalmazva számos NP-nehéz optimalizációs probléma√n vagy √n log n szerinti exponenciális időben megoldhatóvá válik.

Ilyen alakban megjelenő korlátok ismertek maximális elemszámú független halmazok, Steiner-fák és Hamilton-körök megkeresésére, valamint a síkbarajzolható gráfbeli utazó ügynök-probléma megoldására.[31] Hasonló, geometrikus gráfokra vonatkozó szeparátortételeket alkalmazó módszerekkel hasonló időkorlátok alatt oldhatók meg az euklideszi utazó ügynök-problémák és Steiner-fa problémák is.[32]

Olyan parametrizált problémák esetében, melyek a síkbarajzolhatóság megtartásával és a bemeneti gráf méretének lineáris függvénye szerinti méretű kernellel előfeldolgozhatók, ezzel a megközelítéssel olyan, rögzített paraméter mellett kezelhető algoritmusok tervezhetők, melyek futásideje a bemeneti gráf méretének polinom, √k-nak pedig exponenciális függvénye, ahol k az algoritmus paramétere. Ilyen alakú időkorlátok ismertek a k méretű csúcslefedések és domináló halmazok megkeresésére.[33]

Approximációs algoritmusok

szerkesztés

(Lipton & Tarjan 1980) megfigyelése szerint a szeparátortétel segítségével síkbarajzolható gráfok NP-nehéz optimalizációs problémáira, mint amilyen a maximális elemszámú független halmaz keresése előállíthatók polinomiális approximációs sémák. Konkrétan, egy szeparátorhierarchia megfelelő szinten történő csonkolásával olyan, O(n/√log n) méretű szeparátor található, aminek eltávolítása a gráfot c log n méretű részekre bontja, bármilyen c konstansra. A négyszíntétel alapján léteznie kell legalább n/4 méretű független csúcshalmaznak, ezért az eltávolított csúcsok a maximális elemszámú független halmaz elhanyagolható részét adják, és a maradék részgráfok maximális elemszámú független halmazai függetlenül, méretük szerinti exponenciális időben megtalálhatók. Ezt a megközelítést kombinálva a későbbi, lineáris idejű szeparátorhierarchia-előállítási módszerekkel[15] és az izomorf részgráfok független halmazainak számítását elősegítő, táblázatból történő kikereséssel, lehetőség nyílik az optimális mérettől legfeljebb 1 − O(1/√log n) faktorral eltérő független halmazok lineáris idejű előállítására. Ennél a faktornál 1-hez még közelebb lévő approximációs arány érhető el (Baker 1994) későbbi megközelítésével (ami fafelbontáson alapul, de nem használ síkszeparátorokat), ami jobb egyensúlyozást tesz lehetővé az idő és az approximáció minősége között.

Hasonló, szeparátoralapú approximációs megoldásokat vetettek be más nehéz problémák, például a csúcslefedés-probléma közelítő kiszámítására.[34] (Arora et al. 1998) a szeparátorokat másként használva approximálják a súlyozott síkbarajzolható gráfok legrövidebb út-metrikájának utazó ügynök-problémáját; algoritmusuk dinamikus programozással keresi meg azt a legrövidebb bejárást, ami a szeparátorhierarchia minden egyszer szintjén a szeparátoron korlátozott számban halad át, majd megmutatják, hogy az áthaladások korlátjának növekedésével az így konstruált bejárások az optimális bejárás hosszúságát approximálják.

Gráftömörítés

szerkesztés

Síkbarajzolható gráfok és más, szeparálható gráfok esetén szeparátorokat használó adattömörítési algoritmusok kisebb tárterületen ábrázolhatják. Az ilyen algoritmusok működésének lényege, hogy egy k szám kiválasztása után az adott síkbarajzolható gráfot szeparátorokkal ismételten O(n/k) darab, legfeljebb k méretű részgráfra osztjuk, ahol maguk a szeparátorok O(n/√k) csúcsot tartalmaznak. A k értékének alkalmas megválasztásával (legfeljebb n logaritmusával arányos legyen) a nem izomorf k-csúcsú síkbarajzolható részgráfok száma lényegesen kisebb a felbontásban szereplő részgráfok számánál, tehát a gráf tömöríthető oly módon, hogy létrehozzuk a lehetséges nem izomorf részgráfok táblázatát, majd a szeparátor-dekompozíció részgráfjait a táblázatbeli indexeivel reprezentáljuk. A gráf a szeparátorcsúcsok alkotta maradék része letárolható akár direkten, akár az imént említett rekurzív adatstruktúrát használva. Ezzel a módszerrel a síkbarajzolható gráfok és néhány egyéb korlátozott gráfosztály információelméleti szempontból optimális számú biten eltárolható: ha az ábrázolandó gráfcsaládban Pn darab n-csúcsú gráf található, akkor a család egy-egy gráfja mindössze (1 + o(n))log2Pn bittel ábrázolható.[35] Ugyanilyen logika mentén felépített reprezentáció segítségével olyan konstans idejű lekérdezések is lehetségesek, mint a csúcsok közötti szomszédosságnak és a csúcsok fokszámának vizsgálata, valamint a szomszédos csúcsok listázása; ezt a részgráfok táblázatának további információkkal való kiegészítése teszi lehetővé.[36][37]

Univerzális gráfok

szerkesztés

Egy F gráfcsalád univerzális gráfja olyan gráf, ami az F család minden tagját részgráfként tartalmazza. Szeparátorok segítségével megmutatható, hogy megmutatható, hogy az n-csúcsú síkgráfoknak vannak univerzális gráfjai O(n3/2).[38]

A konstrukcióhoz szükséges egy olyan, erősebb alakra hozott szeparátortétel, melyben a szeparátor három csúcshalmazának méretei nem függnek a gráf szerkezetétől: létezik olyan c szám, melynek nagysága legfeljebb √n konstansszorosa, hogy minden n-csúcsú síkbarajzolható gráf felosztható A, S és B részhalmazokba, ahol A és B között nem mennek élek, ahol |S| = c és ahol |A| = |B| = (n − c)/2. Ez megmutatható a szokásos szeparátortétel újra és újra alkalmazásával a gráfra egészen addig, míg a partíció összes komponense elosztható két, n/2-nél kevesebb csúcsot tartalmazó részhalmazba, majd ezekből addig mozgatva csúcsokat a szeparátorba, míg az el nem éri a megadott méretet.

Miután ez az erősebb alakú szeparátortétel előállt, felhasználásával előállítható az n-csúcsú síkbarajzolható gráfok olyan szeparátorhierarchiája, ami szintén nem függ a gráfok szerkezetétől: az ebből a hierarchiából képzett fafelbontás szélessége O(√n) és bármilyen síkbarajzolható gráfhoz használható. Ebben a fafelbontásban azon csúcspárok halmaza, melyek a fafelbontás közös csomópontjához tartoznak, egy O(n3/2) csúcsú triviálisan perfekt gráfot alkot, mely minden n-csúcsú síkbarajzolható gráfot tartalmaz részgráfként. Egy hasonló jellegű konstrukció megmutatja, hogy a korlátos fokszámú síkbarajzolható gráfok O(n log n) élszámú univerzális gráffal rendelkeznek, ahol az O jelölésben elrejtett konstans a fokszámkorláttól függ. Bármely, síkbarajzolható gráfokhoz (vagy akár nem korlátos fokszámú fákhoz) tartozó univerzális gráfnak rendelkeznie kell Ω(n log n) éllel, de az nem ismeretes, hogy akár ez az alsó korlát, akár az O(n3/2) felső korlát éles-e tetszőleges síkbarajzolható gráf univerzális gráfjaira.[38]

Fordítás

szerkesztés
  • Ez a szócikk részben vagy egészben a Planar separator theorem című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
  1. (Alon, Seymour & Thomas 1990).
  2. a b (Djidjev 1982).
  3. a b c (George 1973). Ahelyett, hogy egy sort vagy oszlopot választana, George egy sor és oszlop uniójával a gráfot négy részre particionálja.
  4. (Lipton & Tarjan 1979).
  5. (Gazit & Miller 1990).
  6. a b c d e (Miller et al. 1997).
  7. (Pach & Agarwal 1995).
  8. (Eppstein, Miller & Teng 1995).
  9. (Spielman & Teng 1996).
  10. (Gremban, Miller & Teng 1997).
  11. (Har-Peled 2011).
  12. (Donath & Hoffman 1972); (Fiedler 1973).
  13. (Miller 1986) bizonyította 2-összefüggő síkbarajzolható gráfokra, majd (Diks et al. 1993) kiterjesztette az összes síkbarajzolható gráfra.
  14. (Miller 1986); (Gazit & Miller 1990).
  15. a b c (Goodrich 1995).
  16. (Seymour & Thomas 1994).
  17. (Lipton & Tarjan 1979); (Erdős, Graham & Szemerédi 1976).
  18. (Sýkora & Vrťo 1993).
  19. (Kawarabayashi & Reed 2010). A minorzárt gráfcsaládok szeparátoraival foglalkozó korábbi munkákhoz lásd (Alon, Seymour & Thomas 1990), (Plotkin, Rao & Smith 1994) és (Reed & Wood 2009).
  20. (Miller et al. 1998).
  21. (Łącki & Sankowski 2011).
  22. (Chang & Lu 2011).
  23. Greg n. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM J. Comput., pp. 1004-1022, 1987.
  24. Monika R. Henzinger , Philip Klein , Satish Rao , Sairam Subramanian, \textit{Faster shortest-path algorithms for planar graphs}, Journal of Computer and System Science, Vol. 55, Issue 1, August 1997.
  25. (Lipton, Rose & Tarjan 1979); (Gilbert & Tarjan 1986).
  26. Philip N. Klein, Shay Mozes and Oren Weimann, Shortest Paths in Directed Planar Graphs with Negative Lengths: a Linear-Space O(n log2  n)-Time Algorithm}, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009.
  27. (Eppstein et al. 1996); (Eppstein et al. 1998).
  28. a b (Lipton & Tarjan 1980).
  29. (Klein et al. 1994); (Tazari & Müller-Hannemann 2009).
  30. (Frieze, Miller & Teng 1992).
  31. (Bern 1990); (Deĭneko, Klinz & Woeginger 2006); (Dorn et al. 2005); (Lipton & Tarjan 1980).
  32. (Smith & Wormald 1998).
  33. (Alber, Fernau & Niedermeier 2003); (Fomin & Thilikos 2006b).
  34. (Bar-Yehuda & Even 1982); (Chiba, Nishizeki & Saito 1981).
  35. (He, Kao & Lu 2000).
  36. (Blandford, Blelloch & Kash 2003).
  37. (Blelloch & Farzan 2010).
  38. a b (Babai et al. 1982); (Bhatt et al. 1989); (Chung 1990).

Kapcsolódó szócikkek

szerkesztés