Korvan hajoaminen

Graafiteoriassa suuntaamattoman graafin G korva on polku P , jonka kaksi päätepistettä voivat yhtyä, mutta muuten kärkien tai reunojen toistuminen ei ole sallittua, joten millä tahansa P :n sisäpisteellä on polussa aste kaksi. Suuntaamattoman graafin G korvahajotelma on sen reunan osio , joka on asetettu korvasarjaan siten, että kunkin korvan päätepisteet kuuluvat sarjassa aiemmin valittuihin korviin, kun taas kunkin korvan sisäpisteet eivät kuulu edelliseen. korvat. Useimmissa tapauksissa sarjan ensimmäisen korvan tulisi myös olla silmukka. Avoin tai oikea korvan hajoaminen on korvan hajoamista, jossa kummankin korvan kaksi päätepistettä, paitsi ensimmäinen, ovat erilaisia.

Korvahajotelmaa voidaan käyttää kuvaamaan joitakin tärkeitä graafiluokkia ja osana tehokkaita graafialgoritmeja . Korvan hajoaminen voidaan yleistää matroideihin .

Kuvaus graafiluokista

Joitakin tärkeitä kaavioluokkia voidaan kuvata tietyntyyppisillä korvahajotelmilla.

Kuvaajan liitettävyys

Graafi on vertex-k-kytketty , jos vain ( k − 1) kärjen poistaminen jättää aligraafin liitetyksi, ja k- särmäkytkennäinen, jos poistamalla minkä tahansa ( k − 1) reunan, aligraafi jää yhteen.

Seuraava tulos johtuu Hasler Whitneystä [1] :

Graafi , jossa on kärkipiste, on 2-kytketty silloin ja vain, jos sillä on avoin korvahajotus.

G=(V,E)

|E|\geq 2

Seuraava tulos johtuu Herbert Robinsonista [2] :

Graafi on 2-särmäinen silloin ja vain, jos siinä on korvahajotus.

Molemmissa tapauksissa korvien lukumäärän on oltava yhtä suuri kuin käyrän ääriviiva . Robbins käytti 2-reunaan yhdistettyjen graafien korvahajottelua keinona todistaa Robbinsin lause , että nämä ovat täsmälleen graafit, joille voidaan antaa vahvasti yhdistetty orientaatio. Koska Whitney ja Robinson tutkivat ensimmäisenä korvan hajoamista, sitä kutsutaan joskus Whitney-Robinson-synteesiksi [3] .

Ei- erottava korvahajotelma on avoin korvahajotus siten, että jokaiselle v:n kärjelle yhtä lukuun ottamatta v :llä on naapuripiste, joka esiintyy myöhemmin kuin v hajotuksessa . Tämän tyyppistä hajotusta voidaan käyttää yleistämään Whitneyn tulos:

Graafi c on 3-pisteinen, jos ja vain jos G :llä on erottelematon korvahajotelma.

G=(V,E)

|V|\geq 2

Jos tällainen jaottelu on olemassa, se voidaan valita G :n reunan uv suhteen siten, että u kuuluu ensimmäiseen korvaan, v on uusi kärki viimeisessä korvassa, jossa on useampi kuin yksi reuna ja uv on korva, joka koostuu yhdestä reuna. Tämän tuloksen esittivät ensin selkeästi Cheryan ja Maheshwari [4] , mutta kuten Schmidt kirjoittaa [5] , se vastaa Ph.D:n tulosta. Lee Mondsheinin väitöskirja vuodelta 1971. Rakenteet, jotka liittyvät läheisesti maksimaalisten tasokaavioiden erottamattomiin korvahajotuksiin, joita kutsutaan kanonisiksi järjestyksiksi, ovat myös tavallinen kuvaajan visualisoija .

Suunnattujen kuvaajien vahva liitettävyys

Yllä annetut määritelmät voidaan laajentaa myös suunnattuihin graafisiin . Korva on tällöin suunnattu polku, jossa kaikkien sisäisten kärkien in -aste ja ulkoaste on 1. Suunnattu graafi on vahvasti yhteydessä , jos se sisältää suunnatun polun mistä tahansa kärjestä mihin tahansa toiseen kärkeen. Sitten seuraava lause pätee:

Suunnattu graafi on vahvasti yhteydessä silloin ja vain, jos siinä on korvahajotelma.

Vastaavasti suunnattu graafi on kaksinkertaisesti yhdistetty , jos jollekin kahdelle pisteelle on olemassa yksinkertainen sykli, joka sisältää molemmat kärjet. Sitten

Suunnattu graafi on kaksinkertainen, jos ja vain, jos sillä on avoin korvahajotus.

Tekijäkriittiset kaaviot

