Cayleyho graf

Cayleyho graf je grafické znázornění diskrétních grup.

Britský matematik 19. století Arthur Cayley navrhl elegantní grafický způsob znázornění diskrétních grup. Jeho „barevné“ grafy byly následně pojmenovány „Cayleyho grafy“ (Cayley graphs). Rozvoj počítačové techniky a rozvoj počítačových metod v matematice způsobil, že se Cayleyho grafy staly vděčným objektem výzkumu.

Princip metody

Cayleyho metoda vychází z vyjádření struktury grupy G = {g1,g2, ... } pomocí generátorů S = {s1,s2, ... }, S ${\textstyle \subset }$ G. Množina generátorů S je podmnožina grupy G taková, že každý prvek grupy G lze vyjádřit jako součin některých generátorů (a jejich inverzí). Generátory S generují grupu G. Cayleyho graf se kreslí tak, že vrcholy grafu odpovídají prvkům grupy g1,g2,.. a orientované hrany odpovídají generátorům s1,s2,... Dva vrcholy g, g´ se spojují orientovanou hranou s = (g, g´), jestliže g.s = g´ (tečka značí grupovou operaci). Hrany odpovídající různým generátorům se kreslí různými barvami. Níže je příklad. Více v odstavci „Generátory, relace, grafy“.

Cayley graph of the modular maximal-cyclic group of order 16

Různé podoby diskrétních grup

Abstraktní grupa G je množina prvků G = {g1,g2, ... }, na které je definována operace „násobení“ (píšeme tečku, x.y = z), splňující určitá pravidla (axiomy), jako asociativitu, existenci identického prvku „E“ (od slova „einheit“), existenci opačného (inverzního) prvku k danému ( g. g⁻¹ = E). Když grupová operace splňuje vlastnost komutativity, tak se označuje jako „součet“. Jestliže tedy v celé grupě platí x.y = y.x, píše se místo tečky „plus“, x+y = y+x. Taková grupa se pak jmenuje abelovská, nebo komutativní. Identický prvek E je „nula“, inverzní prvek k x je „mínus“ x.

Následující odstavce poskytují informace o některých „reprezentacích“ abstraktních grup, ve smyslu „co vlastně mohou znamenat“ prvky g1,g2, .... Tyto a jiné reprezentace se používají jak v matematice samotné (teorie grup, algebra, ...), tak v přírodních vědách (fyzika, chemie,...).

Tabulka násobení

Jako výchozí / startovací reprezentaci uvažujme tabulku grupového násobení. Tabulka musí pochopitelně splňovat určité vlastnosti, aby skutečně reprezentovala grupu. To se manuálně někdy dost těžko testuje. Příklad:

	0	1	2
0	0	1	2
1	1	2	0
2	2	0	1

Tabulka reprezentuje grupu G= {0,1 2}. Symetrie podle hlavní diagonály znamená, že grupa je komutativní (abelovská), s identickým prvkem 0. Jde o grupu celých čísel {0,1,2} s operací + modulo 3. Například 2+2(mod 3) = 4(mod 3)= 1. Analogicky lze sestavit tabulku pro G= {0,1 2, ... n−1} s operací součtu modulo n pro libovolné přirozené číslo n. Grupovou tabulku lze někdy sestrojit poměrně jednoduše. Obecně je však tento úkol pracný, protože zvláště teorie neabelovských grup je složitá a dosti exotická na to, aby její grupy byla součástí běžné matematiky. Některé neabelovské grupy jsou dobře rozpracované a mají svá historická označení. S vyjmenováním a označením všech abelovských grup není problém, protože mají jednoduchou strukturu. Grupa reprezentovaná výše uvedenou tabulkou se jmenuje cyklická grupa a má označení C₃.

Grupy permutací

Diskrétní grupy se často definují pomocí množiny permutací. Prvky grupy P = {π₁ , π₂, ... π_n } jsou tedy permutace, tj. transformace jedna k jedné některé k-prvkové množiny.  Elementární způsob zápisu permutací je dvojřádkový. První řádek je vždy stejný a obsahuje posloupnost všech k prvků permutované množiny. Druhý řádek jsou vlastní permutace, tj. jak se transformují prvky z prvního řádku. Konkrétně grupa C₃ = {0,1,2} má izomorfní reprezentaci {0,1,2} → {π₁ , π₂, π₃ }:

