Skládaný krychlový graf - Folded cube graph - Wikipedia

Skládaný krychlový graf
Clebsch hypercube.svg
Skládaný krychlový graf řádu 5 (tj Clebschův graf ).
Vrcholy2n−1
Hrany2n−2n
Průměrpodlaha(n/2)
Chromatické číslo2 (pro sudé n) nebo 4 (je-li liché).
VlastnostiPravidelný graf
Hamiltonian
Přechodná vzdálenost.
Tabulka grafů a parametrů

v teorie grafů, a skládaný krychlový graf je neorientovaný graf vytvořený z a hyperkrychlový graf přidáním k tomu a perfektní shoda který spojuje naproti páry vrcholů hyperkrychlí.

Konstrukce

Přeložený krychlový graf objednávky k (obsahující 2k − 1 vrcholy) mohou být vytvořeny přidáním hran mezi protilehlé páry vrcholů v hyperkrychlovém grafu řádu k - 1. (V hyperkrychli s 2n vrcholy, dvojice vrcholů jsou naproti pokud nejkratší cesta mezi nimi má délku n.) Může být ekvivalentně vytvořen z hyperkrychlového grafu (také) řádu k, který má dvakrát tolik vrcholů, o identifikace společně (nebo uzavírat smlouvy) každý protilehlý pár vrcholů.

Vlastnosti

Objednávka-k složený krychlový graf je k-pravidelný s 2k − 1 vrcholy a 2k − 2k hrany.

The chromatické číslo objednávky-k složený krychlový graf je dva, když k je sudé (tj. v tomto případě je to graf bipartitní ) a čtyři, když k je zvláštní.[1] The zvláštní obvod skládané kostky lichého pořadí je k, takže pro zvláštní k větší než tři skládané krychlové grafy poskytují třídu grafy bez trojúhelníků s chromatickým číslem čtyři a libovolně velkým lichým obvodem. Jako vzdálenost-pravidelný graf s lichým obvodem k a průměr (k - 1) / 2, skládané kostky lichého pořadí jsou příklady zobecněné liché grafy.[2]

Když k je zvláštní, dvojdílný dvojitý kryt objednávky-k složená kostka je objednávka-k kostka, ze které byla vytvořena. Kdy však k je sudý,k kostka je a dvojitý kryt ale ne bipartitní dvojitý kryt. V tomto případě je složená kostka již sama o sobě bipartitní. Skládané krychlové grafy dědí ze svých hyperkrychlí podgrafy vlastnost mít a Hamiltonovský cyklus a z hyperkrychlí, které je zdvojnásobují, je vlastnost být a vzdálenost-tranzitivní graf.[3]

Když k je zvláštní, objednávkak skládaná kostka obsahuje jako podgraf a kompletní binární strom s 2k - 1 uzel. Kdy však k je sudé, to není možné, protože v tomto případě je složená kostka bipartitní graf se stejným počtem vrcholů na každé straně bipartice, velmi odlišný od poměru téměř dvou ku jedné pro bipartici celého binárního stromu .[4]

Příklady

Aplikace

v paralelní výpočty, skládané krychlové grafy byly studovány jako potenciál topologie sítě, jako alternativa k hyperkrychli. Ve srovnání s a hyperkrychle, a skládaná kostka se stejným počtem uzlů má téměř stejný vrchol, ale pouze polovinu průměr. Účinný distribuované algoritmy (ve vztahu k těm pro a hyperkrychle) jsou známé pro vysílání informací ve složené krychli.[5]

Viz také

Poznámky

  1. ^ Godsil (2004) poskytne důkaz a výsledek připsá Naserasrovi a Tardifovi.
  2. ^ Van Dam & Haemers (2010).
  3. ^ van Bon (2007).
  4. ^ Choudam & Nandini (2004).
  5. ^ El-Amawy & Latifi (1991); Varvarigos (1995).

Reference

  • van Bon, John (2007), „Konečné primitivní grafy vzdálenosti a přechodu“, European Journal of Combinatorics, 28 (2): 517–532, doi:10.1016 / j.ejc.2005.04.014.
  • Choudam, S. A .; Nandini, R. Usha (2004), „Kompletní binární stromy ve složených a vylepšených kostkách“, Sítě, 43 (4): 266–272, doi:10,1002 / net.20002.
  • Van Dam, Edwin; Haemers, Willem H. (2010), Zvláštní charakteristika zobecněných zvláštních grafů, Diskusní papír CentER, řada 2010-47, SSRN  1596575.
  • El-Amawy, A .; Latifi, S. (1991), "Vlastnosti a výkon skládaných hyperkrychlí", IEEE Trans. Paralelní distribuce Syst., 2 (1): 31–42, doi:10.1109/71.80187.
  • Godsil, Chris (2004), Zajímavé grafy a jejich zbarvení, CiteSeerX  10.1.1.91.6390.
  • Varvarigos, E. (1995), "Efektivní směrovací algoritmy pro sítě ve složených krychlích", Proc. 14. Int. Phoenix Conf. o počítačích a komunikacích, IEEE, s. 143–151, doi:10.1109 / PCCC.1995.472498.

externí odkazy