Silta (graafiteoria)

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 10. marraskuuta 2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Silta on graafiteoriassa reuna , jonka poistaminen lisää kytkettyjen komponenttien määrää [1] . Tällaisia kylkiluita kutsutaan myös leikkausripeiksi , leikkauskaareiksi tai kannaksiksi . Vastaava määritelmä on, että reuna on silta silloin ja vain, jos se ei sisälly mihinkään sykliin .

Puut ja metsät

Graafi, jossa on pisteet, voi sisältää korkeintaan siltoja, koska yhden reunan lisääminen johtaa väistämättä syklin esiintymiseen. Kuvaajat, joissa on täsmälleen siltoja, tunnetaan puina , ja kuvaajat, joissa mikä tahansa reuna on silta, ovat metsiä . $n$ $n-1$ $n-1$

Missä tahansa suuntaamattomassa graafissa on kärkiekvivalenssirelaatio , jonka mukaan kaksi kärkeä on ekvivalenttinen , jos niitä yhdistää kaksi polkua, jotka eivät leikkaa reunoja pitkin (mikä tahansa kärki katsotaan vastaavaksi itselleen). Tämän suhteen ekvivalenssiluokkia kutsutaan 2-edge-connected komponenteiksi ja graafin siltoja ovat juuri ne reunat, joiden päät kuuluvat eri komponentteihin. Graafin siltauslohkokaaviossa on kärkipiste mille tahansa ei-triviaalille komponentille ja kullekin sillalle reuna [2] .

Yhteys vertex-yhteydellä

Sillat liittyvät läheisesti saranoiden käsitteeseen, pisteisiin , jotka menevät mihin tahansa polkuun, joka yhdistää kaksi kärkeä. Sillan kaksi päätypistettä ovat saranoituja, elleivät ne ole astetta 1, vaikka myös ei-sillan reunat voidaan saranoida molemmista päistä. Kuten kaaviot ilman siltoja, jotka on yhdistetty 2 reunaan, graafit ilman saranoita ovat vertex-2-kytkettyjä .

Kuutiokaavioissa mikä tahansa sarana on vähintään yhden sillan päätepiste.

Kuvaajat ilman siltoja

Kuten nimestä voi päätellä, sillaton graafi on graafi, jossa ei ole siltoja. Vastaavia ehtoja ovat, että jokaisella graafin yhdistetyllä komponentilla on avoin korvahajotus [3] , että jokainen yhdistetty komponentti on 2-särmäinen tai ( Robbinsin lauseen mukaan ), että jokaisella yhdistetyllä komponentilla on vahva orientaatio [3 ] .

Tärkeä siltoihin liittyvä avoin ongelma on Seymourin ja Székeresin (vuosina 1978 ja 1979 itsenäisesti) ehdottama kaksinkertaisen syklin peittooletus , jonka mukaan mikä tahansa sillaton graafi voidaan kattaa yksinkertaisilla syklillä, jotka sisältävät kunkin reunan kahdesti [4] .

Tarjanin siltahakualgoritmi

Ensimmäisen algoritmin siltojen löytämiseksi graafista, jossa on lineaarinen ajoaika , kuvasi Robert Tarjan vuonna 1974 [5] . Algoritmi toimii näin:

Etsi kaavion kattava metsä . $G$
Luo metsä, jonka juuret ulottuvat ylittävästä puusta. $F$
Kierrämme metsää suorassa järjestyksessä ja numeroimme kärjet. Vanhempien kärjet on nyt numeroitu pienempiä kuin heidän lapsensa. $F$

Merkitsemme puun sisältämää reunaa (v,w) muodossa , mutta ei sisällä muodossa . $v\to w$ $v-w$

Suoritamme kullekin kärjelle suoran läpikäynnin aikana: $v$
- Laskemme kärjen lapsimäärän , lisäämme yhden kun siirrymme seuraavaan kärkeen (mukaan lukien kärki ). $ND(v)$ $v$

$ND(v) = 1 + \sum_{v \to w} ND(w)$ .

- Laske , minimimäärä, joka voidaan saavuttaa kärjestä , seuraamalla pisteestä alkavan alipuun reunoja (paitsi viimeistä reunaa). Tämä on pienin määrä joukossa, joka koostuu kärjen jälkeläisten arvoista ja pisteiden määrästä, jotka voidaan saavuttaa reunoista, jotka eivät kuulu . $L(v)$ $v$ $v$ $L(w)$ $v$ $v$ $F$

$L(v)=\min(\{v\}\cup \{L(w)\mid v\to w\}\cup \{w\mid v--w\})$

- Samoin laske , suurin luku, joka voidaan saavuttaa seuraamalla alipuun reunoja alkaen . Tämä on suurin määrä arvojoukossa, joka koostuu kärjen jälkeläisten arvoista ja niiden kärkien numeroista, jotka voidaan saavuttaa reunoista, jotka eivät kuulu . $H(v)$ $v$ $H(w)$ $v$ $v$ $F$