$\pi 1={\begin{pmatrix}0&1&2\\0&1&2\end{pmatrix}}$, $\pi 2={\begin{pmatrix}0&1&2\\1&2&0\end{pmatrix}}$, $\pi 3={\begin{pmatrix}0&1&2\\2&0&1\end{pmatrix}}$.

Grupová operace se nazývá „součin permutací“. Výsledkem součinu π_i. π_j  je nějaká permutace, která se dostane tak, že se na jednotlivé prvky 0,1,2 nejprve aplikuje transformace „π_i“ a následně transformace „π_j“. Někdy se preferuje opačný způsob, tj. násobení zprava doleva. Skládání pak vypadá takto: π_k (x) = (π_i (π_j (x)). Takový je zvyk, když symboly π považujeme za funkce π(x).

Značný pokrok (usnadnění) představuje zápis jednotlivých permutací pomocí posloupnosti cyklů. Identická permutace π₁ se zapisuje (), jako že se nic neděje. Permutace π₂ se zapíše (0,1,2), což znamená, že 0 se transformuje na 1, dále 1 na 2, a nakonec 2 na 0, a zase od začátku.

Rozšířený příklad: Množina všech permutací k-prvkové množiny {0,1 2}, k= 3, je tzv. symetrická grupa S_k. Obsahuje 6 permutací, S₃ =  { (), 0,1), (1,2), (2,0), (0,1,2),(0,2,1) }. Každá grupa permutací je podgrupou (podmnožinou) celé symetrické grupy S_k.. Tak zní tzv. Cayleyho věta (opět ten Cayley ...). Symetrická grupa S_k má k! prvků (k-faktoriál), např. 3! = 3 krát 2 krát 1 = 6.

Násobení dvou permutací vyjádřených pomocí cyklického zápisu je jednoduché, ale chce to procvičit. Postup je následující. Jednotlivé cykly obou násobených permutací se vypíší vedle sebe (za sebou, bez interpunkce). Vznikne legálně zapsaný výsledek násobení. Ovšem pokud nejsou všechny prvky takového spojení různé, lze ho dále zjednodušit. Jde se zleva doprava a aplikuje jednotlivé transformace postupně na jednotlivé prvky a jednotlivé cykly až do jejich vyčerpání (až na konec řádku, až už nejsou žádné další prvky ani cykly). Příklad násobení v symetrické grupě S₃: (0,1) krát (0,1,2) = (0,1) (0,1,2). Z předběžného součinu se jde z 0 na 1 podle prvního cyklu, z 1 na 2 podle druhého cyklu. Tím se zápis pro 0 vyčerpal a do prozatímního výsledku se napíše (0,2. Jak to je s jedničkou? Z 1 do 0 (první cyklus), z 0 do 1 (druhý cyklus), tedy dohromady identita, nic. A jak je to prvkem 2? V prvním cyklu dvojka vůbec není. Podle druhého cyklu transformujeme 2 na 0, tak že (2,0). Stačí dát do prozatímního výsledku pravou závorku a dostaneme konečný výsledek (0,2).

Ještě několik příkladů k S₃: (0,1,2) krát (0,1). Vyjde (1,2), což se nerovná výsledku (0,2) z prvního příkladu. To znamená, že grupa S₃ není abelovská (není komutativní). Poslední příklad k S₃ : dvě permutace (0,1,2) a (0,2,1) jsou navzájem inverzní, protože jejich součin je identita.

Cyklus délky 2 se obecně jmenuje transpozice. Součin transpozic (a₁,a₂ ) (a₁,a₃ ) ... (a₁,a_n ) se rovná (a₁,a₂ , ... a_n ), jak lze snadno zkontrolovat. Speciálně součin dvou transpozic (0,1) a (0,2) je cyklus (0,1,2).

Grupy matic

Matice reprezentují transformace vektorových prostorů. Násobení matic je celkem známá věc. Taky je známo, jak se najde inverzní matice, že determinant ortogonální matice rotace se rovná 1, atd., atd. Následující tři matice tvaru

T = ${\textstyle {\begin{pmatrix}sin(\alpha )&cos(\alpha )\\-sin(\alpha )&cos(\alpha )\end{pmatrix}}}$ , kde ${\textstyle \alpha }$ = 0$\pi$, 2/3$\pi$  a 4/3$\pi$,

tvoří grupu izomorfní s cyklickou grupou C₃. Grupová operace je násobení matic. Grupa reprezentuje rotací 2rozměrného vektorového prostoru: roviny, nebo objektů v rovině se středem v bodě (0,0). Běžně si rotaci představujeme jako spojitý proces. Tato grupa grupa je však diskrétní, má jen tři prvky. Je to podgrupa spojité grupy rotací. Ještě příbuzný příklad reprezentace cyklické grupy C3 pomocí tří matic 1 x 1 nad tělesem komplexních čísel:

T = (  e^iφ ) , pro úhel  $\varphi$ = 0$\pi$, 2/3$\pi$  a 4/3$\pi$  .

Fyzika a chemie poskytují velké množství příkladů geometrických symetrii buď přímo zkoumaných objektů, nebo symetrii jevů ve zkoumaných objektech. Tyto symetrie „reálného světa“ se převedou na grupy, které se pak zkoumají matematickými prostředky.

Z tabulky konečné grupy G = {g₁ , g₂, ... g_n } lze pomocí následující konstrukce sestavit izomorfní grupu matic typu n x n. Konstrukci ukážeme na příkladu tabulky C3.= {0,1,2}. Výsledkem konstrukce budou tři matice M₀, M₁, M₂ . V prvním kroku všechny matice M_i vynulujeme. V dalších n krocích některé nuly v M_i nahradíme jedničkami. Indexy (i,j) těchto jedniček se budou řídit hodnotami i-tého řádku tabulky. Matice M₀ se vytvoří tak, že se vychází z nultého řádku tabulky (= 0,1,2) a dává se jednička do míst s indexy  (0,0), (1,1) a (2,2). Matice M₁ se vytvoří tak, že se vychází z prvního řádku tabulky (= 1,2,0) dává se jednička do míst s indexy  (0,1), (1,2) a (2,0). Nakonec Matice M₂ se vytvoří tak, že se vychází z druhého řádku tabulky (= 2,0,1) a dává se jednička do míst s indexy  (0,2), (1,0) a (2,1). Výsledek je následující

M₀ = ${\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}}$, M₁ = ${\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}}$, M₂ = ${\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}$.

