Tasoosion lause

Tasoosiolause  on tasograafien isoperimetrisen epäyhtälön muoto , jossa sanotaan, että mikä tahansa tasograafi voidaan jakaa pienemmiksi paloiksi poistamalla pieni määrä pisteitä. Erityisesti poistamalla O(√ n ) pistettä graafista, jossa on n pistettä (tässä O tarkoittaa "suuria O" ), graafi voidaan osioida irrallisiin aligrafeihin , joista jokaisessa on enintään 2 n /3 kärkeä.

Ungar ( Ungar 1951 ) osoitti heikomman tasomaisen osiolauseen, jossa erottimessa on O(√ n  log  n ) -pisteitä O(√ n ) -pisteen sijaan , ja ensin todistettiin lause, jolla on vahvempi asymptoottinen sidottu erottimen kokoon. Lipton ja Tarjan ( Lipton ja Tarjan 1979) . Heidän kirjoituksensa jälkeen tasoosiolause on todistettu uudelleen useilla eri tavoilla ja lauseen O(√ n ) -vakiota on parannettu. Lause on myös laajennettu joihinkin epätasoisten graafien luokkiin.

Osiointilauseen uudelleen soveltaminen tuottaa erotinhierarkian, joka voi olla joko puuhajotelman tai haaragraafin hajotuksen muodossa . Erotinhierarkiaa voidaan käyttää tehokkaiden " Dive and Conquer " -algoritmien kehittämiseen tasokaavioille, ja näiden hierarkioiden dynaamista ohjelmointia voidaan käyttää eksponentiaalisen ajan ja kiinteän parametrin ratkaistavissa olevien kehittämiseen NP-kovien optimointiongelmien ratkaisemiseksi näissä kaavioissa. Erotinhierarkiaa voidaan käyttää myös sisäkkäisdissektiossa , joka on Gaussin eliminoinnin tehokas muunnelma elementtimenetelmässä syntyvien harvojen lineaaristen algebrallisten yhtälöiden ratkaisemiseen .

Kaksiulotteisuuden teoria Eric Demain , Fedor Fomin, Mohammed Hadjigaya ja Dimitros Tilikos yleistää ja laajentaa merkittävästi tasomaisen osiointilauseen soveltamisalaa laajaan tasograafien ja yleisemmin graafien ongelmajoukon. eivät sisällä tiettyä alaikäistä .

Lauseen lause

Tavallisessa muotoilussaan tasoosiolause sanoo, että missä tahansa tasograafissa G  = ( V , E ), jossa on n kärkeä, on olemassa G:n kärkien osio kolmeen joukkoon A , S ja B siten, että kukin joukoista A: lla ja B :llä on korkeintaan 2 n /3 kärkeä, S :llä O(√ n ) pistettä, eikä ole olemassa kulmia, joiden toinen pää on A: ssa ja toinen B :ssä . Ei vaadita, että A tai B ovat G : n yhdistetyt osagraafit . Joukkoa S kutsutaan tämän osion erottimeksi .

Vastaava formulaatio on, että minkä tahansa tasograafin G , jossa on n kärkeä, reunat voidaan jakaa kahdeksi alagraafiksi G 1 ja G 2 , joita ei ole liitetty reunoilla siten, että molemmilla aligraafilla on vähintään n /3 kärkeä, kun taas näiden kahden aligraafin kärkijoukoilla on O(√ n ) -pistettä. Tällainen jako tunnetaan splittinä [1] . Jos yhteys katkeaa, pistejoukkojen leikkauspiste muodostaa erottimen ja pisteet, jotka kuuluvat yhteen aligraafiin mutta eivät toiseen, muodostavat kaksi osajoukkoa, joissa on korkeintaan 2 n /3 kärkeä. Päinvastoin, jos annetaan osio kolmeen joukkoon A , S ja B , joka täyttää tasomaisen partitiolauseen ehdot, voidaan muodostaa irtikytkentä, jossa reunat, joiden päät ovat A: ssa, kuuluvat G 1 :een ja reunat, joiden päät ovat B :ssä. kuuluvat G 2 :een , ja loput reunojen reunat (joiden molemmat päät ovat S ) voidaan sisällyttää mihin tahansa joukkoon.

Lauseen lauseessa oleva vakio 2/3 on mielivaltainen ja se voidaan korvata millä tahansa muulla avoimen välin numerolla (1/2,1) muuttamatta lauseen muotoa - voidaan tehdä osio samankokoisiksi osajoukoiksi. saadaan vähemmän identtisistä osioista jakamalla suurempi joukko uudelleen epätasaisiin osiin ja järjestämällä uudelleen tuloksena olevia yhdistettyjä komponentteja [2] .

Esimerkki

Tarkastellaan hilaa , jossa on r riviä ja c saraketta. Tämän hilan kärkien lukumäärä n on yhtä suuri kuin rc . Esimerkiksi kuvassa r  = 5, c  = 8 ja n  = 40. Jos r on pariton, on yksi keskirivi, muuten kaksi riviä on yhtä lähellä keskustaa. Vastaavasti, jos c on pariton, on yksi keskisarake, muuten on kaksi saraketta yhtä kaukana keskustasta. Valitsemalla nämä keskeiset rivit ja sarakkeet S :ksi ja poistamalla S graafista, jaamme graafin kahdeksi pienemmäksi yhdistettyyn osagraafiin A ja B , joissa kummassakin on korkeintaan n /2 kärkeä. Jos r  ≤  c (kuten kuvassa), keskisarakkeen valinta antaa erottimen S , jossa on r  ≤ √ n pistettä, ja vastaavasti, jos c  ≤  r , keskirivin valinta antaa erottimen, jossa on enintään √ n pistettä. Siten missä tahansa hilagraafissa on erotin S , jossa on korkeintaan √ n kärkeä, jonka poistaminen jakaa graafin kahdeksi yhdistetyksi komponentiksi, joiden koko ei ylitä n /2 [3] .