$H(v)=\max(\{v\}\cup \{H(w)\mid v\to w\}\cup \{w\mid v--w\})$

- Jokaiselle kärkelle , jolla on vanhempi , tarkistamme jos ja , niin reuna kohdasta kohteeseen on silta. $w$ $v$ $L(w) = w$ $K(w) < w + ND(w)$ $v$ $w$

Jos on silta, niin on selvää, että alipuusta, joka on juurtunut, ei pitäisi olla mitään mahdollisuutta mennä kärkeen, joka ei kuulu tähän alipuuhun. Tämän tarkistamiseksi riittää tarkistaa L(w), H(w) - ehto tarkoittaa, että emme mene kärkeen, joka sijaitsee lähempänä juuria, ja ehto tarkoittaa, että emme mene toiseen alipuuhun. $v\to w$ $w$ $L(w) = w$ $K(w) < w + ND(w)$

Siltojen etsiminen ketjuhajotuksella

Hyvin yksinkertainen siltahakualgoritmi [6] perustuu ketjun hajotukseen. Ketjun hajottaminen ei ainoastaan tuota kaikkia siltoja, se tuottaa myös kaikki graafin G saranat (ja kaksinkertaisesti kytketyt komponentit) , mikä tarjoaa perustan reunan ja vertex 2 -liitettävyyden testaamiseen (ja tätä menetelmää voidaan laajentaa lineaariseen ajassa varmennukseen). reuna- ja kärki 3-yhteydestä).

Ketjuhajotus on korvahajottamisen erikoistapaus, joka perustuu graafin G puun T syvähakuun, ja se voidaan tehdä hyvin yksinkertaisesti:

merkitään kaikki kärjet vierailemattomiksi. Kaikille kärkipisteille v nousevassa järjestyksessä läpikulkunumeroiden 1... n läpi, kuljemme jokaisen takaperin (eli reunan, joka ei kuulu läpikulkupuuhun), joka tulee v :lle , ja seuraa puun reunoja juureen, kunnes kohdata vieraillun huippupisteen. Tämän ohituksen aikana merkitsemme kaikki ohitetut kärjet käydyiksi. Tämä kulku päättyy joko polkuun tai silmukkaan, joka alkaa kohdasta v , kutsumme tätä poluksi tai silmukaksi ketjuksi . Merkitsemme i :ttä merkkijonoa, joka on saatu sellaisella menettelyllä kuin C i . C=C 1 ,C 2 ,... on tällöin graafin G osio ketjuiksi .

Seuraavat ominaisuudet mahdollistavat jonkin graafin G : n tiedon saamisen C:stä tehokkaasti , mukaan lukien kaikki sillat [6] :

Olkoon C yksinkertaisen yhdistetyn graafin G=(V,E) ketjuhajotelma .

G on 2-särmäinen, jos ja vain jos C :n ketjut sisältävät kaikki reunat E :stä .
G :n reuna e on silta silloin ja vain, jos e ei sisälly mihinkään C :n ketjuun .
Jos G on 2-reunainen, C on korvahajotus .
G on 2-kärkikytketty silloin ja vain jos G :llä on minimiaste 2 ja C 1 on C:n ainoa sykli .
2-särmäyhteytetyn graafin G kärki v on sarana silloin ja vain, jos v on ensimmäinen kärki syklissä C - C 1 .
Jos G on vertex-2-kytketty, C on avoin dekompositio korviin .

Muistiinpanot

↑ Bela Bollobas. Moderni graafiteoria. - New York: Springer-Verlag, 1998. - T. 184. - S. 6. - (Matematiikan tutkinnon tekstit). — ISBN 0-387-98488-7 . - doi : 10.1007/978-1-4612-0619-4 .
↑ Jeffery Westbrook, Robert E. Tarjan. Siltakytkettyjen ja kaksoisliitettyjen komponenttien ylläpito online-tilassa // Algorithmica. - 1992. - T. 7 , numero. 5-6 . - S. 433-464 . - doi : 10.1007/BF01758773 .
↑ 1 2 H. E. Robbins. Kaavioiden lause, jossa sovellus liikenteenohjauksen ongelmaan // The American Mathematical Monthly . - 1939. - T. 46 . - S. 281-283 .
↑ F. Jaeger. Annals of Discrete Mathematics 27 - Cycles in Graphs. - 1985. - T. 27. - S. 1-12. — (North-Holland Mathematics Studies). - doi : 10.1016/S0304-0208(08)72993-1 .
↑ R. Endre Tarjan. Huomautus graafin siltojen löytämisestä // Tietojenkäsittelykirjaimet. - T. 2 , no. 6 . - S. 160-161 . - doi : 10.1016/0020-0190(74)90003-9 .
↑ 1 2 Jens M. Schmidt. Yksinkertainen testi 2-vertex- ja 2-Edge-yhteydestä // Tietojenkäsittelykirjaimet. - 2013. - T. 113 , no. 7 . - S. 241-244 . - doi : 10.1016/j.ipl.2013.01.016 .