Grupová operace je násobení matic. Identický prvek grupy je M₀ .

Jednodušší a obecnější způsob je následující. Pro účely vysvětlení konstrukce označme prvky grupy symboly a,b,c,d,e,...  a stejně tak řádky a sloupce tabulky. Všimněme si, že pořadí řádků (sloupců taky) v grupové tabulce není důležité, protože důležitý je jen výsledek násobení, tj. co je na průsečíku řádku a sloupce. Proto můžeme řádky tabulky napsat v pořadí inverzních prvků, tj. a⁻¹,b⁻¹,c⁻¹ , ..(resp. -a.-b,-c, .. v případě abelovské grupy). Matici M_x pak vytvoříme tak, že dáme jedničku do místa, kde je na stejném místě upravené tabulky prvek x. Všude jinde budou nuly. V případě C3= {0,1,2} požadovaná úprava grupové tabulky znamená vyměnit poslední dva řádky. Získané matice M_x reprezentují permutace vektorů vytvořených z řádků (sloupců) grupové tabulky. Násobení matic M_x pak logicky znamená násobení permutací ve smyslu předchozího odstavce.

Generátory, relace, grafy

Příklad dihedrální grupy

Dihedrální grupa  D_n  se zpravidla definuje následujícími relacemi mezi dvěma generátory r,s

  rⁿ  = s²  = r.s.r.s = 1   ( n je přirozené číslo).

Obecně se takovým výrazům říká prezentace grupy (pozn. ke knihám: existují ruské překlady). Identický prvek zde značíme „1“

Grafy se mohou kreslit různě. Podstatné je, aby hrany grafu korektně spojovaly vrcholy. Pochopitelně dobré je kreslit grafy co nejméně zamotaným, dobře zapamatovatelným způsobem. Cayleyho graf grupy D₃ (vpravo) je nakreslen jako dva kruhy ve dvou rovinách nad sebou. Analogicky lze zobrazit grafy grup D₄, D₅ ,D₆ ... Častěji se setkáváme s vyobrazením ve tvaru n-úhelníků (místo kruhů). Z tohoto geometrického náhledu je odvozen název grupy, termín „dihedrální“ je totiž znamená „pomocí dvou rovin“.

