WikiDer > Текшеге қосылған циклдар

Cube-connected cycles
А-ның төбелерінде геометриялық түрде орналасқан 3 тәрізді текшеге байланысты циклдар кесілген текше.

Жылы графтар теориясы, текшеге байланысты циклдар болып табылады бағытталмаған текше график, әрқайсысын ауыстыру арқылы қалыптасады шың а гиперкубтық график а цикл. Ол енгізілді Preparata & Vuillemin (1981) ретінде пайдалану үшін желілік топология жылы параллель есептеу.

Анықтама

Реттеудің текшеге байланысты циклдары n (CCC деп белгілендіn) жиынтығынан құрылған график ретінде анықтауға болады n2n жұп сандармен индекстелген түйіндер (х, ж) мұндағы 0 ≤ х < 2n және 0 ж < n. Әрбір осындай түйін үш көршімен байланысты: (х, (ж + 1) мод n), (х, (ж - 1) мод n), және (х ⊕ 2ж, ж), мұндағы «⊕» таңбаны білдіреді биттік эксклюзивті немесе екілік сандармен жұмыс.

Бұл графикті сонымен қатар әр an төбесін ауыстыру нәтижесі ретінде түсіндіруге болады n-өлшемді гиперкуб графигі n-тексіз цикл. Гиперкуба графының төбелері сандармен индекстеледі х, және сандар бойынша әр циклдегі позициялар ж.

Қасиеттері

Реттеудің текшеге байланысты циклдары n болып табылады Кейли графигі а топ бұл әрекет етеді ұзындықтың екілік сөздерінде n арқылы айналу және сөздің басқа бөліктері.[1] Осы Кейли графигін топтан құру үшін пайдаланылған генераторлар дегеніміз - сөзді бір позиция солға бұру, оны бір позицияға оңға бұру немесе оның алғашқы битін айналдыру арқылы әрекет ететін топ элементтері. Бұл Кэйли графигі болғандықтан, солай шың-өтпелі: кез-келген шыңды кез-келген шыңға бейнелейтін графиктің симметриясы бар.

The диаметрі текшеге байланысты реттілік циклдарының n болып табылады 2n + ⌊N / 2⌋ - 2 кез келген n ≥ 4 үшін; бастап ең алыс нүктех, ж) болып табылады (2n − х − 1, (ж + n/ 2) модn).[2] Sykora & Vrťo (1993) екенін көрсетті қиылысу нөмірі CCCn бұл ((1/20) + o (1)) 4n.

Сәйкес Ловас болжам, текшеге қосылған цикл графикасында әрқашан a болуы керек Гамильтон цикліжәне бұл енді шындық екені белгілі болды. Жалпы, бұл графиктер жоқ болса да панциклді, олар барлық мүмкін циклдардан тұрады, бірақ мүмкін болатын ұзындықтың шектелген санынан және қашан n олар тақтардың көптеген ықтимал тақ ұзындықтарын қамтиды.[3]

Параллельді өңдеу қосымшасы

Текшеге байланысты циклдар зерттелді Preparata & Vuillemin (1981), кім бұл графиктерді өзара байланыс үлгісі а желі а процессорларын қосу параллель компьютер. Бұл қосымшада текшеге қосылған циклдар гиперкубалардың қосылу артықшылықтарына ие, ал бір процессорға тек үш қосылым қажет. Preparata және Vuillemin осы желіге негізделген жазықтық орналасудың оңтайлы ауданы × уақыт болатынын көрсетті2 көптеген қатарлас өңдеу тапсырмаларының күрделілігі.

Ескертулер

  1. ^ Akers & Krishnamurthy (1989); Аннексштейн, Баумслаг және Розенберг (1990).
  2. ^ Фриш, Гавел және Либл (1997).
  3. ^ Герма, Хейдеманн және Сотто (1998).

Пайдаланылған әдебиеттер

  • Акерс, Шелдон Б .; Кришнамурти, Балакришнан (1989), «Симметриялы байланыс тораптарының топтық-теориялық моделі», Компьютерлердегі IEEE транзакциялары, 38 (4): 555–566, дои:10.1109/12.21148.
  • Аннексштейн, Фред; Баумслаг, Марк; Розенберг, Арнольд Л. (1990), «Топтық әрекет графиктері және параллель архитектуралар», Есептеу бойынша SIAM журналы, 19 (3): 544–569, дои:10.1137/0219037.
  • Фриш, Иван; Гавел, Иван; Либл, Петр (1997), «Кубқа қосылған циклдардың диаметрі», Ақпаратты өңдеу хаттары, 61 (3): 157–160, дои:10.1016 / S0020-0190 (97) 00013-6.
  • Джерма, Анна; Хейдеман, Мари-Клод; Сотто, Доминик (1998), «Текшеге байланысты циклдар графигіндегі циклдар», Дискретті қолданбалы математика, 83 (1–3): 135–155, дои:10.1016 / S0166-218X (98) 80001-2, МЫРЗА 1622968.
  • Предата, Франко П.; Вюллемин, Жан (1981), «Кубқа қосылған циклдар: параллельді есептеу үшін жан-жақты желі», ACM байланысы, 24 (5): 300–309, дои:10.1145/358645.358660, hdl:2142/74219.
  • Сыкора, Ондрей; Vrťo, Imrich (1993), «Гиперкубтар мен кубтардың байланысты циклдарының қиылысуы туралы», BIT Сандық математика, 33 (2): 232–237, дои:10.1007 / BF01989746, hdl:11858 / 00-001M-0000-002D-92E4-9.