Tasoosion lauseessa sanotaan, että samanlainen osio voidaan rakentaa mille tahansa tasograafille. Mielivaltaisen tasograafin tapaus eroaa hilagraafista siinä, että tässä tapauksessa erottimen koko on O(√ n ), joka voi olla suurempi kuin luku √ n , ja kahden osajoukon A ja B koot (useimmiten lauseen yleinen versio) eivät ylitä 2 n / 3, ei n / 2, kuten hilagraafit. Myös osajoukot A ja B eivät välttämättä muodosta toisiinsa liittyviä osagraafia.

Rakennukset

Bundle

Lipton ja Tarjan [4] suurentavat tiettyä tasograafia lisäämällä tarvittaessa reunoja niin, että siitä tulee maksimaalinen tasograafi (tasoupotuksen jokainen pinta on kolmio). Sitten he tekevät ensin leveyshaun aloittaen mielivaltaisesta kärjestä v ja jakavat kärjet tasoiksi niiden etäisyyden mukaan v :stä . Jos l 1 on mediaani (taso, jolla sen ylä- ja alapuolella olevien pisteiden määrä ei ylitä n /2:ta), silloin täytyy olla tasoja l 0 ja l 2 , jotka ovat O(√ n ) askelta l 1 :n ylä- ja alapuolella sisältää O (√ n ) kärkeä, muuten lähellä tasoa l 1 on enemmän kuin n kärkeä . He osoittivat, että täytyy olla erotin S , joka muodostuu l 0 :n ja l 2 :n liitosta ja graafin G reunojen päistä, jotka ovat näiden kahden tason välissä. Tällä tavalla rakennetun erottimen S koko ei ylitä √8√ n , mikä on noin 2,83√ n . Erottimen ja kahden osiojoukon kärjet löytyvät lineaarisessa ajassa .

Tämä tasomaisen osiointilauseen todiste pätee myös painotetuille tasograafille, kun jokaisella kärjellä on ei-negatiivinen kustannus. Graafi voidaan jakaa kolmeen joukkoon A , S ja B siten, että A ja B maksavat korkeintaan 2/3 täydestä hinnasta ja S :llä on O(√ n ) kärkeä ilman reunoja A :sta B :hen [4] . Analysoimalla tällaisia ​​erottimien rakenteita tarkemmin, Dzhidzhev [2] osoitti, että kokoraja S voidaan pienentää arvoon √6√ n , joka on suunnilleen yhtä suuri kuin 2,45√ n .

Holzer, Schultz Wagner, Prasinos ja Zaroligis [5] ehdottivat yksinkertaistettua versiota lähestymistavasta - he laajentavat kaavion maksimitasograafiksi ja suorittavat leveyshaun samalla tavalla kuin edellä on kuvattu. Sitten kullekin reunalle e , joka ei kuulu hakupuuhun, ne muodostavat silmukan yhdistämällä e puussa oleviin polkuihin, jotka yhdistävät reunan päät. Sitten he käyttävät yhtä näistä silmukoista vertex-erottimena. Vaikka tämä lähestymistapa ei takaa pienen erottimen löytämistä suurihalkaisijaisille tasograafisille kaavioille, heidän kokeensa osoittavat, että tämä lähestymistapa toimii paremmin kuin Lipton-Tarjan- ja Didzhev-fibrointimenetelmät monen tyyppisissä tasokaavioissa.

Yksinkertaiset erotusjaksot

Graafille, joka on jo maksimaalinen tasomainen, voidaan näyttää tiukka rakenne yksinkertaisesta sykli-erottimesta , pienipituinen sykli, jonka sisä- ja ulkoosissa (tietylle tasomaiselle upotukselle) on korkeintaan 2n /3 kärkeä. Miller [6] todisti tämän (erottimella, jonka koko on √8√ n ) käyttämällä Lipton-Tarjan-tekniikkaa leveysensimmäisen haun modifioitua versiota varten, jossa tasot muodostavat yksinkertaisia ​​syklejä.

Alon, Seymour ja Thomas [7] osoittivat yksinkertaisen syklierottimen olemassaolon suoremmalla tavalla – he tarkastelivat sykliä C , joissa oli korkeintaan √8√ n kärkeä ja joissa on enintään 2 n /3 kärkeä C :n ulkopuolella. osio mahdollisimman moneen lähempään osaan silmukan sisällä ja ulkopuolella. He osoittivat, että kaikissa näissä olosuhteissa C :n tulisi olla erotin. Muussa tapauksessa C :n sisällä olevien etäisyyksien tulee olla yhtä suuria kuin C :n ympäröimän levyn etäisyydet (lyhin polku levyn sisäpuolen läpi muodostaisi osan parasta syklin rajaa). Lisäksi syklin C pituuden tulee olla täsmälleen √8√ n , muuten sitä voidaan parantaa korvaamalla toinen kolmion reunasta kahdella muulla sivulla. Jos syklin C kärjet on numeroitu (myötäpäivään) 1 - √8√ n ja kärki i vastaa kärkeä √8√ n − i + 1 , niin nämä kärkiparit voidaan yhdistää ei-leikkautuvilla poluilla sisällä levy (yhden Mengerin tasograafien lauseen muodoista ). Kuitenkin näiden polkujen kokonaispituus ylittäisi n , mikä on ristiriita. Muutaman lisälaskelman jälkeen he osoittivat samanlaisilla menetelmillä, että on olemassa yksinkertainen syklierotin, jonka koko on enintään (3/√2)√ n , joka on suunnilleen yhtä suuri kuin 2,12√ n .

Jijev ja Venkatesan [8] paransivat myöhemmin vakion yksinkertaisessa jaksoerotuslauseessa arvoon 1,97√ n . Heidän menetelmänsä mahdollistaa myös yksinkertaisten syklierottimien etsimisen graafeille, joilla on ei-negatiiviset kärkipainot ja joiden erottimen koko ei ylitä 2√ n . Menetelmän avulla voit kuitenkin luoda pienempiä erottimia, koska osion osien kokoero on suurempi. 2-liitetyssä ei-maksimaalisessa tasograafissa on yksinkertainen erotinsykli, jonka koko on verrannollinen kasvojen pituusvektorin euklidiseen normiin ja joka löytyy lähes lineaarisessa ajassa [9] .

Kiertoerottimet