Z grupového hlediska kruhy na obrázku reprezentují cykly, odpovídající relaci  r³ = 1 Všimněte si, že cykly v protilehlých rovinách mají opačné směry. Je to dáno relací r.s.r.s = 1 . Vzhledem k symetrii Cayleyho grafu libovolný vrchol se může označit prvkem grupy „1“ (identita). Z takto jednou označeného vrcholu „1“ lze pak „cestovat“ po zbývajících vrcholech a markovat je odpovídajícím součinem generátorů. Protější cykly jsou v grafu spojeny neorientovanou hranou. Toto je užitečná konvence. Obecně dvě orientované hrany, které odpovídají relaci s²  = 1, které by se podle definice měly kreslit jako dvě hrany s šipkami proti sobě, se kreslí zjednodušeně jako jedna neorientovaná hrana.

Dihedrální grupa D_n  pro n > 2 není komutativní. Z grafu grupy D₃ je vidět, že r.s  s.r . Z vrcholu „1“ zvoleného někde v horní rovině, obě cesty sice vedou do spodní roviny, ale do různých vrcholů. Jestliže směry cyklů v protilehlých rovinách otočíme tak, aby byly shodné, dostaneme Cayleyho graf jiné grupy, která se dá vyjádřit symbolem C_n x C₂ (kartézský/přímý součin grup C_n a C₂ ) . Prezentace takové grupy pomocí generátorů a relací vypadá následovně:

rⁿ  = s²  = 1, r.s = s.r

Nejednoznačnosti

D₃ a S₃ jsou si rovny (jsou izomorfní). Pokud to je pravda (a je to pravda), pak 6 vrcholů Cayleho grafu D₃ by se mělo dát označit šesti permutacemi S₃ =  { (), (0,1), (1,2), (2,0), (0,1,2),(0,2,1) } . Ale jak to udělat, aby to bylo správně? Přiřazení není jednoznačné. Na vině je symetrie. Nejednoznačnost začíná již tím, že je jedno, který vrchol grafu se označí jako identický prvek () = 1. Které permutace z množiny S₃ mají odpovídat symbolům r,s ? Protože s²  = 1, symbol s se může namapovat pouze na některou transpozici (0,1), (1,2), nebo (2,0). Symbol r se může namapovat pouze na (0,1,2), nebo (0,2,1). Z toho pak plyne označení všech vrcholů grafu. Základem je tedy namapování generátorů. Nejlépe je začít s označením vrcholů pomocí symbolických součinů generátorů (např. jak je to na obrázku v úvodu článku) a následně vyjádřit součiny ve vrcholech pomocí prvků grupy.

Příklad hyperkrychle

Cayley graph of (C₂)⁵

Cayley graph of 3=cube and Hamiltonian cycle

Tento odstavec je věnován matematickým objektům, které přímo nebo nepřímo inspirovaly zástupy lidí, od vědců, tvůrců současných superpočítačů, až po literární a filmové fantasty. Objekty se jmenují hyperkrychle, což je zkratka termínu n-krychle pro n= 0,1,2,... ∞ , symbolicky (C₂)ⁿ , resp. (C₂)∞ . Hyperkrychli chápeme buď jako diskrétní grupu, která je přímým součinem n stejných vzorků cyklické grupy C₂ = {0,1}, nebo jako Cayleyho graf této grupy, nebo tentýž Cayleyho graf, u kterého jsou všechny hrany nakresleny jednobarevně. Na prvky cyklické grupy C₂ = {0,1} se díváme jako na počítačové bity a na prvky grupy (C₂)ⁿ  jako na počítačová „slova”. Například (C₂)³ = {000,001,010,011,100,101,110,111}. Je to abelovská grupa, v níž je součet dvou „slov“ definován jako pokomponentní součet modulo 2 (součet modulo 2 protilehlých bitů). Jako generátory hyperkrychle se nejčastěji berou „samé nuly a jedna jednička“.

Definice n-krychle pomocí symbolických generátorů a relací je zobecnění následující prezentace grupy (C₂)³:

r² = s²   =  t² = 1,     r.s = s.r ,  s.t = t.s , r.t = t .r

