I grafteori er parallel-sekventielle grafer grafer med to forskellige toppunkter, som kaldes terminal , dannet rekursivt ved hjælp af to simple operationer [1] . Disse grafer kan bruges til at modellere serie- og parallelforbindelse af elektriske kredsløb .
I denne sammenhæng indebærer begrebet en graf en multigraf .
Der er flere måder at definere parallel-sekventielle grafer på. Den følgende definition er hovedsageligt baseret på David Eppsteins [2] definition .
En graf med ét terminalpar (STP) er en graf, der har to adskilte hjørner s og t mærket , kaldet henholdsvis source og sink .
En parallelforbindelse Pc = Pc(X,Y) af to ikke-skærende GTP-grafer X og Y er en graf med ét terminalpar, skabt ved at kombinere graferne X og Y ved at flette kilderne X og Y for at danne kilde Pc og flette sinks X og Y for at danne sink af grafen Pc .
Den serielle forbindelse Sc = Sc(X,Y) af to ikke-skærende GST-grafer X og Y er GST-grafen skabt af foreningen af graferne X og Y ved at flette sink X med kilden Y . Kilden til graf X bliver kilden til Sc , og synken til graf Y bliver synken til Sc .
En seriel-parallel graf med et terminalpar (PSPP-graf) er en graf, der kan opnås som et resultat af serielle og parallelle forbindelser af et sæt kopier af K 2 -enkantsgrafer med tildelte terminalhjørner.
Definition 1 . En graf siges at være seriel-parallel , hvis den er en POTP, og to af dens hjørner er mærket som en kilde og et synke.
På samme måde kan man definere serie-parallelle digrafer , som er bygget af kopier af rettede grafer med én bue, i hvilket tilfælde buen ledes fra kilden til synken.
Den følgende definition giver den samme klasse af grafer [3] .
Definition 2 . En graf er seriel-parallel, hvis den kan transformeres til en graf K 2 ved hjælp af en sekvens af følgende operationer:
Enhver parallel-sekventiel graf har en træbredde og en forgreningsbredde , der ikke overstiger 2 [4] . Faktisk har en graf højst træbredde 2, hvis og kun hvis den har en grenbredde på højst 2, og også hvis og kun hvis en biforbundet komponent er en parallel-seriel graf [5] [6] . Maksimale parallel-serielle grafer, grafer, hvortil yderligere kanter ikke kan tilføjes uden at ødelægge den seriel-parallelle struktur, er nøjagtigt 2-træer .
Parallel-sekventielle grafer er karakteriseret ved fraværet af en subgraf homøomorf til grafen K 4 [4] .
Parallel-sekventielle grafer kan karakteriseres ved deres ørenedbrydning [2] .
Parallel-sekventielle grafer kan genkendes i lineær tid [7] og deres parallel-sekventielle dekomponeringer kan også konstrueres i lineær tid.
Ud over at modellere nogle typer elektriske kredsløb, er disse grafer af interesse i beregningsmæssig kompleksitetsteori , da mange standardproblemer på grafer løses i lineær tid på GTT-grafer [8] , herunder at finde den maksimale matchning , maksimale uafhængige sæt , minimum dominerende sæt og Hamiltonsk komplement . Nogle af disse generelle grafproblemer er NP-komplette . Grunden til dette er det faktum, at hvis svarene på disse problemer er kendt for to parallel-serielle grafer, så kan man hurtigt finde svaret for deres serielle og parallelle forbindelser.
Seriel-Parallel Graph Problem refererer til spørgsmålet om optælling af grafer og spørger om antallet af parallel-serielle grafer, der kan dannes ud fra et givet antal kanter.
Generaliserede parallel-sekventielle grafer (GPP-grafer) er en generalisering af parallel-sekventielle grafer [9] , hvor graferne har samme algoritmiske effektivitet for de nævnte problemer. Klassen af OPP-grafer omfatter parallelle-serielle grafer og ydreplanære grafer .
OPP-grafer kan defineres ved at tilføje en tredje operation for at fjerne dinglende hjørner (hjørnepunkter af grad 1) i definition 2 . På samme måde kan følgende operation tilføjes til definition 1 .
Et SPQR-træ er en struktur, der kan defineres for en vilkårlig 2-vertex-forbundet graf . Strukturen har S-knuder, der er analoge med en seriel forbindelse i parallel-serielle grafer, P-knuder, der er analoge med en parallelforbindelse af parallel-serielle grafer, og R-knuder, der ikke svarer til operationerne af parallel-serielle grafer. En 2-forbundet graf er parallel-sekventiel, hvis og kun hvis der ikke er nogen R-noder i SPQR-træet.