Koebe-Andreev-Thurstonin ympyräpakkauslauseen mukaan mikä tahansa tasograafi voidaan esittää ympyröiden pakkauksena tasossa, jossa on ei-leikkaavat sisäalueet, niin että graafin kaksi kärkeä ovat vierekkäin silloin ja vain, jos vastaavat ympyrät koskettavat . Kuten Miller, Teng, Thurston ja Wawasis [10] osoittivat , tällaisissa pakkauksissa on ympyrä, jota kosketetaan tai sen sisällä, enintään 3 n /4 kiekkoa, enintään 3 n /4 kiekkoa on ympyrän ulkopuolella, tai kosketa sitä, ja joka leikkaa O(√ n ) levyä.

Tämän todistamiseksi Miller ym. käyttivät stereografista projektiota kartoittaakseen pakkauksen yhden 3D-pallon pinnalle. Projektion huolellisella valinnalla pallon keskipiste voidaan sijoittaa pinnan kiekkojen keskipisteiden keskipisteeseen siten, että mikä tahansa pallon keskustan läpi kulkeva taso jakaa pallon kahdeksi puolipalloksi, joista kumpikin joista sisältää tai leikkaa enintään 3 n /4 levyä. Jos keskipisteen läpi kulkeva taso valitaan satunnaisesti ja tasaisesti, levy leikataan todennäköisyydellä, joka on verrannollinen säteeseen. Siten odotettu ristikkäisten levyjen lukumäärä on verrannollinen levyjen säteiden summaan. Neliön säteiden summa on kuitenkin verrannollinen levyjen kokonaispinta-alaan, joka ei ylitä yksikköpallon pinta-alaa, vakio. Argumentit, joissa käytetään Jensenin epäyhtälöä , osoittavat, että jos n ei-negatiivisen luvun neliösumma on vakion rajoittama, itse lukujen summa ei ylitä arvoa O(√ n ). Näin ollen odotus levyjen leikkauskohtien lukumäärästä satunnaisen tason suhteen on O(√ n ) ja on olemassa taso, joka leikkaa enintään tämän määrän levyjä. Tämä taso leikkaa pallon suuressa ympyrässä , jonka projektio takaisin tasoon antaa halutut ominaisuudet. Tämän ympyrän leikkaamat O(√ n ) -kiekot vastaavat tasograafierottimen huippuja, joka erottaa kärjet, joiden kiekot ovat ympyrän sisällä, niistä pisteistä, joiden kiekot ovat ympyrän ulkopuolella, ja jokaisessa näistä osajoukoista on enintään 3 n /4 kärkeä [10] [11] .

Tämä menetelmä johtaa probabilistiseen algoritmiin , joka löytää erottimen lineaarisessa ajassa [10] , ja vähemmän käytännölliseen deterministiseen algoritmiin , jolla on sama lineaarinen aikaraja [12] . Analysoimalla tämä algoritmi huolellisesti ja käyttämällä ympyröiden pakkaustiheyden tunnettuja rajoja voidaan osoittaa, että on mahdollista löytää erottimia, jotka eivät ylitä kokoa.

[13]

Vaikka tämä parannettu erottimen koko johtaa graafin epätasa-arvoisempaan osiointiin, Shpilman ja Teng [14] väittävät, että menetelmä antaa paremman kertoimen sisäkkäisen osioinnin ajoajassa verrattuna Alonin, Seymourin ja Thomasin erottimeen [1] . Erottimien kokoa voidaan käytännössä parantaa käyttämällä satunnaisten leikkaustasojen epätasaista jakautumista [15] .

Stereografinen projektio Millerin ym.:n argumentissa voidaan välttää ottamalla huomioon pienin ympyrä, joka sisältää vakion levykeskipisteiden murto-osan, ja laajentamalla sitten väliltä tasaisesti valitulla määrällä [1,2]. On helppo osoittaa, kuten Millerin kohdalla, että tällaisen ympyrän ylittämät kiekot muodostavat säännöllisen erottimen, jolloin matemaattinen odotus leikkauspisteiden lukumäärästä antaa oikean tuloksen. Totta, tuloksena saadut vakiot ovat jonkin verran huonompia [16] .

Spektrin osiointi

Spektriklusterointimenetelmiä , joissa graafin kärkipisteet ryhmitellään graafista saatujen matriisien ominaisarvokoordinaattien mukaan, on pitkään käytetty heuristisina menetelminä graafisen osiointiongelmien ratkaisemisessa epätasoisille graafille [17] [18] . Kuten Shpilman ja Teng [19] ovat osoittaneet , spektriklusterointia voidaan käyttää vaihtoehtoisesti myös tasoosiolauseen heikentyneen muodon osoittamiseen, jota sovelletaan tasograafiin, joilla on rajattu kärkiaste. Heidän menetelmässään tietyn tasograafin kärjet lajitellaan graafin Kirchhoff-matriisin ominaisvektorien toisen koordinaatin mukaan ja tämä järjestys jaetaan kohdassa, joka minimoi poistettujen reunojen määrän suhteen osion pienemmän osan kärjet. Kuten he osoittivat, millä tahansa tasograafilla, jolla on rajoitettu kärkiaste, on osio, jossa tämä suhde on O(1/√ n ). Vaikka tämä osio ei ehkä ole tasapainotettu, kahdesta suuremman osion toistaminen ja kussakin iteraatiossa saatujen leikkausten yhdistäminen johtaa lopulta tasapainotettuun ositukseen, jossa on O(√ n ) reunat. Näiden reunojen päätypisteet muodostavat koon (√ n ) erottimen.

Rib-erottimet

Tasomaisen hajottelulauseen muunnelma puhuu reunaerottimista , pieniä reunajoukkoja, jotka muodostavat leikkauksen graafin kärkien kahden osajoukon A ja B välille. Kahden joukon A ja B koon tulee olla enintään vakio murto-osa graafin kärkien lukumäärästä n (yleensä molempien joukkojen ei tarvitse olla suurempia kuin 2 n /3), ja jokainen graafin kärkipiste kuuluu vain A: lle tai B :lle . Erotin koostuu reunoista, joiden toinen pää on kohdassa A ja toinen pää kohdassa B. Reunaerottimen kokorajat riippuvat sekä graafin kärkien asteesta että pisteiden lukumäärästä graafissa - tasograafit, joissa yhden kärjen aste on n  − 1, jossa pyörät ja tähdet putoavat , ei ole erotinta alilineaarilla. reunojen määrä, koska minkä tahansa reunaerottimen tulee sisältää kaikki reunat, jotka yhdistävät korkean asteen kärjen leikkauksen toisella puolella oleviin pisteisiin. Jokaisella tasograafilla, jonka maksimiaste on Δ, on kuitenkin reunaerotin, jonka koko on O(√(Δ n )) [20]