Korvan hajoaminen on pariton , jos kullakin korvalla on pariton määrä reunoja. Tekijäkriittinen graafi on graafi, jossa on pariton määrä pisteitä siten, että kun mikä tahansa kärki v poistetaan graafista, loput pisteet sopivat täydellisesti . Laszlo Lovas [6] havaitsi, että:

Graafi G on tekijäkriittinen graafi silloin ja vain, jos G :llä on pariton korvahajotus.

Yleisemmin Frankin tulos [7] mahdollistaa sen, että mille tahansa graafille G voidaan löytää korvahajotelma, jossa on vähiten parillisia korvia.

Rinnakkaiset peräkkäiset kaaviot

Puukorvahajotelma on oikea korvahajotelma , jossa ensimmäinen korva on yksi reuna ja jokaiselle seuraavalle korvalle on ainutlaatuinen korva , , jossa molemmat päätepisteet sijaitsevat [8] . Sisäkkäinen korvahajotelma on puun korvahajotus siten, että kunkin korvan sisällä olevien muiden korvien päätepisteiden joukko muodostaa joukon sisäkkäisiä välejä. Rinnakkaissarjagrafiikka on graafi, jossa on kaksi erillistä päätä s ja t , joka voidaan muodostaa rekursiivisesti yhdistämällä pienempiä rinnakkaissarjagrafioita kahdella tavalla - sarjakytkentä (tunnistamme toisen graafin toisen pään toinen graafi, ja toinen molempien graafien kahdesta päästä liitoksen päiksi) ja rinnakkaiskytkentä (tunnistamme molempien pienempien graafien molemmat pääteparit). ${\displaystyle P_{i))$ ${\näyttötyyli P_{j))$ ${\näyttötyyli i>j}$ ${\displaystyle P_{i))$ ${\näyttötyyli P_{j))$ ${\näyttötyyli P_{j))$ ${\displaystyle P_{i))$ ${\näyttötyyli P_{j))$

Seuraava tulos johtuu David Epsteinista [9] :

Vertex-2-yhdistetty graafi on rinnakkaissarjakuvaaja silloin ja vain, jos siinä on sisäkkäinen korvahajotelma.

Lisäksi kaikki 2-pisteisiin yhdistetyn rinnakkaissarjakuvaajan avoimen korvan hajotelmat on sisäkkäistettävä. Tulos voidaan yleistää rinnakkaisiksi peräkkäisiksi graafisiksi, jotka eivät ole 2-kärkiliitoksia, käyttämällä avoimen korvan hajotusta, joka alkaa näiden kahden pään väliseltä polulta.

Matroidit

Korvahajoamisen käsite voidaan yleistää kaavioista matroideihin . Matroidin korvahajoaminen määritellään matroidisyklien sarjaksi, jolla on kaksi ominaisuutta:

jokaisella sekvenssin silmukalla on ei-tyhjä leikkauspiste aiempien silmukoiden kanssa.
jokainen jakso jaksossa pysyy syklinä, vaikka kaikki sekvenssin edelliset jaksot supistuisivat.

Kun sitä sovelletaan graafin G graafimatroidiin , tämä korvahajotelman määritelmä on sama kuin G :n oikean hajotuksen määritelmä - virheelliset hajotukset suljetaan pois vaatimuksella, että jokaiseen sykliin kuuluu vähintään yksi reuna. edellisiin sykleihin. Tätä määritelmää käyttäen matroidi voidaan määritellä osamääräkriittiseksi, jos sillä on korvahajotus, jossa jokaisessa jaksossa on pariton määrä uusia elementtejä [10] .

Algoritmit

2-reunaan yhdistettyjen graafien korvahajotus ja 2-vertex-yhdistettyjen graafien avoin dekompositio voidaan löytää käyttämällä ahneita algoritmeja , jotka löytävät jokaisen korvan yksitellen. Schmidt [11] ehdotti yksinkertaista ahnetta algoritmia, joka laskee korvan laajenemisen, avoimen korvan laajenemisen, st-numeroinnin ja st-orientaation lineaarisessa ajassa (jos sellaisia on olemassa ) . Lähestymistapa perustuu erikoistyyppisen korvahajottamisen, ketjuhajottamisen, laskemiseen yhden polun generointisäännöllä. Schmidt osoitti [5] , että erottelematon korvahajotus voidaan rakentaa lineaarisessa ajassa.

Lovas [12] , Maon, Shiber ja Vyshkin [13] sekä Miller ja Ramachandran [14] ovat tarjonneet tehokkaita rinnakkaisalgoritmeja erityyppisten korvadekompositioiden rakentamiseen. Esimerkiksi 2-reunaan yhdistetyn graafin korvahajotelman löytämiseksi Maonin, Schieberin ja Wyshkinin [13] algoritmi käy läpi seuraavat vaiheet:

Annetun graafin virittävä puu löydetään ja puun juuri valitaan.
Määritä jokaiselle reunalle uv , joka ei ole osa puuta, etäisyys u :n ja v :n juuren ja vähiten yhteisen esi -isän välillä .
Etsi jokaiselle puun osalle kuuluvalle reunalle uv vastaava "pääreuna", reuna wx , joka ei ole puusta siten, että kierto, joka muodostuu lisäämällä puuhun wx , kulkee uv :n läpi ja siten, että kaikkien reunojen joukossa w ja x sillä on alin esi-isä mahdollisimman lähellä juuria.
Muodostamme korvan kullekin ei-puun reunalle, joka koostuu tästä reunasta ja sen puun reunoista, joille tämä reuna on tärkein. Järjestämme korvat pääreunan etäisyyksien mukaan juurista.

Tätä algoritmia voidaan käyttää proseduurina muihin ongelmiin, mukaan lukien liitettävyyden tarkistaminen, sarja-rinnakkaiskuvaajien tunnistaminen ja kaavioiden st -numeroinnin muodostaminen (tärkeä menettely tasomaisuuden tarkistamiseksi ).

Matroidin korvahajotus lisärajoituksella, että mikä tahansa korva sisältää saman kiinteän määrän matroidielementtejä, voidaan löytää polynomiajassa , jos matroidille on riippumaton oraakkeli [15] .

Kirjallisuus

J. Cheriyan, S. N. Maheshwari. Erottelemattomien indusoitujen syklien ja riippumattomien virittävien puiden löytäminen 3-liitetyistä kaavioista // Journal of Algorithms. - 1988. - T. 9 , no. 4 . — S. 507–537 . - doi : 10.1016/0196-6774(88)90015-6 .
Collette R. Collard, Lisa Hellerstein. Itsenäisyys ja porttioraakkelit matroideille, sovelluksella laskennalliseen oppimisteoriaan // Combinatorica . - 1996. - T. 16 , no. 2 . — S. 189–208 . - doi : 10.1007/BF01844845 .
D. Eppstein. Sarja-rinnakkaiskuvaajien rinnakkaistunnistus // Information & Computation. - 1992. - T. 98 , no. 1 . - S. 41-55 . - doi : 10.1016/0890-5401(92)90041-D .
Andras Frank. Konservatiiviset painotukset ja graafien korvahajotteet // Combinatorica . - 1993. - T. 13 , no. 1 . — s. 65–81 . - doi : 10.1007/BF01202790 .
Jonathan L. Gross, Jay Yellen. Graafiteoria ja sen sovellukset. – 2. – Chapman & Hall/CRC, Boca Raton, FL, 2006. – s. 498–499. - (Diskreetti matematiikka ja sen sovellukset (Boca Raton)). - ISBN 978-1-58488-505-4 .
Samir Huller. Korvien hajoaminen // SIGACT News . - 1989. - T. 20 , no. 1 . - S. 128 .
Laszlo Lovasz . Huomautus tekijäkriittisistä kaavioista // Studia Sci. Matematiikka. Ripustettu .. - 1972. - T. 7 . — S. 279–280 .
László Lovasz. 26. vuotuinen symposium tietojenkäsittelytieteen perusteista . - 1985. - S. 464-467. - doi : 10.1109/SFCS.1985.16 .
Y. Maon, B. Schieber, U. Vishkin. Rinnakkaiskorvahaku (EDS) ja ST-numerointi kaavioissa // Tietojenkäsittelyteoria . - 1986. - T. 47 , no. 3 . - doi : 10.1016/0304-3975(86)90153-2 .
G. Miller , V. Ramachandran. Tehokas rinnakkaiskorvan hajoaminen sovelluksilla. - Julkaisematon käsikirjoitus, 1986.
H.E. Robbins . Kaavioiden lause, jossa sovellus liikenteenohjauksen ongelmaan // American Mathematical Monthly . - 1939. - T. 46 . — S. 281–283 . - doi : 10.2307/2303897 . .
Jens M. Schmidt. Yksinkertainen testi 2-vertex- ja 2-Edge-yhteydestä // Tietojenkäsittelykirjaimet. – 2013a. - T. 113 , no. 7 . — S. 241–244 . - doi : 10.1016/j.ipl.2013.01.016 .
Jens M. Schmidt. Mondshein-sarja. – 2013b.
Alexander Schrijver . kombinatorinen optimointi. Polyhedra ja tehokkuus. Vol A. - Springer-Verlag, 2003. - ISBN 978-3-540-44389-6 .
Balázs Szegedy, Christian Szegedy. Symplektiset tilat ja matroidien korvahajoaminen // Combinatorica . - 2006. - T. 26 , no. 3 . — S. 353–377 . - doi : 10.1007/s00493-006-0020-3 .
H. Whitney . Erottelemattomat ja tasomaiset graafit // Transactions of the American Mathematical Society . - 1932. - T. 34 . — S. 339–362 . - doi : 10.1090/S0002-9947-1932-1501641-2 . — .