Dnešní článek bude na rozdíl od těch předcházejících laděn na poněkud matematičtější notu. Budeme se zabývat hyperkrychlí, což je objekt známý z teorie grafů.

Zní to složitě, ale těžké to není

Na začátek si zkusíme poněkud tajemně znějící pojem trošku rozpitvat a ukázat jakou má souvislost s tradiční třírozměrnou krychlí v prostoru. U hyperkrychle je vždy potřeba říct jakou má dimenzi. Podívejme se kupříkladu na Obrázku 1 na hyperkrychli dimenze dvě.

Nic objevného se tady nekoná, vypadá jako obyčejný čtverec. Dle očekávání hyperkrychle dimenze tři na Obrázku 2 vypadá jako krychle, ale zdání může klamat.

U hyperkrychle nás nezajímá fyzikální interpretace rozměrů, tedy zda jsou prostorové, časové nebo jiné. Zajímá nás pouze propojení vrcholů hranami mezi sebou. Proto je v pořádku že hyperkrychle dimenze tři může vypadat i jako na Obrázku 3.

Kde takovou hyperkrychli vzít? Hyperkrychli dimenze tři vytvoříme tak, že vezmeme dvě hyperkrychle dimenze dvě a spárujeme protější vrcholy novými hranami. Stejně tak vytvoříme hyperkrychli dimenze čtyři - spárováním vrcholů dvou hyperkrychlí dimenze 3 jak je vidět na Obrázku

Opačným způsobem (tedy řezáním) snadno dostaneme z hyperkrychle dimenze dva hyperkrychli dimenze jedna a z ní hyperkrychli dimenze nula. Zkuste si to :). Obecně hyperkrychli dimenze budeme označovat jako kde je číslo větší nebo rovno nule. A když už víme jak hyperkrychle vypadá, zkusme se zamyslet nad tím, kolik má taková hyperkrychle dimenze vrcholů. Snadno spočítáme že má jen jeden vrchol, dva vrcholy, má čtyři a osm. Protože každá je vytvořena spojením dvou hyperkrychlí (tedy dimenzí o jednu menší), musí mít má dvakrát tolik vrcholů než , čtyřikrát tolik vrcholů než , osmkrát tolik vrcholů než a tak dále. Tedy počet vrcholů je a to je vrcholů.

Vrcholy to nejsou jen tak obyčejné a není náhodou, že je na obrázcích kreslíme různě. Vrcholy každé hyperkrychle lze totiž rozdělit na černé a bílé vrcholy a to takovým způsobem, že jsou hranami spojeny jen černé vrcholy s bílými. Nikdy nejsou mezi sebou spojené žádné dva černé vrcholy a stejně tak nejsou nikdy mezi sebou spojené ani žádné dva bílé vrcholy. Této vlastnosti se říká bipartita. Například graf se třemi vrcholy který vypadá jako trojúhelník bipartitní není.

Poslední pojem který si představíme bude Hamiltonovskost. Je to jakási varianta kreslení domečku jedním tahem. Položíme tužku na jeden libovolný vrchol hyperkrychle a budeme chtít bez zvednutí tužky z papíru projít všechny vrcholy hyperkrychle, skončit na místě kde jsme začali, ale zároveň žádný vrchol nechceme projít dvakrát. Útvaru který tímto nakreslíme se říká Hamiltonovský cyklus a graf kde takový cyklus umíme najít se nazývá Hamiltonovský. Hyperkrychle dimenze čtyři je Hamiltonovská, jak můžeme vidět na Obrázku 5.

Protože Hamiltonovský cyklus v obsahuje všechny vrcholy hyperkrychle, musí mít hran a vrcholů. Není těžké ukázat že každá hyperkrychle dimenze aspoň dva je Hamiltonovská.

Zajímavější problém nastává, pokud začneme nějaké vrcholy mazat. Bude mít hyperkrychle s nějakými vrcholy smazanými stále Hamiltonovský cyklus? To záleží nejen na tom jaké vrcholy smažeme, ale také kolik. Dovolíme-li v hyperkrychli smazat až vrcholů, pak můžeme jednomu vrcholu smazat všechny jeho sousedy a nebudeme jej tak moc na Hamiltonovský cyklus nijak napojit. Dále si musíme dát pozor na to, abychom mazali stejný počet bílých vrcholů jako černých, jinak by nám vždycky nějaké vrcholy zbyly. V roce 2001 Locke vyslovil hypotézu že pokud v hyperkrychli smažeme nejvýše černých a bílých vrcholů (ale stejně bílých jako černých) kde pak je taková otrhaná hyperkrychle stále Hamiltonovská. Tato hypotéza nebyla zatím dokázána (ani vyvrácena). Jsou však známy různé částečné výsledky.

No a k čemu je to všechno dobré?

Představme si například, že vrcholy hyperkrychle jsou procesory a hrany hyperkrychle jakési “dráty” kterými mezi sebou ony procesory komunikují. Po několika návrzích byl tento koncept realizován a v roce 1983 spatřil na Caltechu světlo světa první hyperkrychlový počítač jménem CosmicCube. Měl 64 procesorů propojených do topologie šestirozměrné hyperkrychle. Ve stejné době vyvíjeli na MIT vlastní hyperkrychlový počítač jménem Connection Machine, na kterém pracoval mimo jiné i známý fyzik Richard Feynman (o jeho patáliích s Connection Machine byl napsán moc hezký článek). O pár let později začal Intel nabízet hyperkrychlové počítače i komerčně. Avšak po dalších pokusech o jejich zdokonalování byly nakonec pro svoji špatnou škálovatelnost opuštěny. I přesto hyperkrychle nacházejí využití i v současnosti. Zmiňme alespoň P2P síť HyperCup, bluetooth síť BlueCube či hyperkrychlovou topologii pro dynamicky distribuované databáze zvanou HyperD, která byla představena v roce 2011.

Pro pozorné čtenáře

Bonusová otázka na závěr. V článku jsme zmínili, že hyperkrychle dimenze má vrcholů. Kolik má hran?