Yksinkertainen syklierotin tasograafin kaksoisgraafissa muodostaa alkuperäisen graafin reunaerottimen [6] [9] . Gacitin ja Millerin [9] yksinkertaisen syklierotuslauseen soveltaminen tietyn tasograafin kaksoisgraafiin vahvistaa O(√(Δ n )) -estimaattia reunaerottimen koolle, koska se osoittaa, että jokaisella tasograafilla on reunaerotin. jonka koko on verrannollinen graafin vektoripisteen asteiden euklidiseen normiin.

Papadimitrou ja Sideri [21] kuvasivat polynomiaikaalgoritmin reunaerottimen löytämiseksi, joka jakaa graafin G kahdeksi samankokoiseksi osagraafiksi, jos G on generoitu aligraafi hilagraafista ilman reikiä tai vakiomäärällä reikiä. He kuitenkin olettivat, että ongelma on NP-täydellinen mielivaltaisten tasokaavioiden tapauksessa, ja osoittivat, että ongelman monimutkaisuus hilakaavioissa, joissa on mielivaltainen määrä reikiä, on sama kuin mielivaltaisissa tasokaavioissa.

Alarajat

Hilakaaviossa √ n  × √ n joukko S , joka sisältää s  < √ n pistettä, voi ympäröidä enintään s ( s  − 1)/2 hilan pisteen osajoukon, ja maksimi saavutetaan asettamalla S diagonaalille. viiva lähempänä hilan kulmaa. Siten vähintään n /3 pistettä ruudukosta erottavan erottimen muodostamiseksi s :n koon tulee olla vähintään √(2 n /3), mikä on noin 0,82√ n .

On olemassa tasograafisia kaavioita, joissa on n pistettä (satunnaisen suurille n:n arvoille ) siten, että jokaiselle erottimelle S , joka jakaa jäljellä olevan graafin enintään 2n /3 kärkeä sisältäviksi alagraafiksi, S :llä on vähintään √(4π√3)√ n kärjet, noin 1,56√ n [2] . Rakenteessa käytetään pallon likiarvoa kuperalla monitahoisella korvaamalla polyhedronin jokainen pinta kolmiomaisella verkolla. Isoperimetristä lausetta sovelletaan sitten pallon pintaan.

Erotinhierarkiat

Erottimet voidaan yhdistää tasomaiseen graafierottimen hierarkiaan , rekursiiviseen jaotteluun pienempiin kaavioihin. Erotinhierarkia voidaan esittää binääripuuna , jossa juuri edustaa itse graafia, ja juuren kaksi lapsisolmua ovat rekursiivisesti muodostetun erotinhierarkian osajoukkojen A ja B luotujen aligraafien juuria.

Tämän tyyppisten erottimien hierarkia muodostaa perustan tietyn graafin puuhajottamiselle, jossa puun solmuun liittyvä kärkijoukko on erottimien liitto polulla tästä solmusta puun juureen . Koska kaavioiden koot pienenevät vakiokertoimella jokaisella puun tasolla, myös erottimien koon ylärajat pienenevät vakiokertoimella kullakin tasolla, joten erottimien koot näillä poluilla summautuvat eksponentiaalisesti . O(√ n ). Toisin sanoen näin muodostetun erottimen leveys on O(√ n ) ja tätä voidaan käyttää osoittamaan, että millä tahansa tasograafilla on puun leveys O(√ n ).

Erotinhierarkian rakentaminen suoraan kulkemalla binaaripuun läpi ylhäältä alas ja käyttämällä lineaariaikaista algoritmia tasomaisen erottimen löytämiseksi jokaiselle luodulle aligraafille, joka liittyy kuhunkin binääripuun solmuun, vie kokonaisajan O( n  log  n ) . On kuitenkin mahdollista rakentaa koko erotinhierarkia lineaarisessa ajassa, jos käytämme Lipton-Tarjan-leveyskuitumenetelmää ja käytämme sopivia tietorakenteita kunkin osiointivaiheen toteuttamiseen alilineaarisessa ajassa [22] .

Jos muodostamme hierarkioita, jotka eivät perustu erottimiin, vaan disconnecteihin, joissa kahdesta lapsipisteestä tulee juuria erotinhierarkioiden rekursiiviseen rakentamiseen tietyn graafin erotuksen kahdelle osagraafille G 1 ja G 2 , niin täydellinen rakenne muodostaa hajotuksen . kaavion oksiksi , ei puun hajotukseksi. Tämän jaottelun minkä tahansa jaon leveyttä rajoittaa jälleen erottimien kokojen summa polulla mistä tahansa solmusta hierarkian juureen, joten kaikilla näin saaduilla hajotuksilla on leveys O(√ n ) ja mikä tahansa tasograafi . on haaran leveys O(√ n ). Vaikka monet muut liittyvät graafin osiointiongelmat ovat NP-täydellisiä jopa tasograafien kohdalla, on mahdollista löytää tasograafin hajoaminen haaroihin, joiden leveys on pienin polynomiajassa [23] .

Soveltamalla Alonin, Seymourin ja Thomasin [7] menetelmiä suoremmin graafin haarojen rakentamiseen, Fomin ja Tilikos [24] osoittivat, että minkä tahansa tasograafin haarautumisleveys ei ylitä 2,12√ n , eli samalla tavalla. vakio kuin Alon Alonin, Seymourin ja Thomasin osiointilauseessa yksinkertaisilla jaksoerottimilla. Koska minkä tahansa graafin puun leveys on enintään 3/2 haaran leveydestä, tämä osoittaa myös, että tasograafien puun leveys on enintään 3,18√ n .

Muut kaavioluokat

