A gráfelméletben a párhuzamos-szekvenciális gráfok két különböző csúcsú gráfok, amelyeket terminálisnak nevezünk , és két egyszerű művelettel rekurzív módon alakítanak ki [1] . Ezek a grafikonok felhasználhatók elektromos áramkörök soros és párhuzamos kapcsolásának modellezésére .
Ebben az összefüggésben a gráf fogalma multigráfot jelent .
Számos módja van a párhuzamos-szekvenciális gráfok meghatározásának. A következő meghatározás főként David Eppstein [2] definícióján alapul .
Az egy terminálpárt tartalmazó gráf (STP) egy olyan gráf, amelynek két különálló s és t csúcsa van, amelyeket forrásnak és nyelőnek neveznek .
Két nem metsző X és Y GTP gráf Pc = Pc(X,Y) párhuzamos kapcsolata egy egy terminálpárral rendelkező gráf, amelyet az X és Y gráfok kombinálásával hoztak létre, az X és Y források összevonásával Pc forrást és X nyelőket egyesítve . és Y a Pc gráf nyelőjét képezi .
Két nem metsző X és Y GST gráf Sc = Sc(X,Y) soros kapcsolata az X és Y gráfok egyesítése által az X nyelőnek az Y forrással való egyesítése által létrehozott GST gráf . Az X gráf forrása Sc forrásává, az Y gráf nyelője pedig Sc nyelőjévé válik .
A Serial-Parallel Graph with One Terminal Pair (PSPP-gráf) egy olyan gráf, amely a hozzárendelt terminálcsúcsokkal rendelkező K 2 egyélű gráfok másolatainak soros és párhuzamos összekapcsolásával nyerhető .
1. definíció . Egy gráfot soros párhuzamosnak mondunk, ha egy POTP, és két csúcsa forrásként és nyelőként van megjelölve.
Hasonlóképpen definiálhatunk soros-párhuzamos digráfokat , amelyek egy ívű irányított gráfok másolataiból épülnek fel, ebben az esetben az ív a forrástól a nyelőig irányul.
A következő definíció ugyanazt a gráfosztályt adja meg [3] .
2. definíció . Egy gráf soros-párhuzamos, haa következő műveletek sorozatával K 2 gráfrá alakítható:
Bármely párhuzamos-szekvenciális gráf faszélessége és elágazási szélessége nem haladja meg a 2 -t [4] . Valójában egy gráf faszélessége legfeljebb 2 akkor és csak akkor, ha ágszélessége legfeljebb 2, és akkor és csak akkor, ha bármely kettõs komponens párhuzamos soros gráf [5] [6] . A maximális párhuzamos-soros gráfok, amelyekhez nem lehet további éleket hozzáadni a soros-párhuzamos struktúra tönkretétele nélkül, pontosan 2-fák .
A párhuzamos-szekvenciális gráfokat a K 4 gráfra homeomorf részgráf hiánya jellemzi [4] .
A párhuzamos-szekvenciális gráfok fülbontásukkal jellemezhetők [2] .
A párhuzamos-szekvenciális gráfok lineáris időben felismerhetők [7] , és párhuzamos-szekvenciális dekompozícióik lineáris időben is megszerkeszthetők.
Amellett, hogy bizonyos típusú elektromos áramköröket modelleznek, ezek a grafikonok érdekesek a számítási komplexitáselméletben is, mivel a gráfokon sok standard probléma lineáris időben megoldott GTT gráfokon [8] , beleértve a maximális illeszkedést , a maximális független halmazt , a minimális dominanciát . halmaz , és Hamilton komplementer . Ezen általános gráffeladatok némelyike NP-teljes . Ennek az az oka, hogy ha ezekre a problémákra két párhuzamos-soros gráf esetében ismerjük a választ, akkor azok soros és párhuzamos kapcsolataira is gyorsan meg lehet találni a választ.
A Serial-Parallel Graph Problem a gráfok felsorolásának kérdéséreés arra kérdez rá, hogy adott számú élből hány párhuzamos-soros gráfot lehet kialakítani.
Az általánosított párhuzamos-szekvenciális gráfok (GPP-gráfok) a párhuzamos-szekvenciális gráfok általánosítása [9] , amelyekben a gráfok algoritmikus hatékonysága megegyezik az említett problémákkal. Az OPP gráfok osztályába tartoznak a párhuzamos soros gráfok és a külső síkbeli gráfok .
Az OPP gráfok egy harmadik művelet hozzáadásával definiálhatók a lógó csúcsok (1. fokú csúcsok) eltávolítására a 2. definícióban . Ugyanígy a következő művelet hozzáadható az 1. definícióhoz .
Az SPQR fa egy tetszőleges, 2 csúcsponttal összekapcsolt gráfhoz definiálható struktúra . A struktúrának van S csomópontja, amely analóg a párhuzamos soros gráfok soros kapcsolatával, P csomópontja, amely analóg a párhuzamos soros gráfok párhuzamos kapcsolatával, és R csomópontja, amelyek nem felelnek meg a párhuzamos soros gráfok műveleteinek. Egy 2 összekapcsolt gráf akkor és csak akkor párhuzamos-szekvenciális, ha nincs R csomópont az SPQR fában.