Gyűrűs kocka

A Wikipédiából, a szabad enciklopédiából
Gyűrűs kocka
Cube-connected cycles.svg
A harmadrendű gyűrűs kocka megegyezik a csonkított kocka élgráfjával

Csúcsok száma n2n
Élek száma 2n-13n
Átmérő \scriptstyle 2n\, +\, \lfloor n/2\rfloor \,-\, 2

Gyűrűs kocka névvel illetik a gráfelméletben azokat az irányítatlan gráfokat, amik úgy keletkeznek, hogy hiperkockagráf csúcsait cserélik le körgráfokra. Először Preparata és Vuillemin vezették be a fogalmat hálózati topológiaként a párhuzamos algoritmusok vizsgálatakor.[1][2]

Definíció[szerkesztés | forrásszöveg szerkesztése]

Az n-ed rendű gyűrűs kocka egy n2n csúcsú G=(V,E) gráf, melynek csúcshalmaza

V = \mathbb{Z}_2^n  \times \mathbb{Z}_n

és minden ( v , k ) csúcsnak három szomszédja van:

  1. ( v , k + 1 ) (mod n)
  2. ( v , k - 1 ) (mod n)
  3. ( v + ek , k )

ahol e1, e2, …, en a kanonikus bázis a \mathbb{Z}_2^n vektortérben.

Az n-ed rendű gyűrűs kockára a CCCn jelölést szokták használni, ami az angol cube-connected cycles elnevezés rövidítése.

Tulajdonságok[szerkesztés | forrásszöveg szerkesztése]

A definíció következménye, hogy a gyűrűs kockák 3-reguláris gráfok, sőt csúcstranzitívak is.

Az Friš és Havel bizonyították, hogy az n-ed rendű gyűrűs kocka átmérője minden n≥4 esetben \scriptstyle 2n\, +\, \lfloor n/2\rfloor \,-\, 2.[3]

A keresztezési szám (1+o(1))4n/20.[4]

Bizonyították azt is, hogy a gyűrűs kocka Cayley-gráfként is generálható.[5] [6]

Alkalmazások[szerkesztés | forrásszöveg szerkesztése]

A gyűrűs kockákat Preparata és Vuillemin alkalmazta hálózati topológiaként egy párhuzamos számítógép processzorainak összekapcsolására. Ebben az alkalmazásban a gyűrűs kockák rendelkeznek a hiperkockák előnyös tulajdonságaival, továbbá fokszámuk n-től független konstans, minden processzornak csak három másikhoz kell kapcsolódnia. Megmutatták, hogy ez a topológia optimális area × time2 bonyolultsággal rendelkezik sok párhuzamos programozási feladat esetében.[1]

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

  1. ^ a b Preparata, Franco P. & Vuillemin, Jean (1981), "The cube-connected cycles: a versatile network for parallel computation", Communications of the ACM 24 (5): 300–309, DOI 10.1145/358645.358660
  2. Angol-magyar informatikai szótár. tankonyvtar.hu. (Hozzáférés: 2010. április 10.)
  3. Friš, Ivan; Havel, Ivan & Liebl, Petr (1997), "The diameter of the cube-connected cycles", Information Processing Letters 61 (3): 157–160, DOI 10.1016/S0020-0190(97)00013-6
  4. Sýkora, Ondrej & Vrťo, Imrich (1993), "On crossing numbers of hypercubes and cube connected cycles", BIT Numerical Mathematics 33 (2): 232–237, DOI 10.1007/BF01989746
  5. Akers, Sheldon B. & Krishnamurthy, Balakrishnan (1989), "A group-theoretic model for symmetric interconnection networks", IEEE Transactions on Computers 38 (4): 555–566, DOI 10.1109/12.21148
  6. Annexstein, Fred; Baumslag, Marc & Rosenberg, Arnold L. (1990), "Group action graphs and parallel architectures", SIAM Journal on Computing 19 (3): 544–569, DOI 10.1137/0219037