Joissakin harvoissa graafisissa kaavioissa ei ole alilineaarisia kokoerottimia – laajentimessa pisteiden vakio-osuuden poistaminen jättää yhden yhdistetyn komponentin [4] [25] .

Ehkä varhaisin osiointilause on Jordanin tulos [26] , jonka mukaan mikä tahansa puu voidaan jakaa kahdeksi alipuuksi, joissa kummassakin on enintään n /2 kärkeä, poistamalla yksi kärki [10] . Erityisesti maksimikomponentin koon minimoivalla kärjellä on tämä ominaisuus. Soveltamalla samaa tekniikkaa mielivaltaisen graafin puuhajottamiseen voidaan osoittaa, että missä tahansa graafissa on erotin, jonka koko ei ylitä sen puun leveyttä .

Jos graafi G ei ole tasomainen, vaan se voidaan upottaa suvun g pintaan , niin siinä on erotin, jossa on O(( gn ) 1/2 ) -pisteet. Gilbert, Hutchinson ja Tarjan [27] osoittivat tämän käyttämällä lähestymistapaa, joka on lähellä Liptonin ja Tarjanin [4] lähestymistapaa . He ryhmittelevät graafin kärjet leveysensimmäisten hakutasojen mukaan ja löytävät kaksi tasoa, joiden poistaminen jättää enintään yhden suuren komponentin, joka koostuu pienestä määrästä tasoja. Tämä jäljellä oleva komponentti voidaan tehdä tasomaiseksi poistamalla useita graafin sukuun verrannollisia leveysensimmäisiä hakupolkuja, minkä jälkeen Lipton-Tarjan-menetelmää voidaan soveltaa jäljellä olevaan tasograafiin. Tulos saadaan tasapainottamalla huolellisesti poistetun kahden tason koko ja tasojen lukumäärä niiden välillä. Kun kaavio on upotettu, sen erotin löytyy lineaarisesta ajasta . Suvun g kaavioissa on erottimet, joiden koko on O(( g Δ n ) 1/2 ) [28] .

Rajatun suvun kaaviot muodostavat esimerkin graafiperheestä, joka on suljettu alaikäisten ottamiseksi , ja osiolauseet pätevät mielivaltaisiin graafiperheisiin, jotka on suljettu alaikäisten ottamiseen. Erityisesti, jos graafiperheellä on kielletty molli , jossa on h - pisteitä, niin siinä on erotin, jossa on O( h √ n ) -pisteitä, ja tällainen erotin löytyy O( n 1 + ε ) -ajassa mille tahansa ε:lle > 0 [29]

Millerin, Tengin, Thurstonin ja Vavasisin [10] erotinsyklien menetelmä on yleistetty minkä tahansa d - ulotteisten pallojen järjestelmän leikkauskaavioille, joilla on ominaisuus, että minkä tahansa pinnan pisteen peittävät pallot korkeintaan jollain vakiolla. luku k kertaa, graafisille k - lähimmät naapurit dimensiossa d [10] , ja graafisille, jotka syntyvät elementtiruudukoista [30] . Tällä tavalla muodostetut pallomaiset erottimet jakavat syötegraafin aligraafiksi, joissa on enintään n ( d + 1)/( d + 2) kärkeä. K -kertaisten päällekkäisten pallojen ja k-lähimpien naapureiden kuvaajien erottimien koko on O( k 1 / d n 1 − 1/ d ) [10] .

Sovellukset

Divide and Conquer -algoritmit

Erotinosioita voidaan käyttää tehokkaiden " Dive and Conquer " -algoritmien rakentamiseen tasograafien ongelmien ratkaisemiseksi. Esimerkki ongelmasta, joka voidaan ratkaista tällä lähestymistavalla, on lyhimmän syklin löytäminen painotetusta tasosuuntaisesta graafista. Voit tehdä sen näin:

Kahden rekursiivisen kutsun A: lle ja B :lle aikaa tässä algoritmissa hallitsee Dijkstran algoritmin O(√ n ) -ajoaika, joten tämä algoritmi löytää lyhimmän syklin O( n 3/2  log  n ) -ajassa.

Wolf-Nielsen [31] antoi nopeamman algoritmin samalle ongelmalle lyhimmän syklin löytämiseksi ajassa O( n  log 3 n ) . Hänen algoritminsa käyttää samaa erottimiin perustuvaa jaa ja hallitse -rakennetta, mutta käyttää yksinkertaisia ​​jaksoerottimia mielivaltaisten erottimien sijasta, jolloin joukon S kärjet kuuluvat samaan pintaan (sisäiselle graafille ja ulommalle graafille suhteessa erottimeen). Sitten se korvaa Dijkstran algoritmin O(√ n ) yksittäiset kutsut kehittyneemmillä algoritmeilla lyhimpien polkujen löytämiseksi kaikista tasograafin yhdellä pinnalla olevista pisteistä ja etäisyyksien yhdistämisestä kahdesta osagraafista. Painotetuille mutta suuntaamattomille tasograafisille lyhyin jakso vastaa kaksoisgraafin pienintä leikkausta ja se löytyy O( n  log log  n ) -ajasta [32] ja lyhin sykli painotetussa suuntaamattomassa tasograafissa (sen ympärysmitta ) löytyy ajasta O( n ) [33] . (Kuitenkin painottamattomien graafien nopeampi algoritmi ei perustu osiolauseeseen.)

Frederickson ehdotti vuonna 1986 toista nopeaa algoritmia lyhimmälle polulle yhdestä lähteestä käyttämällä tasograafien osiointilausetta [34] . Algoritmi on parannus Dijkstran iteratiiviseen hakuun huolellisesti valitulla kärkien osajoukolla. Tämä versio toimii O( n √(log n ))-ajassa graafissa, jossa on n kärkeä. Erottimia käytetään etsimään graafin jako, toisin sanoen sen osio kahdeksi tai useammaksi osajoukoksi, joita kutsutaan alueiksi. Solmun sanotaan kuuluvan alueelle, jos jokin alueen reuna osuu solmuun. Solmua, joka sisältyy useampaan kuin yhteen alueeseen, kutsutaan sen sisältävien alueiden rajasolmuksi. Menetelmässä käytetään käsitettä graafin r -jaosta, jossa on n solmua, mikä vastaa graafin jakamista O( n / r )-alueisiin, joista jokainen sisältää O( r )-solmua, mukaan lukien O(√ r ) -rajasolmut . . Frederickson osoitti, että r - jako voidaan löytää O( n log n ) -ajassa käyttämällä rekursiivisesti osiolausetta.

