Soros-párhuzamos gráf

A soros-párhuzamos gráfok soros és párhuzamos kompozíciós műveletei.

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

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ó

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

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

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

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

Fordítá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

  1. ↑ 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. 
  2. ↑ 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. 
  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 
  4. ↑ (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. 
  5. ↑ (2002) „On matroids of branch-width three”. Journal of Combinatorial Theory, Series B 86 (1), 148–171. o. DOI:10.1006/jctb.2002.2120. 
  6. ↑ 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. 
  7. ↑ (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. 
  8. ↑ 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)

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!