Gyűrűs kocka

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.

Gyűrűs kocka
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$
Jelölés	CCCn

Definíció

Az n-ed rendű gyűrűs kocka egy n2ⁿ 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 + e_k , k )

ahol e₁, e₂, …, e_n a kanonikus bázis a $\mathbb {Z} _{2}^{n}$ vektortérben.

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

Tulajdonságok

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

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$.

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

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

Alkalmazások

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 × time² bonyolultsággal rendelkezik sok párhuzamos programozási feladat esetében.