În teoria grafurilor, grafurile paralel-secvențiale sunt grafuri cu două vârfuri diferite, care se numesc terminal , formate recursiv folosind două operații simple [1] . Aceste grafice pot fi utilizate pentru modelarea conexiunii în serie și paralelă a circuitelor electrice .
În acest context, conceptul de graf implică un multigraf .
Există mai multe moduri de a defini grafice paralele-secvențiale. Următoarea definiție se bazează în principal pe definiția lui David Eppstein [2] .
Un graf cu o pereche de terminale (STP) este un graf care are două vârfuri distincte s și t etichetate , numite sursă și respectiv sink .
O conexiune paralelă Pc = Pc(X,Y) a două grafice GTP care nu se intersectează X și Y este un grafic cu o pereche de terminale, creat prin combinarea graficelor X și Y prin îmbinarea surselor X și Y pentru a forma sursa Pc și fuzionarea chiuvetelor X și Y pentru a forma sink al graficului Pc .
Conexiunea serială Sc = Sc(X,Y) a două grafice GST care nu se intersectează X și Y este graficul GST creat prin unirea graficelor X și Y prin fuzionarea chiuvei X cu sursa Y . Sursa graficului X devine sursa lui Sc , iar chiuveta graficului Y devine sursa lui Sc .
Un grafic serial-paralel cu o pereche de terminale (graf PSPP) este un grafic care poate fi obținut ca rezultat al conexiunilor seriale și paralele ale unui set de copii ale graficelor K 2 cu o singură muchie cu vârfuri terminale alocate.
Definiția 1 . Se spune că un grafic este paralel-serial dacă este un POTP și două dintre nodurile sale sunt etichetate ca sursă și cadă.
În mod similar, se pot defini digrafe seriale-paralele , care sunt construite din copii ale graficelor direcționate cu un arc, caz în care arcul este direcționat de la sursă la chiuvetă.
Următoarea definiție oferă aceeași clasă de grafice [3] .
Definiția 2 . Un grafic este serial-paralel dacă poate fi transformat într-un grafic K 2 folosind o succesiune a următoarelor operații:
Orice grafic paralel-secvențial are o lățime a arborelui și o lățime a ramificației care nu depășește 2 [4] . De fapt, un graf are lățimea arborelui de cel mult 2 dacă și numai dacă are lățimea ramurilor de cel mult 2 și, de asemenea, dacă și numai dacă orice componentă biconectată este un graf paralel-serial [5] [6] . Graficele maxime paralel-seriale, grafice la care nu se pot adăuga muchii suplimentare fără a distruge structura serial-paralelă, sunt exact 2-arbori .
Graficele paralel-secvențiale sunt caracterizate prin absența unui subgraf homeomorf cu graficul K 4 [4] .
Graficele paralel-secvențiale pot fi caracterizate prin descompunerea urechii lor [2] .
Graficele paralel-secvențiale pot fi recunoscute în timp liniar [7] și descompunerea lor paralel-secvențială pot fi, de asemenea, construite în timp liniar.
Pe lângă modelarea unor tipuri de circuite electrice, aceste grafice sunt de interes în teoria complexității computaționale , deoarece multe probleme standard pe grafice sunt rezolvate în timp liniar pe grafice GTT [8] , inclusiv găsirea potrivirii maxime , a mulțimii independente maxime , a dominanței minime. mulţime şi complement hamiltonian . Unele dintre aceste probleme generale ale graficului sunt NP-complete . Motivul pentru aceasta este faptul că, dacă răspunsurile la aceste probleme sunt cunoscute pentru două grafice paralel-seriale, atunci se poate găsi rapid răspunsul pentru conexiunile lor seriale și paralele.
Problema graficului serial-paralel se referă la problema enumerarii grafurilor și întreabă despre numărul de grafuri paralel-seriale care pot fi formate dintr-un număr dat de muchii.
Graficele generalizate paralel-secvențiale (GPP-graphs) sunt o generalizare a graficelor paralel-secvențiale [9] în care graficele au aceeași eficiență algoritmică pentru problemele menționate. Clasa de grafice OPP include grafice paralele-seriale și grafice exterioare .
Graficele OPP pot fi definite prin adăugarea unei a treia operații pentru a elimina vârfurile atârnate (vârfurile de gradul 1) în Definiția 2 . În același mod, următoarea operație poate fi adăugată la Definiția 1 .
Un arbore SPQR este o structură care poate fi definită pentru un grafic arbitrar conectat cu 2 vârfuri . Structura are S noduri care sunt analoge unei conexiuni seriale în graficele paralel-seriale, P noduri care sunt analoge cu o conexiune paralelă a graficelor paralel-seriale și R noduri care nu corespund operațiilor graficelor paralel-seriale. Un graf cu două conexiuni este paralel-secvențial dacă și numai dacă nu există noduri R în arborele SPQR.