Krychle spojené cykly - Cube-connected cycles

Krychle spojené cykly řádu 3, uspořádané geometricky na vrcholech a zkrácená kostka.

v teorie grafů, cykly spojené s krychlí je neorientovaný kubický graf, vytvořený jejich nahrazením vrchol a hyperkrychlový graf podle a cyklus. To bylo představeno Preparata & Vuillemin (1981) pro použití jako topologie sítě v paralelní výpočty.

Definice

Krychle spojené cykly řádu n (označeno CCCn) lze definovat jako graf vytvořený ze sady n2n uzly, indexované dvojicemi čísel (X, y) kde 0 ≤ X < 2n a 0 ≤ y < n. Každý takový uzel je připojen ke třem sousedům: (X, (y + 1) mod n), (X, (y - 1) mod n), a (X ⊕ 2y, y), kde „⊕“ označuje bitový exkluzivní nebo operace na binárních číslech.

Tento graf lze také interpretovat jako výsledek nahrazení každého vrcholu an n-dimenzionální hyperkrychlový graf pomocí n-vrcholový cyklus. Vrcholy grafu hyperkrychle jsou indexovány podle čísel Xa pozice v každém cyklu podle čísel y.

Vlastnosti

Krychle spojené cykly řádu n je Cayleyův graf a skupina že činy na binární slova délky n podle otáčení a převrácení kousků slova.[1] Generátory použité k vytvoření tohoto Cayleyova grafu ze skupiny jsou prvky skupiny, které působí otočením slova o jednu pozici doleva, otočením o jednu pozici doprava nebo překlopením jeho prvního bitu. Protože je to Cayleyův graf, je vrchol-tranzitivní: existuje symetrie grafu mapujícího jakýkoli vrchol na jakýkoli jiný vrchol.

The průměr řádů cyklů spojených s krychlí n je 2n + ⌊N / 2⌋ - 2 pro libovolné n ≥ 4; nejvzdálenější bod od (X, y) je (2n − X − 1, (y + n/ 2) modn).[2] Sýkora a Vrťo (1993) ukázal, že číslo křížení CCCn je ((1/20) + o (1)) 4n.

Podle Lovász dohad, graf cyklu spojený s krychlí by měl vždy obsahovat a Hamiltonovský cyklus, a to je nyní známo jako pravda. Obecněji, i když tyto grafy nejsou pancyklický, obsahují cykly všech kromě omezeného počtu možných sudých délek a kdy n je liché, obsahují také mnoho možných lichých délek cyklů.[3]

Aplikace pro paralelní zpracování

Cykly spojené s krychlí byly zkoumány pomocí Preparata & Vuillemin (1981), který tyto grafy použil jako vzor propojení a síť připojení procesorů v a paralelní počítač. V této aplikaci mají cykly připojené k datové krychli výhody připojení hyperkrychlí, přičemž vyžadují pouze tři připojení na procesor. Preparata a Vuillemin ukázali, že plošné rozložení založené na této síti má optimální plochu × čas2 složitost mnoha úkolů paralelního zpracování.

Poznámky

  1. ^ Akers & Krishnamurthy (1989); Annexstein, Baumslag & Rosenberg (1990).
  2. ^ Friš, Havel & Liebl (1997).
  3. ^ Germa, Heydemann & Sotteau (1998).

Reference

  • Akers, Sheldon B .; Krishnamurthy, Balakrishnan (1989), „Skupinový teoretický model pro symetrické propojovací sítě“, Transakce IEEE na počítačích, 38 (4): 555–566, doi:10.1109/12.21148.
  • Annexstein, Fred; Baumslag, Marc; Rosenberg, Arnold L. (1990), „Grafy skupinových akcí a paralelní architektury“, SIAM Journal on Computing, 19 (3): 544–569, doi:10.1137/0219037.
  • Friš, Ivan; Havel, Ivan; Liebl, Petr (1997), „Průměr cyklů spojených s krychlí“, Dopisy o zpracování informací, 61 (3): 157–160, doi:10.1016 / S0020-0190 (97) 00013-6.
  • Germa, Anne; Heydemann, Marie-Claude; Sotteau, Dominique (1998), „Cykly v grafu cyklů spojených s krychlí“, Diskrétní aplikovaná matematika, 83 (1–3): 135–155, doi:10.1016 / S0166-218X (98) 80001-2, PAN  1622968.
  • Preparata, Franco P.; Vuillemin, Jean (1981), „Cykly propojené s krychlí: univerzální síť pro paralelní výpočet“, Komunikace ACM, 24 (5): 300–309, doi:10.1145/358645.358660, hdl:2142/74219.
  • Sýkora, Ondřej; Vrťo, Imrich (1993), "O křížení počtu hyperkrychlí a krychlí spojených cyklů", BIT Numerická matematika, 33 (2): 232–237, doi:10.1007 / BF01989746, hdl:11858 / 00-001M-0000-002D-92E4-9.