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.
Definíció Az n-ed rendű gyűrűs kocka egy n2n csúcsú G=(V,E) gráf, melynek csúcshalmaza
és minden ( v , k ) csúcsnak három szomszédja van: ( v , k + 1 ) (mod n) ( v , k - 1 ) (mod n) ( v + ek , k ) ahol e1, e2, ..., en a kanonikus bázis a 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 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 .
A keresztezési szám (1+o(1))4n/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.
Jegyzetek
Kategória:Számítógép-hálózatok Kategória:Gráfelmélet Kategória:Parametrikus gráfcsaládok Kategória:Reguláris gráfok Kategória:Kocka