Soros-párhuzamos gráf
A matematika, azon belül a gráfelmélet területén a soros-párhuzamos gráfok (series-parallel graphs) két kitüntetett, terminális csúcs között két egyszerű kompozíciós művelettel rekurzívan létrehozható gráfok. Felhasználhatók a soros és párhuzamos áramkörök modellezésére.
Definíció és terminológia[szerkesztés]
Ebben a kontextusban a gráf alatt multigráfot értünk.
A soros-párhuzamos gráfokat többféleképpen szokás definiálni; a következő definíció a David Eppstein által használt megoldást követi.[1]
Egy két terminálú gráf (two-terminal graph, TTG) a két megkülönböztetett csúccsal, az s forrással, illetve a t nyelővel rendelkező gráf.
Két TTG, X és Y párhuzamos kompozíciója, Pc = Pc(X,Y) az X és Y gráfok diszjunkt uniójaként áll elő, ahol az X és Y forrásának egyesítésével áll elő a Pc forrása és az X és Y nyelőjének egyesítésével áll elő a Pc nyelője.
Két TTG, X és Y soros kompozíciója, Sc = Sc(X,Y) az X és Y gráfok diszjunkt uniójaként áll elő, ahol X nyelőjét Y forrásával egyesítjük. Az X forrása így az Sc forrása lesz, Y nyelője pedig az Sc nyelője.
Egy két terminálos soros-párhuzamos gráf (two-terminal series-parallel graph, TTSPG) olyan gráf, ami előállítható a soros, illetve párhuzamos kompozíciók sorozatával, ha a kiindulási gráfok az egy élből álló K2, kijelölt terminálokkal ellátott egyetlen élből álló gráf kópiái.
Definíció 1. Végül, egy gráfot akkor nevezünk soros-párhuzamos gráfnak (sp-gráf), ha az egy TTSPG, melynek 1-1 csúcsát forrásnak, illetve nyelőnek tekintjük.
Hasonló módon lehet definiálni az irányított soros-párhuzamos gráfokat, melyek egyetlen irányított élből álló gráfokból konstruálhatók, ahol az irányított élek a forrástól a nyelő felé mutatnak.
Alternatív definíció[szerkesztés]
A következő definíció ugyanezt a gráfcsaládot határozza meg.[2]
Definíció 2. Egy gráf sp-gráf, ha előállítható belőle a K2 a következő műveletek egy sorozatával:
- Két párhuzamos él cseréje a közös végpontokat összekötő egyetlen éllel
- Egy 2 fokszámú csúcsra (az s és t kivételével) illeszkedő élpár cseréje egyetlen élre.
Tulajdonságok[szerkesztés]
A soros-párhuzamos gráfok faszélessége legfeljebb 2, és elágazás-felbontásának minimális szélessége (branchwidth) szintén legfeljebb 2.[3] Valóban, egy gráf faszélessége pontosan akkor legfeljebb 2, ha elágazás-felbontásának minimális szélessége legfeljebb 2, ami pedig akkor áll fenn, ha minden kétszeresen összefüggő komponense soros-párhuzamos gráf.[4][5] A maximális soros-párhuzamos gráfok, melyekhez nem adható hozzá új él a soros-párhuzamos tulajdonság elrontása nélkül, éppen a 2-fák.
A soros-párhuzamos gráfok jellemezhetők úgy, mint a gráfok, melyek nem tartalmaznak a K4 teljes gráffal homeomorf részgráfot.[3]
A soros-párhuzamos gráfok jellemezhetők fülfelbontásaik segítségével is.[1]
Soros-párhuzamos gráfokkal kapcsolatos kutatások[szerkesztés]
A soros-párhuzamos gráfok lineáris időben felismerhetők[6] és lineáris időben a soros-párhuzamos felbontásuk is előállítható.
Amellett, hogy elektromos áramkörök egy fajtájának modelljét adják, ezek a gráfok a számítási bonyolultságelmélet érdeklődésére is számot tartanak, mivel számos általános gráfprobléma lineáris időben megoldható rajtuk,[7] köztük a maximális párosítás, a maximális elemszámú független halmaz, a minimális domináló halmaz és a Hamilton-körré kiegészítés megkeresése. Ezek egy része általános gráfokra NP-teljes nehézség. A megoldás arra a tényre alapoz, hogy ha két soros-párhuzamos gráfra ismert ezeknek a problémáknak a megoldása, akkor gyorsan megtalálható a két gráf soros, illetve párhuzamos kompozícióira is.
A soros-párhuzamos hálózatok problémája olyan leszámlálási probléma, ami adott számú élen létrehozható soros-párhuzamos gráfok számára kérdez rá.
Általánosítása[szerkesztés]
Az általánosított soros-párhuzamos gráfok (GSP-graphs) a soros-párhuzamos gráfok kiterjesztései,[8] melyek megtartják az említett problémákra vonatkozó algoritmikus hatékonyságot. A GSP-gráfok közé tartoznak a soros-párhuzamos gráfok mellett a külsíkgráfok is.
A GSP-gráfok meghatározhatók a Definíció 2 egy harmadik művelettel való kiegészítésével, ez az 1. fokú, „lógó” csúcsok törlése.
Egy SPQR-fa tetszőleges 2-összefüggő gráf esetén definiálható fastruktúra. Rendelkezik a soros-párhuzamos gráfok soros kompozíció műveletének megfelelő S csúcsokkal, a párhuzamos kompozíció műveletének megfelelő P csúcsokkal, és a kompozíciós műveletekkel nem összefüggő R csúcsokkal. Egy 2-összefüggő gráf pontosan akkor soros-párhuzamos gráf, ha SPQR-fájában nem találhatók R csúcsok.
Kapcsolódó szócikkek[szerkesztés]
Fordítás[szerkesztés]
- Ez a szócikk részben vagy egészben a Series-parallel graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Jegyzetek[szerkesztés]
- ↑ a b Eppstein, David (1992). „Parallel recognition of series-parallel graphs”. Information and Computation 98 (1), 41–55. o. DOI:10.1016/0890-5401(92)90041-D.
- ↑ Duffin, R. J. (1965). „Topology of Series-Parallel Networks”. Journal of Mathematical Analysis and Applications 10 (2), 303–313. o. DOI:10.1016/0022-247X(65)90125-3.
- ↑ a b Graph classes: a survey, SIAM Monographs on Discrete Mathematics. and Applications. Philadelphia, PA: Society for Industrial and Applied Mathematics, 172–174. o. (1999). ISBN 978-0-898714-32-6
- ↑ (1998) „A partial k-arboretum of graphs with bounded treewidth”. Theoretical Computer Science 209 (1–2), 1–45. o. DOI:10.1016/S0304-3975(97)00228-4.
- ↑ (2002) „On matroids of branch-width three”. Journal of Combinatorial Theory, Series B 86 (1), 148–171. o. DOI:10.1006/jctb.2002.2120.
- ↑ Valdes, Jacobo; Tarjan, Robert E.; Lawler, Eugene L. (1982). „The recognition of series parallel digraphs”. SIAM Journal on Computing 11 (2), 289–313. o. DOI:10.1137/0211023.
- ↑ (1982) „Linear-time computability of combinatorial problems on series-parallel graphs”. Journal of the ACM 29 (3), 623–641. o. DOI:10.1145/322326.322328.
- ↑ Korneyenko, N. M. (1994). „Combinatorial algorithms on a class of graphs”. Discrete Applied Mathematics 54 (2–3), 215–217. o. DOI:10.1016/0166-218X(94)90022-1. Translated from Notices of the BSSR Academy of Sciences, Ser. Phys.-Math. Sci., (1984) no. 3, pp. 109–111 (oroszul)