Pääpiirteet ongelman ratkaisun algoritmista.

1. Alustava valmistelu . Jaamme graafin huolellisesti valituiksi kärkiosuuksiksi ja löydämme lyhyimmät polut kaikkien näiden osajoukkojen kärkiparien välillä, joissa polun välipisteet eivät kuulu osajoukkoon. Tässä vaiheessa on tarpeen muuntaa tasograafi   G 0 muotoon G , jolla ei ole pisteitä, joiden aste on suurempi kuin 3. Eulerin kaavasta päätepisteiden lukumäärä tuloksena olevassa graafissa on n ≤ 6 n 0  −12, missä n 0   on graafin G 0 pisteiden lukumäärä  . Tämä vaihe tarjoaa myös seuraavat sopivan r -jaon ominaisuudet. Tasograafin sopiva r -jako on sellainen r - jako, että

2. Hae

Henzinger ym. laajensivat Fredericksonin r -jakotekniikkaa algoritmille lyhimmän polun löytämiseksi yhdestä lähteestä tasomaisissa graafisissa ei-negatiivisilla reunanpituuksilla ja ehdottivat lineaarista aikaalgoritmia [35] . Heidän menetelmänsä yleistää Fredrekson-osion käsitteen graafille, niin että nyt graafin ( r , s )-osio, jossa on n solmua, muuttuu osioksi O( n / r )-alueisiin, joista jokainen sisältää r {O(1) }   solmua ja enintään s rajasolmua. Jos ( r , s )-osio toistetaan peräkkäin osioiden pienempiin alueisiin, tätä kutsutaan rekursiiviseksi osioksi. Algoritmi käyttää suunnilleen log* n jakotasoa. Rekursiivista jakoa edustaa juurtunut puu, jonka lehdet on merkitty graafin G eri reunoilla . Puun juuri edustaa aluetta, joka koostuu koko graafista G , juuren lapset edustavat osa-alueita, joihin alue on jaettu. Jokainen lehti edustaa täsmälleen yhtä reunaa.

Sisäkkäinen dissektio  on erottimeen perustuva muunnelma Gaussin eliminointimenetelmän jakaa ja hallitse -lähestymistavan, jolla ratkaistaan ​​harvoja symmetrisiä lineaaristen algebrallisten yhtälöiden järjestelmiä, joissa on tasograafirakenne, kuten elementtimenetelmässä . Menetelmä käyttää erottimen hakua yhtälön kuvauskaaviolle, rekursiivisesti poissulkemalla muuttujat kahdessa toisistaan ​​erottimella erotetussa alitehtävässä ja jättäen sitten erottimen muuttujat pois [36] . Tämän menetelmän käyttöaste (syntyvän Cholesky-laajennuksen nollasta poikkeavien kertoimien lukumäärämatriisille) on O( n  log  n ) [37] [38] , mikä mahdollistaa tämän menetelmän kilpailevan iteratiivisten menetelmien kanssa samoista ongelmista [ 36] .

Klein, Moses ja Weimann [39] ehdottivat O( n log 2  n ) lineaarista muistialgoritmia lyhimpien etäisyyksien löytämiseksi s :stä suunnatun tasomaisen graafin positiivisella ja negatiivisella kaarenpituudella, joka ei sisällä negatiivisia syklejä, kaikille solmuille. Heidän algoritminsa käyttää tasomaisia ​​graafierottimia löytääkseen Jordan-käyrän C , joka kulkee O(√ n ) -solmun läpi (mutta ei kaarien läpi) siten, että n /3 - 2 n /3 solmua on (suljetun käyrän rajoittama alue) sisällä. C . Solmut, joiden kautta käyrä C kulkee, ovat rajasolmuja . Alkuperäinen graafi G on jaettu kahteen osagraafiin G 0   ja G 1 , mikä katkaisee tasomaisen upotuksen käyrää C pitkin ja monistaa rajasolmut. Kun i =0 ja 1, G i :   ssä rajasolmut sijaitsevat Fi:n toisella puolella  .

Alla on yleiskatsaus tästä lähestymistavasta.

Tärkeä osa tätä algoritmia on Price- ja Reduced Length -funktioiden käyttö. Suunnatun graafin G kaarenpituuksilla ι(•) kustannusfunktio on funktio φ graafin G solmuista reaalilukuihin . Kaaren uv pienennetty pituus φ:n suhteen on ιφ( uv )=ι( uv ) + φ( u ) − φ( v ). Sallittu kustannusfunktio on funktio, joka antaa ei-negatiivisia pienennettyjä pituuksia G :n kaikilla kaarilla . On hyödyllistä muuntaa lyhimmän polun ongelma, jolla on sekä positiivinen että negatiivinen kaaren pituus, ongelmaksi, jolla on ei-negatiiviset pituudet, mikä mahdollistaa Dijkstran algoritmin käytön.

Erottimeen perustuvaa jakaa ja hallitse -paradigmaa käytetään myös tietorakenteiden kehittämiseen dynaamisille graafialgoritmeille [40] [41] ja pistelokalisoinnille [42] , polygonin kolmiomittausalgoritmeille [ 22] , lyhimmille poluille [ 43] [44] , lähimpien naapurigraafien muodostamiseen [45] ja approksimaatioalgoritmeihin suurimman riippumattoman joukon löytämiseksi tasograafista [42] .

Tarkka ratkaisu NP-kovaan optimointiongelmiin

Käytettäessä dynaamista ohjelmointia puun tai haaroittamiseen tasograafille , monet NP-kovien optimointiongelmien luokat voidaan ratkaista ajassa eksponentiaalisesti riippuen √ n tai √ n  log  n :stä . Tällaisia ​​rajoja tunnetaan esimerkiksi maksimiriippumattomien joukkojen , Steiner-puiden , Hamiltonin syklien etsimiseen ja matkustavan myyjän ongelman ratkaisemiseen tasograafista [46] . Samanlaisia ​​menetelmiä, joissa käytetään osiointilauseita geometrisille kuvaajille, voidaan käyttää ratkaisemaan euklidisen matkustavan myyjän ongelma ja rakentamaan Steiner-puu samoissa aikarajoissa [47] .

