A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
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ő | |
Jelölés | CCCn |
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ó
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 .[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
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.[1]
Jegyzetek
- ↑ 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
- ↑ Angol-magyar informatikai szótár. tankonyvtar.hu. (Hozzáférés: 2010. április 10.)
- ↑ 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
- ↑ 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
- ↑ 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
- ↑ 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
A lap szövege Creative Commons Nevezd meg! – Így add tovább! 3.0 licenc alatt van; egyes esetekben más módon is felhasználható. Részletekért lásd a felhasználási feltételeket.
Épületirányító rendszer
Útválasztás
Útválasztó
Ütközési tartomány
100Base-FX
100Base-T4
100Base-TX
Arcnet hálózatok
ARPANET
Avaya
Az adatáteresztő képesség mérése
C3 Kulturális és Kommunikációs Központ
CAN-busz
ChatFlow
Cheeger-állandó
Cisco IOS
Common Object Request Broker Architecture
Csomagtovábbítás
Csomag (informatika)
Dataizmus
Dinamikus DNS
Ethernet
Fordított proxy
Forgalomgeneráló modell
Gazdagép
Gyűrűs kocka
Gyors Ethernet
Hálózati címfordítás
Hálózati híd
Hálózati szegmens
Helyi hálózat
Hub (hálózat)
IEEE 802
Intranet
Iperf
Kábelmodem
Kliens
Kvantumhálózat
Localhost
LogMeIn Hamachi
MAC-cím
Magánhálózat
Manchesteri kódolás
Megjelenítési réteg
Modem
Munkamenet
Nagy kiterjedésű hálózat
OSI-modell
Pleziokron digitális hierarchia
Porttovábbítás
Repeater
Squid
Switch (informatika)
System Fault Tolerant
Számítógép-hálózat
Számítógépfürt
Szórási tartomány
Személyi hálózat
Szerver
Szinkron digitális hierarchia
Tűzfal (számítástechnika)
Time to Live
Token-Ring
Tokenbusz
Token busz
Unicast
UTP
Válogatás nélküli üzemmód
Városi hálózat
Varnish
Virtuális helyi hálózat
Virtuális magánhálózat
Windows Internet Name Service
X.25
A lap szövege Creative Commons Nevezd meg! – Így add tovább! 3.0 licenc alatt van; egyes esetekben más módon is felhasználható. Részletekért lásd a felhasználási feltételeket.