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 -nak, melyben a szeparátor O(√n) helyett O(√n log n) csúcsból áll; az éles aszimptotikus korlátot elsőként 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 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.. 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..
Példa
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.. 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.
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
Mélységi rétegzés 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.. Egy hasonló szeparátor-konstrukció részletesebb vizsgálatával kimutatta, hogy S mérete √6√n-re, azaz körülbelül 2,45√n-re redukálható.
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 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 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.
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 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.
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..
Geometriai körszeparátorok 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 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..
Ez a módszer egy olyan véletlen algoritmushoz vezet, ami képes lineáris időben megtalálni egy szeparátort, és egy kevésbé praktikus determinisztikus algoritmushoz, ami ugyanúgy lineáris idejű.. 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 .