Parametrisoiduissa -ongelmissa, jotka mahdollistavat parametrisen pienentämisen , joka säilyttää tasomaisuuden ja pienentää syötetiedoston ytimeen, jonka koko riippuu lineaarisesti parametrista, tätä lähestymistapaa voidaan käyttää kiinteäparametrisesti ratkaistavissa olevien -algoritmien rakentamiseen, joiden suoritusaika riippuu polynomiaalisesti syötegraafin koosta ja eksponentiaalisesti √ k :ssa , missä k  on algoritmin parametri. Esimerkiksi tämänkaltaiset ajonaikaiset rajat tunnetaan k -koon pistepeitteiden ja hallitsevien joukkojen löytämisestä [48] [49] .

Approksimaatioalgoritmit

Lipton ja Tarjan [42] havaitsivat, että osiolausetta voidaan käyttää polynomiajan approksimaatiomenetelmien johtamiseen tasomaisille graafisille NP-koville optimointiongelmille, kuten suurimman riippumattoman joukon löytämiseen . Erityisesti katkaisemalla erotinhierarkia sopivasta paikasta löytyy erotin, jonka koko on O( n /√log  n ), jonka poistaminen jakaa graafin koon c  log  n aligraafiksi mille tahansa vakiolle c . Neljän värin lauseen mukaan on olemassa riippumaton joukko, jonka koko on vähintään n /4, joten poistetut solmut muodostavat pienen osan suurimmasta riippumattomasta joukosta ja suurimmat riippumattomat joukot jäljellä olevissa aligraafissa löytyvät itsenäisesti aika eksponentiaalisesti riippuvaisesti. niiden koon mukaan. Yhdistämällä tämä lähestymistapa lineaariaikaisiin menetelmiin erotinhierarkian muodostamiseksi [22] taulukkohaulla itsenäisten joukkojen etsintäajan lyhentämiseksi isomorfisissa aligraafissa, voidaan rakentaa riippumattomia joukkoja, jotka poikkeavat optimaalisista kertoimella 1 − O(1/√log  n ) lineaarisessa ajassa. Kuitenkin taattua tehokkuutta vielä lähempänä 1:tä kuin tämä tekijä Bakerin ( Baker 1994 ) myöhempi lähestymistapa (perustuu puun hajoamiseen tasomaisten erottimien sijaan) tarjoaa paremman kompromissin ajan ja likimääräisen laadun välillä.

Samanlaisia ​​erottimien rakentamiseen perustuvia approksimaatiomalleja käytetään muiden vaikeiden ongelmien, kuten vertex cover -ongelman , approksimoimiseen [50] [51] . Arora, Grigni, Karger, Klein ja Voloshin [52] käyttivät erottimia eri tavalla arvioidakseen matkustavan myyjän ongelmaa lyhimmän polun metriikassa painotetuissa tasokaavioissa. Niiden algoritmi käyttää dynaamista ohjelmointia löytääkseen lyhimmän polun, joka jokaisella erotinhierarkian tasolla ylittää erottimen rajoitetun määrän kertoja. Ne osoittivat, että risteysten rajan kasvaessa tällä tavalla rakennettujen reittien pituus on suunnilleen optimaalista reittiä.

Kuvaajan pakkaus

Erottimia käytetään osana tietojen pakkausalgoritmeja esittämään tasomaisia ​​graafisia ja muita erotettavissa olevia kuvaajia käyttäen pientä määrää bittejä. Näiden algoritmien pääperiaate on valita luku k ja jakaa annettu tasograafi erottimien avulla uudelleen O( n / k ) aligraafiksi, joiden koko on enintään k , ja erottimissa on O( n /√ k ) -pisteitä. Sopivalla k :n valinnalla (maksimi verrannollinen n : n logaritmiin ) k -kärkisten ei- isomorfisten tasograafien määrä on huomattavasti pienempi kuin hajotuksessa olevien aligraafien määrä, joten graafit voidaan pakata rakentamalla taulukko kaikista mahdollisista ei-isomorfiset alagraafit ja edustavat kutakin alagraafia hajotuksessa taulukon indeksillä. Loput erottimen kärkien muodostamasta graafista voidaan esittää eksplisiittisesti tai saman tietorakenteen rekursiivisella versiolla. Tällä menetelmällä tasograafit ja rajoitetummat tasograafien perheet voidaan koodata käyttämällä optimaalista bittimäärää ( informaatioteorian kannalta ) - jos graafiperheessä on graafia P n , joissa on n kärkeä, niin yksittäinen graafi perhe voidaan esittää käyttämällä vain (1 + o( n ))log 2 P n bittiä [53] . Voidaan myös rakentaa tämän tyyppisiä näkymiä, joissa voi tarkistaa kärkien viereisyyden, määrittää kärjen asteen ja listata kärjen naapureita vakioajassa (kyselyä kohden) laajentamalla aligraafitaulukkoa lisätiedoilla, jotka vastaavat kyselyt [54] [55] .

Yleiskuvaajat

Universaali graafi graafiperheelle F  on graafi, joka sisältää minkä tahansa perheen F elementin aligraafina. Erottimilla voidaan osoittaa, että n-pisteisten tasograafien avulla on universaali graafi, jossa on n kärkeä ja O( n 3/2 ) reunaa [56] .

Konstruktiossa käytetään vahvempaa osiolauseen muotoa, jossa osion kolmen kärkien osajoukon koko ei riipu graafin rakenteesta - on luku c , jonka arvo on vakiotekijä, joka on suurempi kuin √ n , niin että minkä tahansa tasograafin, jossa on n pistettä, kärjet voidaan jakaa osajoukkoihin A , S ja B ilman reunoja A :sta B :hen ja joiden mitat ovat | S | =  c , | A | = | b | = ( n  −  c )/2. Tämä voidaan osoittaa soveltamalla osiointilauseen tavallista muotoa toistuvasti tuloksena oleviin graafin osioihin, kunnes kaikki osion komponentit on koottu kahteen osajoukkoon, joista kukin on kooltaan alle n /2 kärkeä, ja siirtämällä sitten kärjet näistä osajoukoista erottimeen, kunnes sillä ei ole annettua kokoa.

