Graafiteoriassa rinnakkaiset peräkkäiset graafit ovat graafeja, joissa on kaksi eri kärkeä, joita kutsutaan terminaaleiksi ja jotka muodostetaan rekursiivisesti kahdella yksinkertaisella operaatiolla [1] . Näillä kaavioilla voidaan mallintaa sähköpiirien sarja- ja rinnakkaiskytkentää .
Tässä yhteydessä graafin käsite tarkoittaa multigrafia .
On olemassa useita tapoja määritellä rinnakkaisia peräkkäisiä kaavioita. Seuraava määritelmä perustuu pääasiassa David Eppsteinin [2] määritelmään .
Graafi, jossa on yksi päätepari (STP) on graafi, jossa on kaksi erillistä kärkeä s ja t , jotka on merkitty , joita kutsutaan vastaavasti lähteeksi ja nieluksi .
Kahden ei-leikkaavan GTP-graafin X ja Y rinnakkaisyhteys Pc = Pc(X,Y) on graafi, jossa on yksi päätepari, joka on luotu yhdistämällä kuvaajat X ja Y yhdistämällä lähteet X ja Y muodostamaan lähteen Pc ja yhdistämällä nielut X ja Y muodostavat graafin Pc nielun .
Kahden ei-leikkaavan GST-graafin X ja Y sarjayhteys Sc = Sc(X,Y) on GST-graafi, joka on luotu graafien X ja Y liitolla yhdistämällä nielu X lähteeseen Y . Graafin X lähteestä tulee Sc:n lähde ja graafin Y nielusta Sc : n nielu .
Serial-Parallel Graph with One Terminal Pair (PSPP-kaavio) on graafi, joka voidaan saada sarja- ja rinnakkaisliitäntöjen tuloksena K 2 yksireunaisten graafisten kopioiden sarjassa, joilla on määritetty päätepisteet.
Määritelmä 1 . Graafin sanotaan olevan sarjasuuntainen, jos se on POTP ja sen kaksi kärkeä on merkitty lähteeksi ja nieluksi.
Vastaavasti voidaan määritellä sarja-rinnakkaisdigrafit , jotka rakennetaan yhden kaarisen suunnattujen graafien kopioista, jolloin kaari on suunnattu lähteestä nielulle.
Seuraava määritelmä antaa saman luokan graafit [3] .
Määritelmä 2 . Graafi on sarjasuuntainen, jos se voidaan muuntaa graafiksi K 2 seuraavien operaatioiden sarjalla:
Minkä tahansa rinnakkaisen peräkkäisen graafin puun leveys ja haarautumisleveys on enintään 2 [4] . Itse asiassa graafin puun leveys on korkeintaan 2, jos ja vain, jos sen haaran leveys on enintään 2, ja myös jos ja vain jos mikä tahansa biliittynyt komponentti on rinnakkaissarjagraafi [5] [6] . Maksimaaliset rinnakkaissarjakuvaajat, graafit, joihin ei voida lisätä lisäreunoja tuhoamatta sarjarinnanrakennetta, ovat täsmälleen 2-puuta .
Rinnakkaisille peräkkäisille graafiille on ominaista graafin K 4 kanssa homeomorfisen aligraafin puuttuminen [4] .
Rinnakkaiset peräkkäiset graafit voidaan luonnehtia niiden korvahajotuksella [2] .
Rinnakkaiset peräkkäiset kuvaajat voidaan tunnistaa lineaarisessa ajassa [7] ja niiden rinnakkaiset peräkkäiset hajotukset voidaan rakentaa myös lineaarisessa ajassa.
Tietyntyyppisten sähköpiirien mallintamisen lisäksi nämä kaaviot ovat kiinnostavia laskennallisen monimutkaisuuden teoriassa , koska monet kaavioiden standardiongelmat ratkaistaan lineaarisessa ajassa GTT-kaavioissa [8] , mukaan lukien maksimisovituksen , suurimman riippumattoman joukon , minimidominoivan joukon löytäminen . joukko , ja Hamiltonin komplementti . Jotkut näistä yleisistä graafiongelmista ovat NP-täydellisiä . Syynä tähän on se, että jos vastaukset näihin ongelmiin tiedetään kahdelle rinnakkaissarjakuvaajalle, niin niiden sarja- ja rinnakkaisliitäntöihin voidaan löytää nopeasti vastaus.
Serial-Parallel Graph Problem viittaa graafien luetteloimiseen ja kysyy, kuinka monta rinnakkaista sarjakuvaa voidaan muodostaa tietystä määrästä reunoja.
Yleistetyt rinnakkaiset peräkkäiset graafit (GPP-graphs) ovat rinnakkaisten peräkkäisten graafien yleistys [9] , jossa kaavioilla on sama algoritminen tehokkuus mainituissa ongelmissa. OPP-graafien luokkaan kuuluvat rinnakkaissarjakuvaajat ja ulkotasokuvaajat .
OPP-graafit voidaan määritellä lisäämällä kolmas operaatio roikkuvien kärkien (asteen 1 kärkipisteiden) poistamiseksi määritelmässä 2 . Samalla tavalla seuraava operaatio voidaan lisätä määritelmään 1 .
SPQR-puu on rakenne, joka voidaan määrittää mielivaltaiselle 2-vertex-yhdistetylle graafille . Rakenteessa on S solmua, jotka ovat analogisia rinnakkaissarjakaavioiden sarjakytkennän kanssa, P solmuja, jotka ovat analogisia rinnakkaissarjakaavioiden rinnakkaisliitännälle, ja R solmua, jotka eivät vastaa rinnakkaissarjaisten graafien toimintoja. 2-kytkentäinen graafi on rinnakkainen peräkkäinen silloin ja vain, jos SPQR-puussa ei ole R-solmua.