Druhá mocnina generátorů je identita. Prezentace musí obsahovat všechny možné komutační relace. Níže je Cayleyho graf 3krychle, jak se dnes běžně kreslí. Ve vrcholech grafu jsou místo součinů symbolických generátorů r,s,t odpovídající binární čísla, které vyplývají z přiřazení r= 001, s= 010, t= 100. Podle konvence o kreslení dvou hran, které mají orientací proti sobě, se hrany hyperkrychle kreslí jako neorientované, Když vynecháme barvy, dostaneme „černobílý“ neorientovaný graf 3krychle.

Vzniká otázka, jak pokračovat v kreslení hyperkrychlí „vyšších dimenzí“, tedy n-krychlí pro n > 3, aby postup byl systematický a výsledek vypadal „smysluplně“. Jednou z možností je následující konstrukce. Jako příklad vezmeme 5krychli. Nakreslíme kruh, na jehož obvodu vyznačíme v pravidelných intervalech 32 vrcholů. Omarkujeme vrcholy přirozenou posloupností čísel 0,1,2,3,4,5,... 31 (např. proti směru hodinových ručiček). Nebo ještě lépe, místo dekadických čísel použijeme jejich binárními ekvivalenty 00001,00010, ... 11111. Toto bude pomocná posloupnost. V dalším kroku ji nahradíme Grayově kódem, který má tu vlastnost, že dvě sousední slova v posloupnosti (tj. podél kruhu) se budou lišit v jednom bitu.

Ukážeme dvě metody sestrojení Grayova kódu. První metodu lze stručně vyjádřit pomocí programátorského příkazu return b ^ (b >> 1). Vezmeme binární číslo b a uděláme pokomponentní logický součin (operátor  ) tohoto slova b se stejným slovem b posunutým o jeden bit vpravo (operátor >> 1). Z původní posloupnosti binárních čísel podél kruhu 00000,00001,00010,00011,00100,00101,00110, .... tímto způsobem dostaneme Grayovu posloupnost 00000, 00001, 00011, 00010, 00110, 00101, 00100, ...., Poslední člen posloupnosti bude 10000 a tím se kruh uzavře. Sousední slova v posloupnosti se skutečně budou lišit v jednom bitu.

Uvedenou metodu můžeme nazvat „lokální”, protože řeší členy Grayova kódu lokálně, Druhá metoda je „globální”. Z její konstrukce pramení přívlastek „reflected binary code”. Procedura se definuje rekurentně. Předpokládejme, že již máme Grayův kód délky 2ⁿ⁻¹ . Např. pro n= 4 máme Grayovu posloupnost 000,001,010,011,100,101,111,110,100. Grayův kód dvojnásobné délky 2ⁿ vygenerujeme tak, že nejprve uvedenou posloupnost (první polovinu) napíšeme v obráceném pořadí. Dále ke všem členům obrácené posloupnosti připojíme zleva bit s hodnotou „1“. Dostaneme tak 1100,1110,1111,1101,1100,1011,1010, 1001,1000. Když tuto posloupnost připojíme zprava k první posloupnosti, dostaneme Grayův kód dvojnásobné délky 2ⁿ . Aby byl výsledek hezky zarovnaný, ke všech členům první poloviny ještě připojíme zleva bit s hodnotou „0“.

Vraťme se teď ke konstrukci Cayleyho grafu z obrázku. Sousední vrcholy podél kruhu jsou spojeny hranami, které reprezentují generátory grupy (C₂)⁵. Zbývá nakreslit hrany uvnitř kruhu. Obrázek jasně ukazuje jak to udělat. A ještě jedna zvláštnost. Cesta v grafu podél kruhu se jmenuje Hamiltonův cyklus. Takových H. cyklů je v hyperkrychli více. Na vedlejším obrázku hyperkrychle (C₂)³ je jednoduchá ilustrace Hamiltonova cyklu (obarveno žlutě).

Odkazy

Související články

• Hamiltonovský graf
• Grayův kód
• Nadkrychle

Externí odkazy

• Obrázky, zvuky či videa k tématu Cayleyho graf na Wikimedia Commons
• kalyey graph
• GROUPS WITH A CAYLEY GRAPH ISOMORPHIC TO A HYPERCUBE
• Vertex-transitive graphs which are not Cayley graphs, I
• Norman Biggs, Algebraic Graph Theory, 2-ed., Cambridge University Press, 1993
• WILLIAM BURNSIDE, historická kniha o konečných grupách

Portály: Matematika