Nyt tällä lauseella voidaan saada erotinhierarkia tasomaiselle graafille , jossa on n kärkeä, mikä on jälleen riippumaton graafin rakenteesta - tästä hierarkiasta saatu puuhajotelma on O(√ n ) leveä ja sitä voidaan käyttää mihin tahansa tasokaavio. Tämän puuhajotelman kaikkien kärkiparien joukko, jossa kumpikin kahdesta pisteestä kuuluu puujaon yhteiseen solmuun, muodostaa triviaalisen täydellisen graafin , jossa on O( n 3/2 ) pistettä, joka sisältää minkä tahansa tasograafin, jossa on n kärkeä aligraafina. Samankaltainen konstruktio osoittaa, että tasograafisilla rajatuilla asteilla on universaaleja graafia, joissa on O( n  log  n ) -reunat, joissa O -merkinnässä piilotettu vakio riippuu graafin asteesta. Kaikissa tasograafien (tai jopa rajattoman asteisen puiden) universaalissa graafissa on oltava Ω( n  log  n ) reunat, mutta jää epäselväksi, onko tämä alaraja vai O( n 3/2 ) yläraja terävä yleisgrafeille mielivaltaiset tasograafit [56] .

Katso myös

Muistiinpanot

  1. ↑ 1 2 Alon, Seymour, Thomas, 1990 .
  2. ↑ 1 2 3 Djidjev, 1982 .
  3. ↑ George, 1973 . Sen sijaan, että George käyttäisi rivejä ja sarakkeita erottimena kaavion jakamiseen, George käyttää niiden yhdistämistä ja jakaa kaavion neljään osaan.
  4. ↑ 1 2 3 4 Lipton, Tarjan, 1979 .
  5. ↑ Holzer, Schulz, Wagner, Prasinos, Zaroliagis, 2009 .
  6. ↑ 12 Miller , 1986 .
  7. ↑ 1 2 Alon, Seymour, Thomas, 1994 .
  8. ↑ Djidjev, Venkatesan, 1997 .
  9. ↑ 1 2 3 Gazit, Miller, 1990 .
  10. ↑ 1 2 3 4 5 6 7 Miller, Teng, Thurston, Vavasis, 1997 .
  11. ↑ Pach, Agarwal, 1995 .
  12. ↑ Eppstein, Miller, Teng, 1995 .
  13. ↑ Spielman, Teng (1996 ).
  14. ↑ Spielman, Teng, 1996 .
  15. ↑ Gremban, Miller, Teng, 1997 .
  16. ↑ Har-Peled, 2011 .
  17. ↑ Donath, Hoffman, 1972 .
  18. ↑ Fiedler, 1973 .
  19. ↑ Spielman, Teng, 2007 .
  20. ↑ Miller ( Miller 1986 ) todisti tämän tuloksen 2-liitetyille tasokaavioille, kun taas Diks, Djidjev, Sýkora, Vrt'o (1993 ) laajensi tuloksen kaikkiin tasograafisiin.
  21. ↑ Papadimitriou, Sideri, 1996 .
  22. ↑ 1 2 3 Goodrich, 1995 .
  23. ↑ Seymour, Thomas, 1994 .
  24. ↑ Fomin, Thilikos, 2006a .
  25. ↑ Erdős, Graham, Szemerédi, 1976 .
  26. ↑ Jordania, 1869 .
  27. ↑ Gilbert, Hutchinson, Tarjan, 1984 .
  28. ↑ Sýkora, Vrt'o, 1993 .
  29. ↑ Kawarabayashi, Reed, 2010 . Aikaisempi työ vähän suljettujen perheiden erottajista - Alon, Seymour, Thomas, 1990 ; Plotkin, Rao, Smith, 1994 ; Reed, puu, 2009 .
  30. ↑ Miller, Teng, Thurston, Vavasis, 1998 .
  31. ↑ Wulff-Nilsen, 2009 .
  32. ↑ Łącki, Sankowski, 2011 .
  33. ↑ Chang, Lu, 2011 .
  34. ↑ Frederickson, 1987 , s. 1004-1022.
  35. ↑ Henzinger, Klein, Rao, Subramanian, 1997 .
  36. ↑ 12. George, 1973 .
  37. ↑ Lipton, Rose, Tarjan, 1979 .
  38. ↑ Gilbert, Tarjan, 1986 .
  39. ↑ Klein, Mozes, Weimann, 2009 .
  40. ↑ Eppstein, Galil, Italiano, Spencer, 1996 .
  41. ↑ Eppstein, Galil, Italiano, Spencer, 1998 .
  42. ↑ 1 2 3 Lipton, Tarjan, 1980 .
  43. ↑ Klein, Rao, Rauch, Subramanian, 1994 .
  44. ↑ Tazari, Müller-Hannemann, 2009 .
  45. ↑ Frieze, Miller, Teng, 1992 .
  46. ↑ Bern, 1990 ; Deĭneko, Klinz, Woeginger, 2006 ; Dorn, Penninkx, Bodlaender, Fomin, 2005 ; Lipton, Tarjan, 1980 .
  47. ↑ Smith, Wormald, 1998 .
  48. ↑ Alber, Fernau, Niedermeier, 2003 .
  49. ↑ Fomin, Thilikos, 2006b .
  50. ↑ Bar-Yehuda, Even, 1982 .
  51. ↑ Chiba, Nishizeki, Saito, 1981 .
  52. ↑ Arora, Grigni, Karger, Klein, Woloszyn, 1998 .
  53. ↑ Hän, Kao, Lu, 2000 .
  54. ↑ Blandford, Blelloch, Kash, 2003 .
  55. ↑ Blelloch, Farzan, 2010 .
  56. ↑ 1 2 Babai, Chung, Erdős, Graham, Spencer, 1982 ; Bhatt, Chung, Leighton, Rosenberg, 1989 ; Chung, 1990 .

Kirjallisuus