Hypercube graf - Hypercube graph

Hypercube graf
Hyperkrychlový graf Q4
Vrcholy	2n
Hrany	2n−1n
Průměr	n
Obvod	4 -li n ≥ 2
Automorfismy	n! 2n
Chromatické číslo	2
Spektrum	${displaystyle {(n-2k) ^ {jiné {n} {k}}; k = 0, ldots, n}}$
Vlastnosti	Symetrický Vzdálenost pravidelná Jednotková vzdálenost Hamiltonian Bipartitní
Zápis	Qn
Tabulka grafů a parametrů

v teorie grafů, hyperkrychlový graf Q_n je graf vytvořený z vrcholů a hran an n-dimenzionální hyperkrychle. Například krychlový graf Q₃ je graf tvořený 8 vrcholy a 12 hranami trojrozměrné krychle.Q_n má 2ⁿ vrcholy, 2ⁿ⁻¹n hrany, a je a běžný graf s n hrany dotýkající se každého vrcholu.

Hyperkrychlový graf Q_n mohou být také vytvořeny vytvořením vrcholu pro každého podmnožina z n-prvková sada se dvěma vrcholy sousedícími, když se jejich podmnožiny liší v jednom prvku, nebo vytvořením vrcholu pro každý n-číslice binární číslo, se dvěma vrcholy sousedícími, když se jejich binární reprezentace liší v jedné číslici. To je n-složit kartézský součin ze dvou vrcholů kompletní graf a lze jej rozložit na dvě kopie Q_{n − 1} vzájemně propojeny a perfektní shoda.

Hypercube grafy by neměly být zaměňovány s kubické grafy, což jsou grafy, které mají přesně tři hrany dotýkající se každého vrcholu. Jediný hyperkrychlový graf Q_n to je kubický graf je kubický graf Q₃.

Konstrukce

Konstrukce Q₃ spojením párů odpovídajících vrcholů ve dvou kopiích Q₂

Hyperkrychlový graf Q_n mohou být vyrobeny z rodiny podmnožiny a soubor s n prvky vytvořením vrcholu pro každou možnou podmnožinu a spojením dvou vrcholů hranou, kdykoli se odpovídající podmnožiny liší v jediném prvku. Ekvivalentně to může být konstruováno pomocí 2ⁿ vrcholy označené n-bit binární čísla a spojením dvou vrcholů hranou, kdykoli Hammingova vzdálenost jejich štítků je jedna. Tyto dvě konstrukce spolu úzce souvisejí: binární číslo lze interpretovat jako množinu (množina pozic, kde má a 1 číslice) a dvě takové sady se liší v jednom prvku, kdykoli mají odpovídající dvě binární čísla Hammingovu vzdálenost jedna.

Alternativně, Q_n mohou být vyrobeny z disjunktní unie dvou hyperkrychlí Q_{n − 1}, přidáním hrany z každého vrcholu v jedné kopii Q_{n − 1} na odpovídající vrchol v druhé kopii, jak je znázorněno na obrázku. Spojovací hrany tvoří a perfektní shoda.

Další konstrukce Q_n je kartézský součin z n dva vrcholy kompletní grafy K.₂. Obecněji se kartézský součin kopií úplného grafu nazývá a Hammingův graf; hyperkrychlové grafy jsou příklady Hammingových grafů.

Příklady

Graf Q₀ se skládá z jediného vrcholu, zatímco Q₁ je kompletní graf na dvou vrcholech a Q₂ je cyklus délky4.

Graf Q₃ je 1-kostra a krychle, a krychlový graf, rovinný graf s osmi vrcholy a dvanáct hrany.

Graf Q₄ je Leviho graf z Möbiova konfigurace. Je to také rytířský graf pro toroidní ${displaystyle 4 imes 4}$ šachovnice.^[1]

Vlastnosti

Bipartitita

Každý hyperkrychlový graf je bipartitní: to může být barevný pouze se dvěma barvami. Dvě barvy tohoto zbarvení lze najít z konstrukce podmnožiny grafů hyperkrychlí tak, že dáte jednu barvu podmnožinám, které mají sudý počet prvků, a druhou barvu podmnožinám s lichým počtem prvků.

Hamiltonicita

