Küp bağlantılı çevrimler - Cube-connected cycles
Olarak grafik teorisi , küp bağlantılı çevrimler bir olan yönsüz küp grafiği her değiştirilmesi suretiyle oluşan, köşe a hiperküp grafik bir yan çevrim . Bu tarafından tanıtılan Preparata ve Vuillemin (1981) , bir olarak kullanım için ağ topolojisi olarak paralel işlem .
Tanım
n düzeyindeki küp bağlantılı döngüler (CCC n ile gösterilir ), 0 ≤ x < 2 n ve 0 ≤ y olan sayı çiftleriyle ( x , y ) indekslenen bir dizi n 2 n düğümden oluşan bir grafik olarak tanımlanabilir. < n . Bu düğümlerin her biri üç komşuya bağlıdır: ( x , ( y + 1) mod n ) , ( x , ( y − 1) mod n ) ve ( x ⊕ 2 y , y ) , burada "⊕" bit bazındadır özel veya ikili sayılar üzerinde işlem.
Bu grafik, aynı zamanda, bir, her köşe değiştirilmesi sonucu olarak yorumlanabilir , n , bir ile boyutlu hiperküp grafik n -vertex döngüsü. Hiperküp grafik köşeleri x sayılarıyla ve her döngü içindeki konumlar y sayılarıyla endekslenir .
Özellikleri
Küp bağlı düzenin döngüleri N olan Cayley grafiktir a grubunun hareket uzunluğu ikili kelime n ile dönme ve kelime çevirme biti. Gruptan bu Cayley grafiğini oluşturmak için kullanılan jeneratörler, kelimeyi bir pozisyon sola, bir pozisyon sağa döndürerek veya ilk bitini çevirerek hareket eden grup elemanlarıdır. Bu bir Cayley grafiği olduğu için, köşe-geçişlidir : herhangi bir köşeyi başka bir köşeye eşleyen grafiğin bir simetrisi vardır.
Çapı düzenin küp bağlı döngüleri N olan 2 n- 2 - + ⌊n / 2⌋ , herhangi bir n ≥ 4 ( x , y ) noktasından en uzak nokta (2 n − x − 1, ( y + n /2) mod n ). Sýkora ve Vrťo (1993) göstermiştir geçiş sayısı CCC n değerinin ((1/20) + o (1)) 4 N .
Lovász varsayımına göre , küp bağlantılı çevrim grafiği her zaman bir Hamilton çevrimi içermelidir ve bunun artık doğru olduğu bilinmektedir. Daha genel olarak, bu grafikler pansiklik olmasa da , sınırlı sayıda olası çift uzunluk dışında tüm döngüleri içerirler ve n tek olduğunda, olası tek döngü uzunluklarının çoğunu da içerirler.
Paralel işleme uygulaması
Küp bağlantılı çevrimler, bu grafikleri paralel bir bilgisayarda işlemcileri birbirine bağlayan bir ağın ara bağlantı modeli olarak uygulayan Preparata ve Vuillemin (1981) tarafından incelenmiştir . Bu uygulamada, küp bağlantılı çevrimler, işlemci başına yalnızca üç bağlantı gerektirirken hiperküplerin bağlantı avantajlarına sahiptir. Preparata ve Vuillemin, bu ağa dayalı bir düzlemsel yerleşimin , birçok paralel işleme görevi için optimal alan × zaman 2 karmaşıklığına sahip olduğunu gösterdi .
Notlar
Referanslar
- Akers, Sheldon B.; Krishnamurthy, Balakrishnan (1989), "Simetrik ara bağlantı ağları için bir grup teorik modeli", Bilgisayarlarda IEEE İşlemleri , 38 (4): 555–566, doi : 10.1109/12.21148.
- Annexstein, Fred; Baumslag, Marc; Rosenberg, Arnold L. (1990), "Grup eylem grafikleri ve paralel mimariler", SIAM Journal on Computing , 19 (3): 544–569, doi : 10.1137/0219037.
- Friš, Ivan; Havel, İvan; Liebl, Petr (1997), "Küp bağlantılı döngülerin çapı", Bilgi İşlem Mektupları , 61 (3): 157–160, doi : 10.1016/S0020-0190(97)00013-6.
- Germa, Anne; Heydemann, Marie-Claude; Sotteau, Dominique (1998), "Cycles in the cube-connected cycles grafiği", Discrete Applied Mathematics , 83 (1–3): 135–155, doi : 10.1016/S0166-218X(98)80001-2 , MR 1622968.
- Preparata, Franco P. ; Vuillemin, Jean (1981), "Küp bağlantılı çevrimler: paralel hesaplama için çok yönlü bir ağ", Communications of the ACM , 24 (5): 300–309, doi : 10.1145/358645.358660 , hdl : 2142/74219.
- Sikora, Ondrej; Vrťo, Imrich (1993), "Hiperküplerin ve kübe bağlı döngülerin çapraz sayıları üzerinde", BIT Numerical Mathematics , 33 (2): 232–237, doi : 10.1007/BF01989746 , hdl : 11858/00-001M-0000-002D- 92E4-9.