I grafteorin är parallellsekventiella grafer grafer med två olika hörn, som kallas terminal , bildade rekursivt med hjälp av två enkla operationer [1] . Dessa grafer kan användas för att modellera serie- och parallellkoppling av elektriska kretsar .
I detta sammanhang innebär begreppet en graf en multigraf .
Det finns flera sätt att definiera parallellsekventiella grafer. Följande definition är huvudsakligen baserad på David Eppsteins [2] definition .
En graf med ett terminalpar (STP) är en graf som har två distinkta hörn s och t märkta , kallade source respektive sink .
En parallellkoppling Pc = Pc(X,Y) av två icke-korsande GTP-grafer X och Y är en graf med ett terminalpar, skapad genom att kombinera graferna X och Y genom att slå samman källorna X och Y för att bilda källan Pc och sammanfoga sänkor X och Y för att bilda sjunka av grafen Pc .
Den seriella anslutningen Sc = Sc(X,Y) för två icke-korsande GST-grafer X och Y är GST-grafen som skapas av föreningen av graferna X och Y genom att sammanfoga sinken X med källan Y . Källan till graf X blir källan till Sc , och sänkan till grafen Y blir sänkan till Sc .
En seriell-parallell graf med ett terminalpar (PSPP-graf) är en graf som kan erhållas som ett resultat av seriella och parallella anslutningar av en uppsättning kopior av K 2 -enkantsgrafer med tilldelade terminaler.
Definition 1 . En graf sägs vara seriell-parallell om den är en POTP och två av dess hörn är märkta som en källa och en sänka.
På liknande sätt kan man definiera serieparallella digrafer , som är byggda från kopior av riktade grafer med en båge, i vilket fall bågen riktas från källan till sänkan.
Följande definition ger samma klass av grafer [3] .
Definition 2 . En graf är seriell-parallell om den kan omvandlas till en graf K 2 med hjälp av en sekvens av följande operationer:
Varje parallellsekventiell graf har en trädbredd och en grenbredd som inte överstiger 2 [4] . Faktum är att en graf har en trädbredd på högst 2 om och endast om den har en grenbredd på högst 2, och även om och endast om någon bikopplad komponent är en parallell-seriell graf [5] [6] . Maximala parallell-seriegrafer, grafer till vilka ytterligare kanter inte kan läggas till utan att förstöra den seriell-parallella strukturen, är exakt 2-träd .
Parallellsekventiella grafer kännetecknas av frånvaron av en subgraf som är homeomorf till grafen K 4 [4] .
Parallellsekventiella grafer kan karakteriseras av deras öronupplösning [2] .
Parallellsekventiella grafer kan kännas igen i linjär tid [7] och deras parallellsekventiella uppdelningar kan också konstrueras i linjär tid.
Förutom att modellera vissa typer av elektriska kretsar, är dessa grafer av intresse i beräkningskomplexitetsteori , eftersom många standardproblem på grafer löses i linjär tid på GTT-grafer [8] , inklusive att hitta den maximala matchningen , den maximala oberoende mängden , den minsta dominerande set och Hamiltonskt komplement . Några av dessa generella grafproblem är NP-kompletta . Anledningen till detta är det faktum att om svaren på dessa problem är kända för två parallell-seriegrafer, så kan man snabbt hitta svaret för deras seriella och parallella anslutningar.
Seriell-Parallell Graph Problem hänvisar till frågan om att räkna upp grafer och frågar om antalet parallell-seriella grafer som kan bildas från ett givet antal kanter.
Generaliserade parallellsekventiella grafer (GPP-grafer) är en generalisering av parallellsekventiella grafer [9] där graferna har samma algoritmiska effektivitet för de nämnda problemen. Klassen av OPP-grafer inkluderar parallell-seriegrafer och ytterplanära grafer .
OPP-grafer kan definieras genom att lägga till en tredje operation för att ta bort hängande hörn (hörn av grad 1) i definition 2 . På samma sätt kan följande operation läggas till i definition 1 .
Ett SPQR-träd är en struktur som kan definieras för en godtycklig 2-vertex-kopplad graf . Strukturen har S-noder som är analoga med en seriell anslutning i parallell-seriella grafer, P-noder som är analoga med en parallellkoppling av parallell-seriella grafer och R-noder som inte motsvarar operationerna för parallell-seriella grafer. En 2-kopplad graf är parallellsekventiell om och endast om det inte finns några R-noder i SPQR-trädet.