Každá hyperkrychle Q_n s n > 1 má Hamiltonovský cyklus, cyklus, který navštíví každý vrchol přesně jednou. Navíc, a Hamiltonova cesta existuje mezi dvěma vrcholy u a proti právě když mají různé barvy v a 2-barvení grafu. Obě skutečnosti lze snadno dokázat pomocí principu indukce na dimenzi hyperkrychle a konstrukci grafu hyperkrychle spojením dvou menších hyperkrychlí se shodou.

Hamiltonicita hyperkrychle úzce souvisí s teorií Šedé kódy. Přesněji existuje bijektivní korespondence mezi sadou n-bitové cyklické šedé kódy a sada hamiltonovských cyklů v hyperkrychli Q_n.^[2] Obdobná vlastnost platí pro acykliku n-bitové šedé kódy a hamiltonovské cesty.

Méně známým faktem je, že každá dokonalá shoda v hyperkrychle sahá až do Hamiltonovského cyklu.^[3] Otevřeným problémem zůstává otázka, zda se každá shoda vztahuje na Hamiltonovský cyklus.^[4]

Další vlastnosti

Hyperkrychlový graf Q_n (pro n > 1) :

• je Hasseův diagram konečný Booleova algebra.
• je střední graf. Každý střední graf je izometrický podgraf hyperkrychle, a může být vytvořen jako zatažení hyperkrychle.
• má více než 2^2n-2 perfektní shody. (toto je další důsledek, který snadno vyplývá z indukční konstrukce.)
• je oblouk tranzitivní a symetrický. Symetrie hyperkrychlových grafů lze reprezentovat jako podepsané permutace.
• obsahuje všechny cykly délky 4, 6, ..., 2ⁿ a je tedy bipancyclic graf.
• může být tažené jako graf jednotkové vzdálenosti v euklidovské rovině pomocí konstrukce hyperkrychlového grafu z podmnožin množiny n prvky, výběr odlišné jednotkový vektor pro každý prvek množiny a umístění vrcholu odpovídající množině S na součtu vektorů v S.
• je ngraf spojený s vrcholem tím, že Balinskiho věta
• je rovinný (může být tažené bez přechodů) právě tehdy n ≤ 3. Pro větší hodnoty n, hyperkrychle má rod (n − 4)2^{n − 3} + 1.^[5][6]
• má přesně ${displaystyle 2 ^ {2 ^ {n} -n-1} prod _ {k = 2} ^ {n} k ^ {n zvolit k}}$ klenout se nad stromy.^[6]
• má šířka pásma přesně ${displaystyle sum _ {i = 0} ^ {n-1} {jiné {i} {lfloor i / 2floor}}}$.^[7]
• má achromatické číslo úměrný ${displaystyle {sqrt {n2 ^ {n}}}}$, ale konstanta proporcionality není přesně známa.^[8]
• má jako vlastní čísla své matice sousedství čísla (−n, −n + 2, −n + 4, ... , n − 4, n − 2, n) a jako vlastní čísla jeho laplaciánské matice čísla (0, 2, ..., 2n). The kvlastní číslo má multiplicitu ${displaystyle {jiný {n} {k}}}$ v obou případech.
• má izoperimetrické číslo h(G) = 1.

Rodina Q_n pro všechny n > 1 je Lévyho rodina grafů

Problémy

Problém najít nejdelší cesta nebo cyklus, který je indukovaný podgraf daného hyperkrychlového grafu je známé jako had-in-the-box problém.

Szymanskiho domněnka se týká vhodnosti hyperkrychle jako a topologie sítě pro komunikaci. Uvádí se, že bez ohledu na to, jak si člověk zvolí a permutace spojením každého vrcholu hyperkrychle s jiným vrcholem, se kterým by měl být spojen, vždy existuje způsob, jak spojit tyto páry vrcholů pomocí cesty které nesdílejí žádnou směrovanou výhodu.^[9]

Viz také

• de Bruijnův graf
• Krychle spojené cykly
• Fibonacciho kostka
• Skládaný krychlový graf
• Frankl – Rödlův graf
• Graf na polovinu krychle
• Topologie sítě Hypercube

Poznámky

Reference

• Harary, F.; Hayes, J. P .; Wu, H.-J. (1988), „An theory of the theory of hypercube graphs“, Počítače a matematika s aplikacemi, 15 (4): 277–289, doi:10.1016/0898-1221(88)90213-1, hdl:2027.42/27522.