Cayleyho graf

Princip metody

Cayleyho metoda vychází z vyjádření struktury grupy G = {g1,g2, . } pomocí generátorů S = {s1,s2, . +more }, S \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. +morey = 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−1 = 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, . +more), 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. +more To se manuálně někdy dost těžko testuje. Příklad:

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í C3.

Grupy permutací

Diskrétní grupy se často definují pomocí množiny permutací. Prvky grupy P = {π1 , π2, . +more π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 C3 = {0,1,2} má izomorfní reprezentaci {0,1,2} → {π1 , π2, π3 }:.

\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. +more π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 π1 se zapisuje , jako že se nic neděje. +more Permutace π2 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 Sk. +more Obsahuje 6 permutací, S3 =  { , 0,1), (1,2), (2,0), (0,1,2),(0,2,1) }. Každá grupa permutací je podgrupou (podmnožinou) celé symetrické grupy Sk. Tak zní tzv. Cayleyho věta (opět ten Cayley . ). Symetrická grupa Sk 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í. +more 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ě S3: (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 S3: (0,1,2) krát (0,1). Vyjde (1,2), což se nerovná výsledku (0,2) z prvního příkladu. +more To znamená, že grupa S3 není abelovská (není komutativní). Poslední příklad k S3 : 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 (a1,a2 ) (a1,a3 ) . +more (a1,an ) se rovná (a1,a2 , . an ), 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. +more 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 = \begin{pmatrix} sin(\alpha) & cos(\alpha) \\ -sin(\alpha) & cos(\alpha) \end{pmatrix} , kde \alpha = 0\pi, 2/3\pi  a 4/3\pi,

tvoří grupu izomorfní s cyklickou grupou C3. Grupová operace je násobení matic. +more 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 = (  eiφ ) , 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 = {g1 , g2, . gn } lze pomocí následující konstrukce sestavit izomorfní grupu matic typu n x n. +more Konstrukci ukážeme na příkladu tabulky C3. = {0,1,2}. Výsledkem konstrukce budou tři matice M0, M1, M2 . V prvním kroku všechny matice Mi vynulujeme. V dalších n krocích některé nuly v Mi nahradíme jedničkami. Indexy (i,j) těchto jedniček se budou řídit hodnotami i-tého řádku tabulky. Matice M0 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 M1 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 M2 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í.

M0 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}, M1 = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}, M2 = \begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}.

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

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,. +more  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−1,b−1,c−1 , . (resp. -a. -b,-c, . v případě abelovské grupy). Matici Mx 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 Mx reprezentují permutace vektorů vytvořených z řádků (sloupců) grupové tabulky. Násobení matic Mx pak logicky znamená násobení permutací ve smyslu předchozího odstavce.

Generátory, relace, grafy

Příklad dihedrální grupy

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

  rn  = s2  = 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). +more Identický prvek zde značíme „1“ náhled 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 D3 (vpravo) je nakreslen jako dva kruhy ve dvou rovinách nad sebou. Analogicky lze zobrazit grafy grup D4, D5 ,D6 . Č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  r3 = 1 Všimněte si, že cykly v protilehlých rovinách mají opačné směry. Je to dáno relací r. +mores. 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 s2  = 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 Dn  pro n > 2 není komutativní. Z grafu grupy D3 je vidět, že r. +mores  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 Cn x C2 (kartézský/přímý součin grup Cn a C2 ) . Prezentace takové grupy pomocí generátorů a relací vypadá následovně:.

rn  = s2  = 1, r.s = s.r

Nejednoznačnosti

D3 a S3 jsou si rovny (jsou izomorfní). Pokud to je pravda (a je to pravda), pak 6 vrcholů Cayleho grafu D3 by se mělo dát označit šesti permutacemi S3 =  { , (0,1), (1,2), (2,0), (0,1,2),(0,2,1) } . +more 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 S3 mají odpovídat symbolům r,s . Protože s2  = 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 (C2)5 +morepng|vlevo|náhled|260x260pixelů'>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 (C2)n , resp. (C2)∞ . Hyperkrychli chápeme buď jako diskrétní grupu, která je přímým součinem n stejných vzorků cyklické grupy C2 = {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 C2 = {0,1} se díváme jako na počítačové bity a na prvky grupy (C2)n  jako na počítačová „slova”. Například (C2)3 = {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 (C2)3:

r2 = s2   =  t2 = 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. +more 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. +more 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). +more 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”. +more Procedura se definuje rekurentně. Předpokládejme, že již máme Grayův kód délky 2n−1 . 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 2n 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 2n . 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 (C2)5. +more 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 (C2)3 je jednoduchá ilustrace Hamiltonova cyklu (obarveno žlutě).

Odkazy

Reference

Související články

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

Externí odkazy

kalyey graph * [url=https://www. cambridge. +moreorg/core/services/aop-cambridge-core/content/view/5005F1930F6877DE28A58FD9B4A262CC/S0004972700034055a. pdf/groups_with_a_cayley_graph_isomorphic_to_a_hypercube. pdf]GROUPS WITH A CAYLEY GRAPH ISOMORPHIC TO A HYPERCUBE[/url] * Vertex-transitive graphs which are not Cayley graphs, I * Norman Biggs, Algebraic Graph Theory, 2-ed. , Cambridge University Press, 1993 * WILLIAM BURNSIDE, [url=https://www. gutenberg. org/files/40395/40395-pdf. pdf]historická kniha o konečných grupách[/url].

Kategorie:Teorie grup