V teorii grafů jsou paralelně-sekvenční grafy grafy se dvěma různými vrcholy, které se nazývají terminál , vytvořené rekurzivně pomocí dvou jednoduchých operací [1] . Tyto grafy lze použít k modelování sériových a paralelních zapojení elektrických obvodů .
V tomto kontextu pojem graf implikuje multigraf .
Existuje několik způsobů, jak definovat paralelně-sekvenční grafy. Následující definice je založena hlavně na definici Davida Eppsteina [2] .
Graf s jedním terminálovým párem (STP) je graf, který má dva odlišné vrcholy s a t označené , nazývané source a sink , v tomto pořadí.
Paralelní spojení Pc = Pc(X,Y) dvou neprotínajících se GTP grafů X a Y je graf s jedním vývodovým párem, vzniklý spojením grafů X a Y sloučením zdrojů X a Y za vzniku zdroje Pc a sloučením propadů X a Y tvoří propad grafu Pc .
Sériové spojení Sc = Sc(X,Y) dvou neprotínajících se GST grafů X a Y je GST graf vzniklý spojením grafů X a Y sloučením sink X se zdrojem Y . Zdroj grafu X se stává zdrojem Sc a propad grafu Y se stává propadem Sc .
Serial-Parallel Graph with One Terminal Pair (PSPP graf) je graf, který lze získat jako výsledek sériového a paralelního připojení sady kopií K 2 jednohranných grafů s přiřazenými koncovými vrcholy.
Definice 1 . O grafu se říká , že je sérioparalelní , pokud se jedná o POTP a dva jeho vrcholy jsou označeny jako zdroj a jímka.
Podobně lze definovat sérioparalelní digrafy , které jsou sestaveny z kopií orientovaných grafů s jedním obloukem, v takovém případě je oblouk nasměrován od zdroje k jímce.
Následující definice uvádí stejnou třídu grafů [3] .
Definice 2 . Graf je sérioparalelní, pokud jej lze převést na graf K2 pomocí sekvence následujících operací :
Libovolný paralelně sekvenční graf má šířku stromu a šířku větvení nepřesahující 2 [4] . Ve skutečnosti má graf šířku stromu nanejvýš 2 tehdy a jen tehdy, když má šířku větve maximálně 2, a také tehdy a jen tehdy, když je nějaká bipropojená složka grafem paralelní série [5] [6] . Maximální paralelně-sériové grafy, grafy, ke kterým nelze přidat další hrany bez zničení sérioparalelní struktury, jsou přesně 2-stromy .
Paralelně-sekvenční grafy jsou charakterizovány absencí podgrafu homeomorfního ke grafu K 4 [4] .
Paralelně-sekvenční grafy lze charakterizovat jejich ušním rozkladem [2] .
Paralelně sekvenční grafy lze rozpoznat v lineárním čase [7] a jejich paralelně sekvenční rozklady lze také konstruovat v lineárním čase.
Kromě modelování některých typů elektrických obvodů jsou tyto grafy zajímavé v teorii výpočetní složitosti , protože mnoho standardních problémů na grafech je řešeno v lineárním čase na grafech GTT [8] , včetně nalezení maximální shody , maximální nezávislé množiny , minima dominujícího množina a hamiltonovský doplněk . Některé z těchto obecných problémů s grafy jsou NP-úplné . Důvodem je skutečnost, že pokud jsou známy odpovědi na tyto problémy pro dva paralelně-sériové grafy, pak lze rychle najít odpověď na jejich sériové a paralelní zapojení.
Problém sériového-paralelního grafu se týká problematiky výčtu grafů a ptá se na počet paralelně-sériových grafů, které lze vytvořit z daného počtu hran.
Zobecněné paralelně sekvenční grafy (GPP-grafy) jsou zobecněním paralelně sekvenčních grafů [9] , ve kterých mají grafy stejnou algoritmickou účinnost pro uvedené problémy. Třída OPP grafů zahrnuje paralelně-sériové grafy a vnější rovinné grafy .
OPP grafy lze definovat přidáním třetí operace k odstranění visících vrcholů (vrcholů stupně 1) v Definici 2 . Stejným způsobem lze do Definice 1 přidat následující operaci.
Strom SPQR je struktura, kterou lze definovat pro libovolný graf propojený se 2 vrcholy . Struktura má S uzlů, které jsou analogické sériovému spojení v paralelně-sériových grafech, P uzlů, které jsou analogické paralelnímu spojení paralelně-sériových grafů, a R uzlů, které neodpovídají operacím paralelně-sériových grafů. 2-souvislý graf je paralelně sekvenční právě tehdy, když ve stromu SPQR nejsou žádné R uzly.