UNIVERZA V LJUBLJANI PEDAGOˇ SKA FAKULTETA
ANA PETEK
GRUPE IN CAYLEYJEVI DIGRAFI
DIPLOMSKO DELO
LJUBLJANA, 2016
UNIVERZA V LJUBLJANI PEDAGOˇ SKA FAKULTETA
DVOPREDMETNI U ˇ CITELJ: fizika - matematika
ANA PETEK
Mentor: Doc. dr. Primoˇ z ˇ Sparl
GRUPE IN CAYLEYJEVI DIGRAFI
DIPLOMSKO DELO
LJUBLJANA, 2016
Zahvala
Mentorju doc. dr. Primoˇzu ˇSparlu se zahvaljujem za vse koristne nasvete, strokovno pomoˇc in razumevanje pri nastajanju mojega diplomskega dela.
Rada bi se zahvalila tudi vsem svojim najbliˇzjim sorodnikom in prijateljem, ki so mi ves ˇ
cas stali ob strani in me spodbujali skozi celoten ˇstudij.
Povzetek
Vsebina diplomskega dela po eni strani sodi na podroˇcje teorije grup, po drugi strani pa na podroˇcje teorije grafov. V diplomskem delu obravnavamo Cayleyjeve digrafe razliˇcnih konˇcnih grup in se ukvarjamo s prepoznavanjem lastnosti grup iz njihovih upodobitev s pomoˇcjo Cayleyjevih (di)grafov. Ko govorimo o lastnostih grup, mislimo predvsem na lastnosti kot so redi elementov, generatorji grupe, podgrupe, podgrupe edinke, odseki in podobno. Cayleyjevi digrafi so za takˇsno obravnavo zelo primerni, saj nam neposredno ali posredno pokaˇzejo vse lastnosti grupe in nam dajejo jasno sliko o njeni kompleksnosti.
Cayleyjevi (di)grafi so ime dobili po Arthurju Cayleyju, ki jih je prviˇc omenil leta 1878.
Omenjene grafe naravno dobimo iz grup, saj so njihova vozliˇsˇca elementi grupe. Zaradi si- metrije, ki jo dopuˇsˇcajo, ti grafi iz vsakega vozliˇsˇca ”izgledajo”povsem enako. Pri iskanju lastnosti grup preuˇcujemo strukture njihovih Cayleyjevih (di)grafov in njegovih lastno- sti. Grupe so namreˇc abstrakten pojem, zato nam je v veliko pomoˇc, da lahko lastnosti grup obravnavamo na njihovih Cayleyjevih (di)grafih in s tem obravnavo teh abstraktnih objektov vizualiziramo.
V diplomskem delu uvodoma pojasnimo osnovne pojme teorije grup, ki jih bo bralec potre- boval pri razumevanju diplomskega dela. Za tem ponovimo osnovne pojme teorije grafov in vpeljemo pojem digrafa. Potem bralca seznanimo s pojmom Cayleyjevega (di)grafa, kateremu v diplomskem delu posvetimo najveˇc pozornosti. Pri tem predvsem pokaˇzemo, na kakˇsen naˇcin se lastnosti grup odraˇzajo v njihovih Cayleyjevih (di)grafih in kako lahko navedene lastnosti razberemo.
Kljuˇcne besede: grupa, digraf, Cayleyjev digraf, upodobitev.
Klasifikacija MSC (2010): 05C20, 05C25, 05C90.
Title: Groups and Cayley digraphs Abstract
On one hand the content of this thesis falls within the scope of Group theory, and on the other hand in the field of Graph theory. The thesis deals with Cayley digraphs of different finite groups and with identifying properties of groups from their representation as Cayley (di)graphs. By the properties of groups we particularly refer to the properties such as the orders of elements, generators of group, the subgroups, the normal subgroups, the cosets, and so on. Cayley digraphs are very appropriate for such consideration as they directly or indirectly reveal various properties of the groups, and give a clear insight into the complexity of the group.
Cayley (di)graphs are named after Arthur Cayley, who first mentioned them in 1878.
These graphs are naturally obtained from groups with their vertices being the elements of the group in question. Due to the symmetry these graphs “look“ exactly the same from each vertex. When investigating the properties of the groups we examine the structure of their Cayley (di)graphs and their characteristics. Groups are in fact abstract objects.
Being able to investigate their properties via their Cayley (di)graphs is thus of great help since it enables us to visualise these abstract objects.
At the beginning of the thesis we define the basic concepts of Group theory that are ne- eded to understand the thesis. After that we explain the basic concepts of Graph theory and introduce a concept of the digraph. Afterwards we introduce the concept of Cayley (di)graphs, which play a central role in the thesis. In particular, we indicate how the pro- perties of the group are reflected in their Cayley (di)graphs and how these characteristics can be determined.
Keywords: group, digraph, Cayley digraph, representation.
MSC(2010) classification: 05C20, 05C25, 05C90.
Kazalo
1 Uvod 1
2 Osnovni pojmi 3
2.1 Teorija grup . . . 3
2.1.1 Pojem grupe in njene lastnosti . . . 3
2.1.2 Druˇzine grup . . . 6
2.2 Teorija grafov . . . 6
2.2.1 Pojem digrafa in njegove lastnosti . . . 6
3 Cayleyjevi digrafi 11 3.1 Pojem Cayleyjevega digrafa . . . 11
3.2 Grupe in Cayleyjevi digrafi . . . 14
4 Zakljuˇcek 29
Literatura 30
Poglavje 1 Uvod
Vsebina diplomskega dela po eni strani sodi na podroˇcje mlade veje matematike, imeno- vane teorija grafov, hkrati pa tudi na podroˇcje teorije grup, ki je del podroˇcja abstraktne algebre. Teorija grup se ukvarja s preuˇcevanjem grup in njihovih lastnosti. Njen razvoj naj bi se zaˇcel v 18. in 19. stoletju, med zaˇcetnike pa med drugim uvrˇsˇcamo Leonharda Eulerja, Josepha Louisa Lagrangea in Carla Friedricha Gaussa. Sodobna teorija grup, kot jo poznamo danes, naj bi se sicer zaˇcela ˇsele leta 1882, ko sta Walther von Dyck in Heinrich Weber podala definicijo pojma ”abstraktna grupa”. Grupe pogosto sreˇcujemo pri razliˇcnih vejah matematike, saj opisujejo notranjo simetrijo razliˇcnih struktur v obliki grupe avtomorfizmov. Simetrije pa so uporabne tudi na drugih podroˇcjih. Uporabljajo se na primer v kemiji, za opisovanje simetrij molekul, ali v fiziki, ker opisujejo simetrije, ki naj bi jih upoˇstevali fizikalni zakoni. Fiziki se ˇse posebej zanimajo za upodobitev Liejevih grup, saj naj bi njihove upodobitve kazale na moˇzne fizikalne teorije (povzeto po [2], [5]).
Kot reˇceno je drugo podroˇcje, s katerim se sreˇcamo, teorija grafov, katere razvoj se je zaˇcel ˇsele v 20. stoletju. Grafe si lahko predstavljamo kot objekte, sestavljene iz vozliˇsˇc in povezav med njimi. Kot zaˇcetek teorije grafov nekateri sicer ˇstejejo ˇze ˇclanek Leonharda Eulerja iz leta 1736, ki je razreˇsil ”Problem K¨onigsberˇskih mostov”. A prva knjiga o tej teoriji je izˇsla ˇsele leta 1936. Poznamo veˇc podroˇcij teorije grafov, to so na primer to- poloˇska, algebraiˇcna in algoritmiˇcna teorija grafov. Pri algebraiˇcni teoriji grafov se veliko ukvarjamo s simetrijami grafov in njihovim vplivom na razne grafovske lastnosti. Pri tem pod pojmom simetrije grafov razumemo permutacije mnoˇzice vozliˇsˇc, ki ohranjajo strukturo grafa. Prav tako kot teorija grup je tudi teorija grafov pomembna na ˇstevilnih drugih podroˇcjih, kot sta fizika in kemija. Priˇcujoˇce diplomsko delo lahko umestimo na podroˇcje algebraiˇcne teorije grafov, saj je veˇcji del namenjen rezultatom in pristopom s podroˇcja algebre. Pri prouˇcevanju grafov z algebraiˇcnega vidika nas zanimajo predvsem simetrije grafov in njihovi avtomorfizmi. To so bijektivne preslikave tega matematiˇcnega objekta samega vase, ki ohranjajo sosednost (povzeto po [6], [7]).
Primer druˇzine grafov, ki dopuˇsˇcajo veliko mero simetrije, so Cayleyjevi grafi. Cayley- jevi grafi so druˇzina grafov, ki jih naravno dobimo iz grup. Ti grafi so zelo simetriˇcni, saj imajo to lastnost, da graf iz vsakega vozliˇsˇca ”izgleda”povsem enako. Ime so dobili po Arthurju Cayleyju, ki je bil angleˇski matematik 19. stoletja in je ”svoje”grafe prviˇc omenil leta 1878 (povzeto po [1], [9]). Ti grafi so tudi glavna tema diplomskega dela.
Diplomsko delo je razdeljeno na veˇc poglavij. V drugem poglavju so ponovljeni osnovni
1
pojmi teorije grup in grafov, ki jih bo bralec potreboval za razumevanje diplomskega dela. V tretjem in najpomembnejˇsem poglavju posveˇcamo pozornost Cayleyjevim di- grafom razliˇcnih grup. Osredotoˇcamo se predvsem na povezavo med lastnostmi grup in njihovimi Cayleyjevimi digrafi. Cayleyjevi digrafi so namreˇc na nek naˇcin eden izmed naˇcinov vizualizacije grup in nekaterih njenih lastnosti. Dajejo nam jasno sliko strukture in kompleksnosti grupe. Pogledamo si, kako lahko doloˇcene lastnosti grup vidimo iz nji- hovih Cayleyjevih digrafov. S pomoˇcjo znanj, pridobljenih v drugem poglavju, poskusimo dokazati nekatere trditve, povezane z lastnostmi grup v digrafih. Sreˇcamo se tudi s poj- mom simetrije oziroma avtomorfizma v Cayleyjevih digrafih.
2
Poglavje 2
Osnovni pojmi
Preden se lotimo glavne teme diplomskega dela, ponovimo nekaj osnovnih pojmov s po- droˇcja teorije grup in teorije grafov ter navedimo nekatere rezultate, ki jih potrebujemo za razumevanje v nadaljevanju. Razdelek 2.1 je povzet predvsem po virih [2], [3] in [5], razdelek 2.2 pa po virih [6], [7] in [11].
2.1 Teorija grup
2.1.1 Pojem grupe in njene lastnosti
V tem podrazdelku ponovimo pojem grupe in navedemo nekatere njihove osnovne lastno- sti. Za zaˇcetek najprej ponovimo pojem grupe.
Definicija. Grupa je mnoˇzica G z binarno operacijo ∗:G×G→G, pri ˇcemer ima par (G,∗) naslednje lastnosti:
• mnoˇzica G je zaprta za operacijo ∗, to je, ∀g, h∈G je g∗h∈G
• operacija ∗ je asociativna, torej velja (g∗h)∗i=g∗(h∗i) za vse g, h, i∈G
• obstaja nevtralni element e∈G, da veljae∗g =g∗e=g za vse g ∈G
• vsak element iz Gima inverz, to je, ∀g ∈G ∃g−1 ∈G, da je g∗g−1 =g−1∗g =e GrupaGjekomutativnaoziromaabelska, ˇce je operacija∗komutativna, to je,∀g1, g2 ∈G, veljag1∗g2 =g2∗g1. Primeri komutativnih grup so na primer cikliˇcne grupeZn (opisane v naslednjem podrazdelku).
Nevtralni element e v nekaterih grupah oznaˇcimo z 1 ali 0 (ˇce operacijo piˇsemo multipli- kativno oziroma aditivno), inverz g−1 pa v primeru aditivne pisave v komutativni grupi oznaˇcimo z −g. Prav tako je dobro omeniti, da je nevtralni element v grupi en sam, pa tudi inverz poljubnega elementa g ∈G je enoliˇcno doloˇcen.
Dogovorimo se, da bomo v nadaljevanju oklepaje in znak za operacijo obiˇcajno izpuˇsˇcali in namesto o grupi (G,∗) govorili kar o grupiG. Prav tako bo zapisghpomenilg∗h. Grupe, o katerih bomo govorili, bodo obiˇcajnokonˇcne grupe, kar pomeni, da je mnoˇzicaGkonˇcna.
3
Definicija. Naj bo Gkonˇcna grupa ing ∈G. Moˇc (tudi red) grupe G, ki jo oznaˇcimo z
|G|, je ˇstevilo elementov v grupi G. Red elementa g je definiran kot najmanjˇse naravno ˇstevilo n, tako da velja gn=e. ˇCe tako ˇstevilon ne obstaja pravimo, da imag neskonˇcen red.
Definicija. RazbitjemnoˇziceGje druˇzina njenih nepraznih podmnoˇzic{G1, G2, . . . , Gn}, za katere velja:
1. Poljubni dve mnoˇzici sta disjunktni, to je, Gi∩Gj =∅ za vse 1≤i < j≤n.
2. Unija vseh mnoˇzic je enakaG, to je G=G1∪ · · · ∪Gn.
Razbitje na n mnoˇzic imenujemo n-razbitje, mnoˇzicamGi pa reˇcemo deli razbitja.
Trditev 2.1. Naj bo G grupa z binarno operacijo ∗. Potem v G velja pravilo krajˇsanja z leve in z desne strani, tako da iz g∗h=g∗i sledi h=i in iz h∗g =i∗g sledi h=i.
Tako kot v vsaki algebrski strukturi najdemo podstrukture, tudi v grupi najdemo pod- grupe za podedovano operacijo. Pri tem pravimo, da je v grupi G neprazna podmnoˇzica H ⊂G zaprta za podedovano operacijo, ˇce ∀x, y ∈H velja xy ∈ H. Podedovana opera- cija je torej notranja operacija v H.
Definicija. Naj boGgrupa inH ⊂Gnjena neprazna podmnoˇzica. Tedaj jeHpodgrupa grupe G, ˇce je zaprta za binarno operacijo grupeG in je za podedovano operacijo grupa.
To dejstvo oznaˇcimo z H ≤G.
Trditev 2.2. Naj bo G grupa. Njena neprazna podmnoˇzica H je podgrupa grupe G na- tanko tedaj, ko ∀h1, h2 ∈H velja h1h−12 ∈H.
Vsaka grupa G ima oˇcitno vsaj dve podgrupi:
• Vsaka grupa je podgrupa same sebe, to je G≤G. Pravimo ji nepravapodgrupa.
• Mnoˇzica {e} je podgrupa vsake grupe. Pravimo ji trivialna podgrupa.
Vse ostale podgrupe so prave netrivialne.
Definicija. Naj bo G konˇcna grupa in S ⊆ G njena neprazna podmnoˇzica. Podgrupa generirana s S, ki jo oznaˇcimo z hSi, je najmanjˇsa podgrupa grupe G, ki vsebuje S. V primeru, ko je G = hSi, potem podmnoˇzica S generira grupo G, in elementom mnoˇzice S pravimo generatorji grupe G.
Bralec lahko razmisli, da v primeru, ko je G=hSi, vsak element iz grupe Gizrazimo kot produkt konˇcnega ˇstevila elementov iz podmnoˇzice S in njihovih inverzov. V primeru, ko je hsi=G, je grupa Gcikliˇcna grupa, ki je generirana z enim samim elementom. Takˇsne grupe omenimo tudi v naslednjem podrazdelku.
4
Definicija. Naj bog ∈Gin naj boH ≤Gpodgrupa konˇcne grupeG. PodmnoˇzicigH = {gh : h ∈ H} grupe G reˇcemo levi odsek grupe G po podgrupi H, ki pripada elementu g. Podobno je desni odsek grupe G po podgrupi H, ki pripada g, enak podmnoˇzici Hg ={hg:h∈H}. Mnoˇzici vseh levih odsekov grupe Gpo podgrupi H, ki jo oznaˇcimo z G/H, pravimo kvocientna mnoˇzica grupe G po podgrupi H. Kardinalnosti kvocientne mnoˇzice pravimo indeks podgrupe H v grupi G in ga oznaˇcimo z [G:H].
Lahko se prepriˇcamo, da imata odseka gH inHg isto moˇc kot podgrupa H, saj je zaradi pravila krajˇsanja preslikava iz H v gH, podana s predpisomh 7→gh, bijektivna.
Definicija. Naj bo G grupa inH ≤G njena podgrupa. Podgrupi H pravimo podgrupa edinka v G, kar oznaˇcimo z HCG, ˇce velja katerikoli od ekvivalentnih pogojev:
(i) Vsak levi odsek grupe G po podgrupi H je enak pripadajoˇcemu desnemu odseku, torej ∀g ∈Gvelja: gH =Hg.
(ii) Vsak levi odsek grupe G po podgrupi H je enak kakemu desnemu odseku, torej
∀g1 ∈G∃g2 ∈G: g1H =Hg2.
(iii) Za vsak g ∈Gvelja gHg−1 =H, kjer je gHg−1 ={ghg−1 :h∈H}.
Izkaˇze se, da je v primeru, ko je H edinka v G, na G/H dobro definirana operacija (g1H)(g2H) = (g1g2H) in da na ta naˇcin G/H postane grupa.
Definicija. Naj bo G grupa in H edinka v G. Potem je kvocientna grupa mnoˇzica G/H ={gH|g ∈G} z operacijo (g1H)(g2H) = (g1g2)H.
Bralec lahko sam pokaˇze, da je kvocientna grupa res grupa za podano operacijo mnoˇzenja in da je reda [G:H].
Izrek 2.3(Lagrangeov izrek). Naj boH podgrupa konˇcne grupeG. Potem je red podgrupe H delitelj reda grupe G in velja
[G:H] = |G||H|.
Poglejmo si ˇse definicijo delovanja grup. Kasneje omenimo tudi diedrsko grupo Dn, ki je grupa vseh simetrij pravilnega n-kotnika, katere elementi ”delujejo”na n-kotnik kot rotacije in zrcaljenja. Izkaˇze se celo, da lahko vsako grupo predstavimo kot grupo, ki deluje na ustrezni mnoˇzici, a ker tega rezultata v nadaljevanju ne bomo potrebovali, ga ne bomo eksplicitno navedli.
Definicija. Naj bo X neprazna mnoˇzica in G konˇcna grupa z nevtralnim elementom e.
Levo delovanje grupe G na mnoˇzici X je preslikava•:G×X →X, da velja:
1. e•x=x za vse x∈X
2. (g1g2)•x=g1•(g2•x) za vse x∈X in za vse g1, g2 ∈G Mnoˇzici X potem pravimo G-mnoˇzica.
5
2.1.2 Druˇ zine grup
V tem podrazdelku se spomnimo ˇse nekaterih (druˇzin) grup, ki jih bomo sreˇcali v nada- ljevanju.
Cikliˇcna grupa Zn
Je komutativna grupa (Zn,+), pri ˇcemer jeZn mnoˇzica ostankov pri deljenju zn, v grupi pa seˇstevamo po modulu n. Grupa je moˇcin, to je|Zn|=n. Grupa je generirana z enim samim elementom, na primer h1i=Zn.
Simetriˇcna grupa Sn
Simetriˇcna grupaSn je grupa vseh permutacij mnoˇzice {1,2,3, . . . , n}. Grupa ni komuta- tivna (ˇce jen ≥ 3), operacija pa je obiˇcajno komponiranje preslikav. Elemente grupe Sn obiˇcajno zapisujemo kot produkte loˇcenih ciklov. Po dogovoru kompozitume beremo od desne proti levi, tako je na primer (123)(124) = (13)(24). Red grupe Sn je enak n!, kjer je n! =n·(n−1)·(n−2)· · ·2·1.
Alternirajoˇca grupa An
V tem primeru je mnoˇzica An mnoˇzica vseh sodih permutacij iz grupe Sn, to je takih permutacij, ki jih je moˇc zapisati kot produkt sodo mnogo transpozicij (permutacij, ki zamenjajo dva elementa, vse ostale pa pustijo na mestu). Operacija je komponiranje pre- slikav, red grupe An pa je enak n!2. Gre pravzaprav za podgrupo edinko grupe Sn.
Diedrska grupa Dn
Tudi tokrat gre za druˇzino nekomutativnih grup (ˇce je n ≥ 3), kjer gre za mnoˇzico simetrij pravilnega n-kotnika. Operacija je zopet komponiranje preslikav. Diedrsko grupo reda 2n oznaˇcimo z Dn in velja Dn = hr, z : rn = 1, z2 = 1, zrz = r−1i = {1, r, . . . , rn, z, zr, . . . , zrn}. To pomeni, da grupo Dn generirata elementa r in z, ki v resnici predstavljata rotacijo in zrcaljenje v n-kotniku. Pri tem je r reda n, z pa reda 2, z pa nam r skonjugira v r−1. (Seveda lahko mnoˇzico Dn opazujemo kot podmnoˇzico mnoˇzice Sn.)
Kvaternionska grupa Q reda 8 ([4])
Je nekomutativna grupa, ki je oznaˇcena s Q in definirana kot Q= hi, j|i4 =j4 = 1, i2 = j2, iji−1 =j−1i.
2.2 Teorija grafov
2.2.1 Pojem digrafa in njegove lastnosti
Kot reˇceno, v diplomskem delu navedemo tudi nekatere osnovne pojme iz teorije grafov, ki so pomembni za razumevanje diplomskega dela. Najprej si poglejmo pojem usmerjenega in neusmerjenega grafa.
Definicija. Usmerjeni graf ali digraf je urejeni par Γ = (V(Γ), E(Γ)), kjer je V(Γ) ne- prazna mnoˇzica vozliˇsˇc in E(Γ) podmnoˇzica urejenih parov razliˇcnih vozliˇsˇc, imenovanih usmerjene povezave ali loki. ˇCe je za u, v ∈ V(Γ) (u, v) ∈ E(Γ), potem reˇcemo, da je
6
povezava (u, v) usmerjena od u k v ali da gre iz u v v in da je v naslednik vozliˇsˇca u, u pa je predhodnikvozliˇsˇca v.
S tem smo definirali enostavne digrafe brez zank in vzporednih povezav, saj se bomo s takˇsnimi ukvarjali tudi v nadaljevanju diplomskega dela. V primeru, ko za vsako povezavo (u, v)∈E(Γ) obstaja povezava (v, u)∈E(Γ), pa je digraf Γneusmerjeni grafoziromagraf.
Obe povezavi pri upodobitvah obiˇcajno zdruˇzimo v eno (neusmerjeno) povezavo{u, v}(ali uv alivu) in ”pozabimo” na usmeritve. Vozliˇsˇcema u in v pravimo sosednji vozliˇsˇci, kar oznaˇcimo zu∼Γ v. Bralec lahko opazi, da je torej vsak graf pravzaprav le poseben digraf.
Dogovorimo se, da bomo v nadaljevanju oznako Γ obiˇcajno izpuˇsˇcali (razen, ˇce bi to pov- zroˇcilo zmedo). Namesto V(Γ), E(Γ) in u ∼Γ v bomo tako pisali V, E in u ∼ v. Bralca opominjamo, da bomo z besedo graf vedno mislili na neusmerjen graf.
(Di)graf je naˇceloma abstrakten objekt, ki ga lahko v primeru, da ni prevelik, upodobimo.
Vozliˇsˇca upodobimo kot toˇcke v ravnini, razliˇcni toˇcki pa poveˇzemo z (usmerjeno) krivuljo (ˇce je povezava element mnoˇzice povezav). Veˇcino rezultatov se da iz usmerjenih grafov (digrafov) razˇsiriti na neusmerjene grafe, zato bomo po veˇcini pri navedbi rezultatov upo- rabljali le izraz digraf.
Spodnja slika prikazuje primer grafa in digrafa ter njuno glavno razliko. To so usmerjene povezave.
Slika 2.1: Neusmerjen in usmerjen cikliˇcen graf reda 6.
Definicija. Naj bo Γ poljuben digraf. Temeljni grafdigrafa Γ je graf, ki ga dobimo iz di- grafa tako, da usmerjene povezave zamenjamo z ustreznimi (neusmerjenimi) povezavami, to je, za vsako povezavo (u, v)∈E v E dodamo ˇse povezavo (v, u).
Tako kot grupe imajo tudi grafi ”svoj”red. Red grafa Γ je kardinalnost mnoˇzice V(Γ).
Definicija. Naj bo Γ digraf in v ∈ V. Izhodna stopnja vozliˇsˇca v je ˇstevilo usmerjenih povezav, ki izhajajo iz vozliˇsˇcav. Vhodna stopnjavozliˇsˇcav je ˇstevilo usmerjenih povezav, ki se konˇcajo v vozliˇsˇcuv. ˇCe govorimo o grafu Γ, potem izraza vhodna in izhodna stopnja nadomestimo z izrazomstopnja. Gre torej za ˇstevilo (neusmerjenih) povezav, ki vsebujejo v. Oznaˇcimo jo z deg(v).
V tem diplomskem delu se sreˇcujemo predvsem z digrafi, v katerih imajo vsa vozliˇsˇca isto vhodno in isto izhodno stopnjo, pa ˇse ti dve sta med seboj enaki. V ta namen zapiˇsimo naslednjo definicijo.
Definicija. ([8]) Naj bo Γ digraf. Digraf Γ je regularen, ˇce imajo vsa vozliˇsˇca digrafa Γ enako vhodno in izhodno stopnjo, ki sta med seboj tudi enaki.
7
V primeru, ko je izhodna in vhodna stopnja vseh vozliˇsˇc enakak, govorimo ok-regularnem digrafu. Kadar je digraf graf, je torej le-ta regularen, ˇce imajo vsa vozliˇsˇca isto stopnjo.
Ko je stopnja vseh vozliˇsˇc grafa enaka k, govorimo o k-regularnem grafu. Regularnim grafom, katerih stopnja je 3, pravimo kubiˇcni.
Trditev 2.4. Vsak konˇcen digrafΓ, v katerem imajo vsa vozliˇsˇca isto izhodno stopnjo d+ in isto vhodno stopnjo d−, je regularen, to je, d+ =d−.
Dokaz. Naj bo mˇstevilo vseh vozliˇsˇc v grafu Γ. Ker iz vsakega vozliˇsˇca izhajad+ lokov (ki se konˇcajo v d+ vozliˇsˇcih) in ker se v vsakem vozliˇsˇcu konˇcad− lokov, potem velja, da je vseh lokov md+ =md−. Od tod sledi, da je d+=d−, torej je digraf Γ regularen.
V primeru, ko je digraf neskonˇcen, navedeno seveda ne velja nujno. Bralca vabimo, da sam poiˇsˇce kak protiprimer.
Iz slike 2.1, kjer imamo upodobljen regularni graf reda 6 (levi graf), vidimo, da ima graf 6 vozliˇsˇc stopnje 2. Vsota stopenj vseh vozliˇsˇc v grafu je enaka 12, kar pa je ravno dva- kratnik ˇstevila povezav, saj ima graf 6 povezav. Ta ugotovitev velja za vse grafe in jo imenujemo Lema o rokovanju.
Trditev 2.5 (Lema o rokovanju). Naj bo Γ konˇcen graf. Vsota stopenj vseh njegovih vozliˇsˇc je enaka dvakratniku ˇstevila njegovih (neusmerjenih) povezav, to je:
Σv∈V(Γ)deg(v) = 2|E(Γ)|,e kjer je E(Γ)e mnoˇzica vseh neusmerjenih povezav grafa Γ.
Lema o rokovanju je ime dobila po dejstvu, da lahko z grafom predstavimo skupino ljudi, ki se rokuje na zabavi. Ljudje predstavljajo vozliˇsˇca, povezavo med ˇclovekoma pa dodamo, ˇ
ce sta se rokovala. Lema o rokovanju torej pravi, da je ˇstevilo vseh rok, ki so sodelovale v vseh rokovanjih (ˇsteto glede na ˇstevilo rokovanj posameznika), enaka dvakratniku ˇstevila vseh rokovanj.
Pri obravnavi lastnosti digrafov nas zanimajo tudi usmerjeni sprehodi, usmerjene poti in podobno, zato si poglejmo ˇse naslednje definicije.
Definicija. Naj bo Γ = (V, E) poljuben digraf. Usmerjeni sprehod od u0 do uk dolˇzine k v digrafu Γ je zaporedje vozliˇsˇc (u0, u1, . . . , uk), pri ˇcemer je (ui, ui+1) ∈ E za vse 0 ≤ i ≤ (k −1). Vozliˇsˇcu u0 pravimo zaˇcetno vozliˇsˇce, vozliˇsˇcu uk pa konˇcno vozliˇsˇce usmerjenega sprehoda. ˇCe so vse povezave sprehoda uiui+1, za 0≤ i ≤(k−1), paroma razliˇcne, potem usmerjeni sprehod imenujemo enostavni usmerjeni sprehod. ˇCe pa so v enostavnem usmerjenem sprehodu razliˇcna tudi vsa vozliˇsˇca, potem govorimo ousmerjeni poti.
Poleg zgornjih definicij je smiselno imeti poimenovanja za usmerjene sprehode, ki se konˇcajo in zaˇcnejo v istem vozliˇsˇcu. V ta namen si poglejmo naslednjo definicijo.
8
Definicija. Naj bo Γ poljuben digraf in (u0, u1, . . . , uk) usmerjeni sprehod v Γ. ˇCe velja u0 =uk, gre zasklenjeni usmerjeni sprehod oziroma usmerjeni obhod. ˇCe so v (usmerje- nem) obhodu paroma razliˇcne vse povezave in vsa vozliˇsˇca, razen zaˇcetnega in konˇcnega vozliˇsˇca, potem ga imenujemo usmerjeni cikel.
Tako kot vsak sprehod ima svojo dolˇzino tudi cikel. (Usmerjenemu) ciklu dolˇzine k pra- vimo tudi (usmerjeni) k-cikel.
S pomoˇcjo zgornjih pojmov lahko zapiˇsimo naslednjo definicijo, ki govori o povezanosti digrafa Γ.
Definicija. Naj bo Γ = (V, E) poljuben (di)graf in naj bo v ∈Γ. Komponenta poveza- nosti (di)grafa Γ, ki vsebuje vozliˇsˇce v, je enaka mnoˇzici vseh vozliˇsˇc u ∈ V, za katere obstaja vsaj en (neusmerjeni) sprehod od v do u, to je, ko v temeljnemu grafu digrafa Γ obstaja vsaj en sprehod od v do u. Ko ima digraf Γ eno samo komponento povezanosti, je digraf Γ povezan.
Digraf Γ je torej povezan, ˇce med poljubnima vozliˇsˇcema v Γ obstaja (neusmerjeni) spre- hod ali pot, v nasprotnem primeru je digraf nepovezan.
Definicija. Naj bo Γ poljuben digraf. Digraf Γ je krepko povezan, ˇce v njem od poljub- nega vozliˇsˇca obstajajo usmerjene poti do vseh drugih vozliˇsˇc.
Potrebujemo tudi pojem dvodelnosti v (di)grafih.
Definicija. Naj bo Γ = (V, E) graf. Graf Γ je dvodelen, ˇce lahko mnoˇzico vozliˇsˇc V razbijemo na dve neprazni podmnoˇzici V1 inV2, tako da vsaka povezava grafa Γ povezuje vozliˇsˇce iz V1 z vozliˇsˇcem iz V2.
Podobno definiramo, da je digraf Γ dvodelen, ˇce je dvodelen njegov temeljni graf. Kadar je (di)graf Γ dvodelen, je mogoˇce njegova vozliˇsˇca pobarvati z dvema barvama tako, da nobeni dve vozliˇsˇci iste barve med seboj nista povezani. Prav tako v primeru, da je Γ dvodelen, v njem ne najdemo nobenega cikla lihe dolˇzine. To sledi iz dejstva, da no- beni vozliˇsˇci iste barve med seboj nista sosednji, saj bi bili potem prvo in zadnje vozliˇsˇce takˇsnega cikla iste barve, kar seveda ni mogoˇce.
Definicija. Naj bosta Γ1 = (V1, E1) in Γ2 = (V2, E2) poljubna (di)grafa. (Di)grafa Γ1 in Γ2 sta izomorfna, ˇce med njima obstaja kak izomorfizem (di)grafov, to je bijektivna preslikava φ:V1 →V2, za katero velja, da za poljuben par vozliˇsˇc u, v ∈V1 velja:
(u, v)∈E1 ⇔(φ(u), φ(v))∈E2
To oznaˇcimo z Γ1 ∼= Γ2. Izomorfizem (di)grafov torej ohranja sosednost.
Seveda je naˇceloma laˇzje pokazati, da dva (di)grafa nista izomorfna kot da sta. To lahko pokaˇzemo tako, da ugotovimo, na primer, da (di)grafa nista istih redov, da nimata enakih zaporedij stopenj, nimata enakega ˇstevila komponent povezanosti in podobno.
Poglejmo si sedaj ˇse definicijo simetrije (di)grafa, ki ji pravimo avtomorfizem (di)grafa.
9
Definicija. Naj bo Γ = (V, E) poljuben (di)graf. Avtomorfizem (di)grafaΓ je bijektivna preslikava φ :V → V, ki ohranja sosednost. Za poljuben par vozliˇsˇc u, v ∈V mora torej veljati:
(u, v)∈E ⇔(φ(u), φ(v))∈E.
Mnoˇzico vseh avtomorfizmov digrafa Γ oznaˇcimo z Aut(Γ). Avtomorfizmi so izomorfizmi digrafa Γ samega vase, saj so permutacije mnoˇzice vozliˇsˇc digrafa, ki ohranjajo sosednost.
Izkaˇze se, da je mnoˇzica Aut(Γ) celo zaprta za operacijo komponiranja.
Trditev 2.6. Naj bo Γ poljuben digraf. Mnoˇzica Aut(Γ) je grupa za operacijo kompozi- tuma preslikav.
Zato mnoˇzici Aut(Γ) obiˇcajno pravimo kar grupa avtomorfizmov digrafa Γ.
Za konec tega razdelka si poglejmo ˇse nekatere druˇzine in konstrukcije digrafov.
Definicija. Naj bosta Γ1 = (V1, E1) in Γ2 = (V2, E2) dva digrafa. Tedaj je digraf Γ2 poddigraf grafa Γ1, ˇce jeV2 ⊂V1 inE2 ⊂E1.
Definicija. Naj bo n ≥ 3 poljubno naravno ˇstevilo. Usmerjeni cikel reda n je digraf z mnoˇzico vozliˇsˇc Zn, kjer so povezave oblike (i, i+ 1), za i ∈ Zn. Graf imenujemo tudi cikliˇcen digrafin ga oznaˇcimo s Cn. Digraf je reda n in je 1-regularen digraf.
Definicija. Naj bosta Γ1 = (V1, E1) in Γ2 = (V2, E2) poljubna digrafa. Njuna (disjunk- tna) unijaje tedaj definirana kot digraf Γ = (V1tV2, E1tE2), pri ˇcemer znaktpredstavlja disjunktno unijo. Red digrafa Γ je torej vsota redov obeh digrafov. Drugaˇce povedano, to je digraf, ki da dobimo tako, da loˇceno zdruˇzimo obe kopiji digrafov. Tak digraf oznaˇcimo kot Γ1tΓ2.
10
Poglavje 3
Cayleyjevi digrafi
V tem poglavju se posveˇcamo glavni temi diplomskega dela, to so Cayleyjevi digrafi v povezavi z grupami. V najveˇcji meri se opiramo na vire [1], [2] in [13], ter si pri risanju pomagamo s programom Group Explorer. ˇCe temu ni tako, je vir posebej naveden.
Kot smo ˇze omenili, so Cayleyjevi digrafi ime dobili po Arthurju Cayleyju, ki je bil an- gleˇski matematik 19. stoletja. Prviˇc je te grafe omenil leta 1878. Cayleyjev digraf lahko konstruiramo za vsako (konˇcno) grupo Gin poljubno podmnoˇzico S ⊂G. So eden izmed naˇcinov vizualizacije grup in nekaterih njihovih lastnosti. Dajejo nam vpogled v strukturo in samo kompleksnost grupe.
3.1 Pojem Cayleyjevega digrafa
Za zaˇcetek si poglejmo definicijo Cayleyjevih digrafov, povzeto po viru [12], in Cayleyjevih grafov ter nekatere njihove osnovne lastnosti.
Definicija. Naj bo G poljubna konˇcna grupa in S ⊂ G njena taka podmnoˇzica, da e /∈ S. Cayleyjev digraf Γ = Cay(G;S) grupe G glede na podmnoˇzico S je usmerjeni graf z mnoˇzico vozliˇsˇc G in mnoˇzico usmerjenih povezav ali lokov E ={(g, h)∈ G×G: g−1h∈S}={(g, gs) :g ∈G, s∈S}.
Bralec lahko opazi, da je mnoˇzica {gs : s ∈ S} mnoˇzica naslednikov vozliˇsˇca g ∈ G, mnoˇzica {gs−1 :s∈S} pamnoˇzica predhodnikov vozliˇsˇcag ∈G.
g
gs1 gs2 gs3
gs1-1 gs2-1 gs3-1
Slika 3.1: Mnoˇzica predhodnikov in mnoˇzica naslednikov.
Razmislimo sedaj za uvod, kdaj je Cayleyjev digraf pravzaprav graf.
11
Trditev 3.1. Cayleyjev digraf Cay(G;S) je graf natanko tedaj, ko je S =S−1.
Dokaz. Naj bo Γ = Cay(G;S) digraf. Predpostavimo najprej, da je Γ graf. Potem za vsako usmerjeno povezavo (g, h) ∈ E(Γ) obstaja tudi povezava (h, g) ∈ E(Γ). Naj bo sedaj s ∈ S poljuben in pokaˇzimo, da je s ∈ S−1. Po definiciji je (e, s)∈ E(Γ), torej po predpostavki velja tudi (s, e)∈E(Γ). Potem obstajaes ∈S, da jeses =e, od koder seveda sledi es=s−1 in tako s−1 ∈S. SlediS ⊆S−1. Podobno pokaˇzemo ˇse, da je S−1 ⊆ S, od koder potem sledi S =S−1.
Predpostavimo sedaj ˇse, da je S = S−1 in pokaˇzimo, da je Γ graf. Ker je podmnoˇzica S zaprta za inverze, za vsak s ∈ S obstaja s−1 ∈ S. Za vsako usmerjeno povezavo (g, gs)∈E(Γ) torej v Γ obstaja povezava (gs,(gs)s−1) = (gs, g). S tem smo pokazali, da je digraf Γ res graf, saj za vsako povezavo v Γ obstaja tudi njena obratna povezava.
Spomnimo se, da v primeru komutativnih grup operacijo obiˇcajno piˇsemo aditivno s +, zato namesto gs piˇsemo g +s. ˇCe je grupa G cikliˇcna in je S = S−1 (oziroma −S v primeru aditivno pisane operacije), potem pripadajoˇcemu Cayleyjevemu grafu pravimo cirkulant. Primer cirkulanta je Cay(Z6,{±1}), ki je prikazan na sliki 2.1 (levi graf).
Definicija. Naj bo Cay(G;S) Cayleyjev digraf in s ∈ S. Povezave oblike (g, gs) tedaj imenujemo s-povezave.
Pri upodobitvi Cayleyjevih digrafov lahko zaradi veˇcje preglednostis-povezave, za razliˇcne s ∈S, prikaˇzemo z razliˇcnimi barvami ali tipom ˇcrte (ˇcrtkano, polno ˇcrto, pikicami, itd.).
Dogovorimo se, da bomo tako postopali v tem diplomskem delu in bomo s-povezave za razliˇcne s ∈ S oznaˇcevali z razliˇcnimi barvami. Ko bomo torej govorili o barvi povezave bomo pravzaprav mislili na ustrezen s ∈ S. V Cayleyjevem digrafu je torej vsakemu g ∈ G dodeljeno vozliˇsˇce, vsakemu elementu s ∈ S pa so dodeljene usmerjene povezave doloˇcene barve.
Smer usmerjene povezave pomeni mnoˇzenje elementa g ∈G z elementom s∈ S z desne.
Pri tem je konˇcno vozliˇsˇce s-povezave z zaˇcetkom v g enako gs = h , ki je prav tako element grupe G. Usmerjena povezava torej kaˇze od vozliˇsˇca g proti vozliˇsˇcu h. Opo- mnimo, da bo sledenje smeri usmerjene povezave ves ˇcas ustrezalo mnoˇzenju z desne. V primeru dvosmerne s-povezave med elementoma g in h bomo ti povezavi pri upodobitvi digrafa nadomestili z eno samo povezavo brez usmeritve (primer so modre povezave na Cay(S3;S) na sliki 3.2).e
Trditev 3.2. Naj bo Cay(G;S) Cayleyjev digraf grupe G za podmnoˇzico S. Element s ∈S nam generira dvosmerne povezave natanko tedaj, ko je reda 2 v grupi G.
Dokaz. Naj bo Γ = Cay(G;S). Predpostavimo, da nam nek element s ∈ S generira dvosmerne povezave. Ker od e dos pridemo po s-povezavi, moramo torej tudi od s doe priti po s-povezavi, od koder sledi, da je ss=e, to je, s je reda 2.
Predpostavimo sedaj, da je element s ∈ S reda 2. Tedaj za poljuben g ∈ G velja, da je (gs)s =g, torej so s-povezave res dvosmerne, saj imamo v Γ tako s-povezave (g, gs) kot
s-povezave (gs, g).
12
V nadaljevanju poglejmo, kako lahko iz Cayleyjevega digrafa razberemo rede elementov grupe G(povzeto po viru [10]).
Trditev 3.3. Naj bo Γ = Cay(G;S) digraf in s ∈ S tak, da s2 6= e. Tedaj nam s- povezave v Γ dajo disjunktno unijo samih usmerjenih ciklov dolˇzine k (k ≥ 3), kjer je k red elementa s v G.
Dokaz. Ker jesredak, jesk =e, poleg tega jesj 6=eza vse 1≤j < k. Naj bog ∈Gpo- ljuben. Potem v digrafu Γ dobimo usmerjeni obhod oblike (g, gs, gs2, . . . , gsk−1, gsk=g).
Ta usmerjeni obhod je pravzaprav usmerjeni cikel, saj so po pravilu krajˇsanja v grupi vsa vozliˇsˇca paroma razliˇcna. Dobljeni cikel je seveda dolˇzinek. Da se usmerjeni cikli dolˇzine k, ki nam jih generira s, med seboj ne dotikajo, sledi direktno iz definicije Cayleyjevih digrafov, saj bi v nasprotnem primeru za neko vozliˇsˇce h dveh takih ciklov veljalo, da s-povezava izh pripelje do dveh razliˇcnih vozliˇsˇc, kar je seveda nemogoˇce.
Zgled: Oglejmo si Cayleyjev digraf simetriˇcne grupeS3za podmnoˇziciS ={(12),(123),(132)}= S−1 inSe={(123),(12)} 6=Se−1.
id
(12)
(123) (132)
(13) (23)
id
(12)
(123) (132)
(23) (13)
Slika 3.2: Cayleyjev digraf Cay(S3;{(12),(123),(132)}) inCay(S3;{(12),(123)}).
.
Dobljena digrafa seveda nista enaka, saj v drugem primeru podmnoˇzica Se ni zaprta za inverze, ker (132) ∈/ S, zaradi ˇe cesar dobljeni digraf ni graf. Crne povezave ustrezajoˇ mnoˇzenju z elementom (123) ∈ Se (z desne) in nam dajo dva loˇcena usmerjena 3-cikla, medtem ko modre povezave ustrezajo mnoˇzenju z elementom (12). Modre povezave so dvosmerne, saj je (12) reda 2, kar se ujema z zgornjo trditvijo 3.2.
Trditev 3.4. ([10]) Naj bo Gkonˇcna grupa inS ⊂Gnjena podmnoˇzica, za kateroe /∈S.
Tedaj je Cayleyjev digraf Cay(G;S) regularen z izhodno in vhodno stopnjo enako moˇci mnoˇzice S, to je |S|. Podobno je vsak Cayleyjev graf Cay(G;S) regularen, kjer stopnja grafa sovpada z moˇcjo povezavne mnoˇzice S.
Dokaz. Naj bo Γ = Cay(G;S) in naj bo g ∈ G poljuben. Po definiciji Cayleyjevega digrafa je mnoˇzica naslednikov vozliˇsˇca g ravno {gs : s ∈ S}. Ker po pravilu krajˇsanja za s1 6= s2 velja gs1 6= gs2, ima torej g natanko |S| naslednikov. Vsa vozliˇsˇca digrafa Γ imajo torej izhodno stopnjo enako |S|. Podobno pokaˇzemo, da je vhodna stopnja vseh vozliˇsˇc enaka |S|, saj je mnoˇzica predhodnikov vozliˇsˇca g enaka {gs−1 :s ∈ S}. Od tod sledi, da je digraf Γ res regularen. Poslediˇcno je tudi vsak Cayleyjev graf regularen, kjer
13
je stopnja grafa enaka |S|.
Obrat trditve 3.4 ne velja. Ni vsak regularen digraf Cayleyjev. Primer takˇsnega digrafa je na primer graf, ki je unija dveh ciklov in sicer C4 tC3, ki je prikazan na spodnji sliki 3.3.
u v
w z
a b
c
Slika 3.3: Nepovezan graf, ki je unija dveh ciklov.
Zakaj ta graf ni Cayleyjev graf? Predpostavimo, da je graf C3 tC4 Cayleyjev za grupo G. Ker je graf reda 7, mora biti tudi grupa G reda 7. Edina grupa reda 7 je cikliˇcna grupa Z7. Po trditvi 3.3 nam vsak s∈Z7\{0} da ustrezen 7-cikel v Cayleyjevem digrafu Cay(Z7;S), kjer je s ∈ S (saj so vsi elementi v grupi reda 7). Ker naˇs graf ne premore nobenega 7-cikla, to ni mogoˇce. Torej C3tC4 res ni Cayleyjev graf. Bralec lahko tudi pokaˇze, da je vsak Cayleyjev (di)graf Cay(Z7;{a,−a})∼=C7 za vsak a∈Z7\{0}. Seveda bi lahko dejstvo, da C3tC4 ni Cayleyjev, utemeljili tudi tako, da bi opazili, da ta graf ni vozliˇsˇcno tranzitiven (premore namreˇc vozliˇsˇca, ki so na 3-ciklu, in vozliˇsˇca, ki niso na nobenem 3-ciklu). Izkaˇze pa se, da je vsak Cayleyjev (di)graf vozliˇsˇcno tranzitiven (komentar po trditvi 3.7). A o vozliˇsˇcni tranzitivnosti ne bomo veliko govorili.
3.2 Grupe in Cayleyjevi digrafi
V tem razdelku si pogledamo, kako lahko iz Cayleyjevega digrafa dane grupe, glede na neko podmnoˇzico S, razberemo nekatere lastnosti te grupe in kako se lastnosti grup izraˇzajo v razliˇcnih Cayleyjevih digrafih dane grupe. Pri tem si pomagamo z zgoraj omenjenimi definicijami, izreki in trditvami ter poskuˇsamo izpeljati ˇse kakˇsne nove rezultate. Najprej si poglejmo naslednji zgled, kjer so prikazani Cayleyjevi digrafi grupe Z4 za nekatere pod- mnoˇzice S⊂Z4.
Zgled: Cayleyjevi digrafiCay(Z4;Si) (i∈ {1,2, . . .6})) zaS1 ={1},S2 ={2},S3 ={3}, S4 ={1,2}, S5 ={1,3} inS6 ={1,2,3}.
0 1
3 2
0
2 1
3
0
3
1
2
14
0 1
3 2
0 1
2 3
0 1
2 3
Slika 3.4: Cayleyjevi digrafi grupeZ4 za razliˇcne podmnoˇzice S.
Iz zgornje slike 3.4 razberemo, da je izgled Cayleyjevega digrafa precej odvisen od izbire podmnoˇzice S. Kaj lahko razberemo iz konkretnega Cayleyjevega digrafa, je torej odvi- sno od izbire podmnoˇzice S. V veˇcini zgornjih primerov je digraf povezan, medtem ko za podmnoˇzico S = {2} digraf ni povezan. Kaj nam povezanost pove o grupi G in pod- mnoˇzici S? Vemo, da je cikliˇcna grupa Z4 grupa, generirana z enim samim elementom, pri ˇcemer je ta element lahko 1 ali 3. Po drugi strani element 2 ne generira cele grupe Z4, saj je 2 ∈ Z4 reda 2. Povezanost oziroma nepovezanost Cayleyjevega digrafa Cay(G;S) nam torej pove, ali podmnoˇzicaSgenerira grupoGali ne. Zapiˇsimo to dejstvo kot trditev.
Trditev 3.5. Cayleyjev digrafCay(G;S) je povezan natanko tedaj, ko je G=hSi (to je, ko podmnoˇzica S generira grupo G).
Dokaz. Naj bo Γ = Cay(G;S). Denimo najprej, da je digraf Γ povezan, in pokaˇzimo, da v tem primeru S generira grupo G, to je G=hSi. Vzemimo poljuben g ∈G. Potem po definiciji povezanosti v temeljnem grafu digrafa Γ obstaja pot od e dog. Torej za nek k in neke s1, s2, . . . , sk ∈ S ter a1, a2, . . . , ak ∈ {1,−1} velja g = sa11sa22. . . sakk, od koder takoj sledi g ∈ hSi. Pri tem vrednost ai = 1 pomeni, da ustreznosi-povezavo prehodimo vzdolˇz usmeritve v Γ, vrednost ai =−1 pa proti usmeritvi v Γ. Torej S generira grupo G.
Denimo sedaj, da S generira grupo G in pokaˇzimo, da je digraf Γ povezan. Pokazati moramo torej, da med poljubnima g, h ∈ G obstaja vsaj ena pot v temeljnemu grafu digrafa Γ. Ker velja, da je g−1h ∈ G = hSi, torej obstajajo k ∈ N, s1, s2, . . . , sk ∈ S in a1, a2, . . . , ak ∈ {1,−1}, da jeg−1h=sa11sa22· · ·sakk. Tedaj je (g, gsa11, gsa11sa22, . . . , gsa11sa22· · ·sakk) pot v temeljnemu grafu digrafa Γ odg doh=gsa11sa22· · ·sakk. Torej je digraf Γ povezan.
V primeru, da je grupa Gkonˇcna, lahko povemo celo veˇc.
Trditev 3.6. Naj bo G konˇcna grupa in S ⊂ G taka podmnoˇzica, da e /∈ S. Tedaj je Cayleyjev digraf Cay(G;S) krepko povezan natanko tedaj, ko je hSi=G.
Dokaz. Ker je G konˇcna grupa, so vsi elementi si ∈ S konˇcnega reda. Torej lahko vsak si−1 v dokazu trditve 3.5 nadomestimo z sim−1, kjer je m red elementa si. Na ta naˇcin sicer lahko dobimo usmerjeni sprehod, ki ni usmerjena pot, ampak se ga da vedno
reducirati v usmerjeno pot.
Poglejmo sedaj Cayleyjev digraf za podmnoˇzico S, ki nam generira dano grupo in pod- mnoˇzico S, ki nam grupe ne generira.
15
Zgled: Zanima nas ali podmnoˇzica S ={r2, z, zr3} generira grupoG=D8 ali ne.
Ce ˇˇ zelimo na to vpraˇsanje odgovoriti direktno, brez uporabe digrafov, je v sploˇsnem potrebnega veliko raˇcunanja (ˇse posebej, ˇce gre za nekoliko veˇcje grupe). Pogledati mo- ramo,sta ali lahko vsak element iz grupeD8 dobimo kot produkt elementov iz podmnoˇzice S in njihovih inverzov. V naˇsem primeru tako na primer element r dobimo kot produkt z·zr3·r−2 in element zr5 kot produkt zr3 inr2. Na ta naˇcin bi lahko po nekaj raˇcunih ugotovili, da podmnoˇzica S generira grupo D8, saj z elementi iz S dobimo vse elemente grupe D8 ={1, r, r2, r3, r4, r5, r6, r7, z, zr, zr2, zr3, zr4, zr5, zr6, zr7}. To lahko bralec pre- veri sam.
Pri veˇcjih grupah se zna zgoditi, da bi na ta naˇcin kak element kar dolgo iskali. V zgornji trditvi pa smo videli, da lahko ˇze z risanjem Cayleyjevega digrafa ugotovimo ali nam neka podmnoˇzica generira grupo ali ne. Seveda bo tudi tu potrebnega nekaj raˇcunanja, a je ta pristop precej bolj sistematiˇcen.
1
r2
r4 r6
r7 z
zr3
r3 r5
r
zr zr2
zr4 zr5
zr6
zr7
Slika 3.5: Cayleyjev digraf Cay(D8;{r2, z, zr3}).
Iz zgornje slike 3.5 vidimo, da je Cayleyjev digraf grupe D8 za mnoˇzico S = {r2, z, zr3} povezan digraf, torej nam podmnoˇzica S res generira celotno diedrsko grupo D8.
Zgled: Kaj pa v primeru, ko je grupaG diedrska grupaD4? Ali nam tokrat podmnoˇzica S ={r2, z} generira celotno grupo?
1 r2
z zr2
r r3
zr3 zr
Slika 3.6: Cayleyjev digraf Cay(D4;{r2, z}).
.
16
Iz slike 3.6 opazimo, da Cayleyjev digraf v tem primeru ni povezan, torej nam mnoˇzica S ={r2, z} ne generira celotne diedrske grupe D4. Iz digrafa tudi vidimo, da elementa r ne moremo dobiti kot kombinacijo elementov r2 in z, saj r ni v isti komponenti poveza- nosti kot 1.
Kot smo omenili ˇze v uvodu, Cayleyjevi (di)grafi dopuˇsˇcajo precejˇsnjo mero simetrije.
Trditev 3.7. ([6]) Naj bo Cay(G;S) Cayleyjev digraf grupe G za podmnoˇzico S. Potem za vsak h∈G velja, da je preslikava:
th :g 7→hg, avtomorfizem digrafa Cay(G;S).
Dokaz. Naj bo Γ = Cay(G;S) in th : G → G preslikava definirana s predpisom th(g) = hg za vsak g ∈ G. Pokaˇzimo, da je preslikava th bijekcija, ki ohranja sose- dnost. Ta preslikava je injektivna, saj v grupi velja pravilo krajˇsanja z iste strani. Torej th(g1) = hg1 = hg2 = th(g2) le v primeru, ko je g1 = g2. Prav tako je surjektivna, saj za g ∈ G velja th(h−1g) = g. Poglejmo ˇse ali ohranja sosednost. Pokaˇzimo, da ˇce je (g, gs)∈E(Γ), potem je (th(g), th(gs))∈E(Γ). Ker jeth(gs) =h(gs) = (hg)s= (th(g))s je torejth(gs) naslednik vozliˇsˇcath(g), od koder sledi, da je preslikavath res avtomorfizem
digrafa Γ.
Mnoˇzenje z elementom grupeG na levi je torej avtomorfizem digrafa Cay(G;S). ˇSe veˇc, ti avtomorfizmi ohranjajo ”barve” povezav. To med drugim pomeni, da lahko vozliˇsˇca vedno preimenujemo tako, da bo neko drugo vozliˇsˇce ”postalo” nevtralni element e ∈G, in bo digraf ˇse vedno izgledal povsem enako, s povezavami iste barve. Posledica zgornje trditve je vozliˇsˇcna tranzitivnost Cayleyjevih digrafov. To pomeni, da za poljuben par vozliˇsˇc g in h, obstaja φ ∈ Aut(Γ), ki nam g preslika v h. Poglejmo si ilustracijo tega dejstva na naslednjem primeru.
Zgled: Oglejmo si Cayleyjev digraf za kvaternionsko grupo Q in podmnoˇzico S ={i, j}, to je Cay(Q;{i, j}), ki je upodobljen na levi strani slike 3.7.
k
1
j i
-j
-i -1
-k
-1
-k
k
-j
j
i -i
1 k
1
j i
-j
-i -1
-k
Slika 3.7: Cayleyjev digraf kvaternionske grupe Cay(Q;{i, j}) in prikaz mnoˇzenja na levi kot avtomorfizem tega digrafa.
.
17
Sedaj s pomoˇcjo ustreznega avtomorfizma iz trditve 3.7 preimenujmo vozliˇsˇca digrafa Cay(Q;{i, j}) tako, da bo ”novo” vozliˇsˇce 1 postalo ”staro” vozliˇsˇce k. Imena vseh vo- zliˇsˇc moramo torej pomnoˇziti z leve z −k (saj je −k·k = 1). Na sliki 3.7 opazimo, da smo dobili Cayleyjev digraf, ki ima povsem enako strukturo, kot prvoten. Sestavljen je iz dveh modrih in dveh ˇcrnih 4-ciklov, ki se med seboj povezujejo na enak naˇcin.
Trditev 3.8. Naj bo Γ = Cay(G;S), kjer je G konˇcna grupa in S ⊆ G \ {e} taka podmnoˇzica, da je hSi=G. Tedaj ima digraf Γ naslednje ˇstiri lastnosti:
(i) Γ je krepko povezan.
(ii) Za vsak g1, g2 ∈ G obstaja v Γ najveˇc ena usmerjena povezava, ki gre od vozliˇsˇca g1 ∈G do vozliˇsˇca g2 ∈G.
(iii) Vsako vozliˇsˇce g ∈ G ima za vsak s ∈ S natanko eno s-povezavo, ki se zaˇcne v g, in natanko eno, ki se konˇca v g.
(iv) ˇCe se dve razliˇcni zaporedji usmerjenih povezav, ki izhajata iz istega vozliˇsˇca g, konˇcata v istem vozliˇsˇcu h, potem ti isti zaporedji usmerjenih povezav iz poljubnega zaˇcetnega vozliˇsˇca u∈G vodita v isto vozliˇsˇce.
Dokaz. Naj bo Γ = Cay(G;S). Da velja (i) smo pokazali ˇze pri trditvi 3.6. Lastnost (ii) velja, ker v grupi velja pravilo krajˇsanja torej g1·s1 =g2 =g1·s2 natanko tedaj, ko je s1 =s2. Enaˇcba g1·s =g2 v Gje tako enoliˇcno reˇsljiva nas∈G. V odvisnosti od tega ali je s ∈S ali ne, potem povezava od g1 dog2 v Γ obstaja oziroma ne obstaja. Lastnost (iii) sledi neposredno iz definicije Cayleyjevih digrafov. Zadnjo lastnost zopet pokaˇzemo s pravilom krajˇsanja v grupi. Naj bosta s1, s2, . . . , sn in es1,es2, . . . ,esm dve poljubni razliˇcni zaporedji elementov izS, da jeg·(s1s2· · ·sn) =g·(es1es2· · ·esm) =h. Po pravilu krajˇsanja velja (s1s2· · ·sn) = (es1es2· · ·esm). Od tod sledi, da je u·(s1s2· · ·sn) =u·(es1es2· · ·esm), kot
smo trdili.
Izkaˇze se, da velja tudi neke vrste obrat. Torej, vsak digraf, ki ustreza zgornjim ˇstirim lastnostim, je Cayleyjev digraf za kakˇsno konˇcno grupoG. V primeru, da nas zanima ali je nek digraf Cayleyjev, moramo pogledati ali lahko povezave digrafa obarvamo v skladu z zgornjo trditvijo. Vsaka izhodna povezava v danem vozliˇsˇcu mora torej biti svoje barve.
Barv imamo po lastnosti (iii) natanko toliko, kolikor je izhodna stopnja (poljubnega) vo- zliˇsˇca. Pri barvanju moramo upoˇstevati zaporedja barv, ki nas pripeljejo v isto vozliˇsˇce.
Nikoli se ne sme zgoditi, da se dva cikla iste barve med seboj dotikata. Z barvanjem lahko po trditvi 3.7 zaˇcnemo v kateremkoli vozliˇsˇcu. ˇCe nam uspe pri barvanju digrafa vse to upoˇstevati, potem je ta digraf lahko Cayleyjev digraf neke konˇcne grupe (za katero veljajo pogoji, ki so doloˇceni z barvanjem). Poiskati moramo le ˇse elemente grupe. Ker mora v sploˇsnem biti digraf krepko povezan, bo pripadajoˇca mnoˇzica ”barv” generirala iskano grupo. Dokaz, da je tak digraf res Cayleyjev in iskanje ustrezne grupe v sploˇsnem, izpustimo, saj to zahteva veliko dela. Oglejmo si le ilustracijo obrata na nekaj primerih.
Zgled: Za zaˇcetek si poglejmo enostavnejˇsi primer. Zanima nas, ali je digraf Γ na spodnji sliki 3.8 Cayleyjev digraf za kakˇsno grupo G in ˇce je, za katero.
18
Slika 3.8: Ali je digraf Cayleyjev?
.
Digraf na sliki je reda 8 in je 2-regularen, saj sta izhodna in vhodna stopnja enaki 2. Di- graf je torej lahko Cayleyjev digraf za kakˇsno grupo reda 8 (teh je 5). Grupe reda 8 so na primerZ8, D4 inQ. Naloge bi se torej lahko lotili tako, da bi konstruirali vse 2-regularne Cayleyjeve digrafe vseh petih grup reda 8 in potem ugotavljali, ˇce je kateri izomorfen di- grafu Γ. Kar je seveda preveˇc zamudno. Zato se naloge lotimo drugaˇce. Opazimo lahko, da v digrafu dobimo usmerjeni 8-cikel (ˇcrne barve), ki nam ga generira element reda 8.
Drugi element je zaradi dvosmernosti povezav lahko le reda 2 (povezave brez usmeritev lahko sicer dobimo tudi v primeru, ko je v podmnoˇzici S inverz obravnavanega elementa reda veˇc kot 2, vendar bi v tem primeru v vsakem vozliˇsˇcu imeli vsaj dve neusmerjeni povezavi). Grupa je tako lahko le cikliˇcna grupaZ8. Edini element reda 2 v grupi Z8 je 4.
Na sliki 3.9 lahko opazimo, da nas zaporedje treh ˇcrnih in ene modre povezave iz vozliˇsˇca e pripelje nazaj v vozliˇsˇce e. Sledi torej, da je 3a+ 4≡ 0 (mod 8) in zato 3a ≡ 4 (mod 8). Od tod sledi, da je a enak 4, vendar v grupiZ8 4 ni reda 8. Torej digraf ni Cayleyjev za cikliˇcno grupo Z8.
Lotimo se naloge ˇse z barvanjem, brez da bi se ozirali na moˇzne konkretne grupe. Zanima nas torej, ali je mogoˇce digraf pobarvati z dvema barvama tako, da bodo izpolnjene vse lastnosti po trditvi 3.8. Za zaˇcetek doloˇcimo a, b∈S, tako daa ustreza ˇcrni, b pa modri barvi povezave. Izberimo poljubno vozliˇsˇce in ga oznaˇcimo z e. Vidimo, da iz e po treh ˇ
crnih in eni modri povezavi zopet pridemo nazaj v isto vozliˇsˇcee, torej je (a3b) = e(tokrat operacijo v iskani grupi piˇsemo kar multiplikativno). Prav tako vidimo, da iz vozliˇsˇcab s tem istim zaporedjem (a3b) ne pridemo nazaj v vozliˇsˇceb, temveˇc v vozliˇsˇcea. S tem ne velja (iv) lastnost iz trditve 3.8, torej digraf ni Cayleyjev.
a a
a b
a
a a
b
e e b
Slika 3.9: Zaporedje a3b nas v prvem primeru pripelje v isto vozliˇsˇce, v drugem primeru pa ne.
19
Zgled: Poglejmo si ˇse (di)graf Γ na sliki 3.10. Zanima nas, ali gre za Cayleyjev graf kakˇsne konˇcne grupe G.
Slika 3.10: Enostavni graf Γ. Ali je Cayleyjev?
.
Ce ˇˇ zelimo ugotoviti, ali je graf Γ Cayleyjev za kakˇsno grupo (in za katero), moramo pre- veriti ali ga lahko pobarvamo tako, da bo ustrezal vsem ˇstirim zahtevam trditve 3.8. Ker gre za povezan graf reda 24, bo imela morebitna ustrezna grupa 24 elementov. Graf je 3-regularen. Oˇcitno je, da sta izpolnjeni prvi dve zahtevi trditve 3.8. Tokrat usmeritev povezav nimamo, kar je lahko bodisi posledica dejstva, da so vsi elementi iz S reda 2, bodisi za vsak s∈S v S najdemo s−1.
Kot reˇceno, imamo torej v S ali tri elemente reda 2 ali en element reda 2 in en ele- ment reda veˇc kot 2 (ter njegov inverz). Element reda veˇc kot 2 je lahko na primer reda 4, 6 ali 8, saj v grafu najdemo 4-cikle, 6-cikle in 8-cikle. Ta element nam mora po tr- ditvi 3.3 generirati disjunktne cikle. Ker je moˇznosti veˇc, si oglejmo le nekatere izmed teh.
Za zaˇcetek doloˇcimo a, b ∈ S tako da b ustreza elementu reda 2, a pa elementu reda 6 (modre povezave na sliki 3.11). Poglejmo, koliko je moˇznosti za disjuntkne unije 6-ciklov.
Ker vsako vozliˇsˇce leˇzi na 6-ciklu, lahko izberemo poljubno vozliˇsˇce in ga oznaˇcimo z e.
Opazimo, da iz vozliˇsˇcaeizhajajo le tri povezave, torej imamo 3 moˇznosti za izbiro, kateri dve povezavi tvorita 6-cikel, ki ustreza mnoˇzenju z elementom a (levi graf na sliki 3.11).
Moˇznost, oznaˇcena z zeleno barvo, odpade, ker ti povezavi ne leˇzita na nobenem 6-ciklu.
Ostaneta nam torej le dve moˇznosti za pripadajoˇci 6-cikel skozi e, ki ustreza mnoˇzenju z a. Bralec se bo zlahka prepriˇcal, da vsaka od njiju enoliˇcno doloˇca disjunktno unijo 6-ciklov generiranih z a (desna grafa na sliki 3.11). Na zaˇcetnem 6-ciklu lahko poljubno izberemo usmeritev.
e e e
a b
b a
Slika 3.11: Dve moˇznosti za disjunktne unije 6-ciklov (modre povezave).
20
Poglejmo si prvo moˇznost za izbiro 6-ciklov (srednji graf na sliki 3.11). Glede na smer na zunanjih 6-ciklih velja bodisi abab = e bodisi aba−1b = e. Potem mora po trditvi 3.8 veljati, da nas eno od teh dveh zaporedij iz kateregakoli vozliˇsˇca pripelje nazaj v isto vozliˇsˇce. Ugotovimo, da to ne velja vedno, saj na primer iz vozliˇsˇca a, z nobenim od zaporedij (abab) in (aba−1b) ne pridemo nazaj v vozliˇsˇce a (slika 3.12). S tem ni izpolnjena (iv) zahteva iz trditve 3.8. Podobno bi lahko pokazali ˇse za drugo izbiro 6- ciklov in ugotovili, da tudi v tem primeru ni izpolnjena (iv) zahteva. Torej digraf ni Cayleyjev za podmnoˇzico z elementom reda 6.
e a
b
e a
Slika 3.12: Dve moˇzni usmeritvi zunanjega 6-cikla (prva moˇznost disjunktnih 6-ciklov).
Poglejmo sedaj moˇznosti, ko je en element reda 2, drugi reda 4. Pri tem naj a ustreza elementu reda 4 (modre povezave), b pa elementu reda 2 (ˇcrne povezave). Podobno kot zgoraj lahko ugotovimo, da imamo le eno moˇznost za izbiro dveh povezav, ki tvorita 4-cikel (zeleni povezavi na sliki 3.11), saj morata imeti a in a−1 skupnega soseda. Ko doloˇcimo 4-cikel, ga lahko poljubno usmerimo. Bralec se bo zopet zlahka prepriˇcal, da je s tem disjunktna unija 4-ciklov, ki ustrezajo mnoˇzenju z a enoliˇcno doloˇcena. Kako pa so usmerjeni ostali 4-cikli? Moˇznosti za usmeritev sta v naˇsem primeru dve. Izkaˇze se, da je le ena moˇznost prava (levi graf na sliki 3.13). V primeru usmeritve na desnem grafu slike 3.13 (iv) pogoj iz trditve 3.8 namreˇc ni izpolnjen. Velja namreˇc ababab = (ab)3 = e, vendar iz vozliˇsˇca a ne pridemo v isto vozliˇsˇce, ampak v vozliˇsˇce a−1. V primeru usmeritve, prikazane na levi strani, pa po konˇcanem barvanju ugotovimo, da so izpolnjene vse zahteve trditve 3.8 in je digraf Cayleyjev digraf za podmnoˇzico z elementom reda 2 in reda 4 (ter njegovim inverzom). Bralec lahko sam preveri, da gre za temeljni graf digrafa Cay(S4,{(12),(1234)}) (slednji je upodobljen na sliki 3.14). V podmnoˇzico S torej vzamemo tudi inverz elementa (1234), to je element (1432), saj je bil izhodiˇsˇcni Γ (neusmerjen) graf.
e a e
b b
a
a-1
Slika 3.13: Dve moˇznosti za usmeritev 4-ciklov (modre povezave).
21
Poglejmo, ali je ˇse kakˇsna moˇznost za izbiro podmnoˇzice S. Zgoraj smo ˇze omenili, da so v podmnoˇzici S lahko elementi reda 2,4, 6 ali 8. V S tako ne more biti element reda 7, saj graf zaradi dvodelnosti nima ciklov lihe dolˇzine, prav tako v nobeni grupi reda 24 ni elementa reda 7 (saj 7 ne deli 24). Poglejmo si ˇse eno izmed moˇznosti, ki nam je ostala.
To je moˇznost, ko so v podmnoˇzici S trije elementi reda 2. Izkaˇze se, da je v tem primeru prav tako graf mogoˇce pobarvati s tremi barvami tako, da ustreza vsem zgornjim zahtevam trditve 3.8. Torej je pobarvani graf krepko povezan, med dvema sosednjima vozliˇsˇcema obstaja najveˇc ena s-povezava (za vsaks∈S), itd. Moˇznost ustreznega barvanja digrafa je prikazana na desni strani slike 3.14. Bralec se lahko prepriˇca, da gre za Cayleyjev digraf grupe S4 glede na podmnoˇzico S ={(12),(23),(34)}.
e e
Slika 3.14: Cayleyjeva digrafaCay(S4,{(12),(1234)}) in Cay(S4,{(12),(23),(34)}).
Na podoben naˇcin bi lahko, brez omenjanja grup reda 10, pokazali, da Petersenov graf (slika 3.15) ni Cayleyjev graf. Bralec lahko sam pokaˇze, da sta naˇceloma le dve moˇznosti.
Bodisi je S sestavljena iz treh elementov reda 2, bodisi iz enega elementa reda 2 in enega reda 5 ali 10 ter njegovega inverza. V nobenem primeru zahteve iz trditve 3.8 niso izpolnjene (podrobnosti prepuˇsˇcamo bralcu).
Slika 3.15: Petersenov graf ni Cayleyjev graf.
V nadaljevanju si poglejmo, katere lastnosti grup ˇse lahko razberemo iz Cayleyjevih di- grafov. Zgoraj smo ˇze omenili, da sledenje smeri povezave pomeni mnoˇzenje z elementom s ∈S z desne. Produktov torej ni teˇzko opazovati. Vzeti moramo le pravo podmnoˇzico S ⊂ G in potem iz izbranega elementa slediti ustreznim povezavam (barvam). ˇCe na primer ˇzelimo izraˇcunati produkt elementa g z s1s2, torej g(s1s2), potem v podmnoˇzico S vzamemo elementa s1 ins2. Produkt doloˇcimo tako, da gremo iz elementa g najprej v smeri s1-povezave in nato ˇse v smeris2-povezave.
22
Poglejmo si tudi, kako razberemo komutativnost grupe iz Cayleyjevega digrafa. Vemo, da smer povezave ustreza mnoˇzenju z desne z ustreznim elementom iz S. ˇCe je torej grupa G komutativna, moramo z razliˇcnim zaporedjem dveh razliˇcnih povezav iz istega vozliˇsˇca vedno priti v isto vozliˇsˇce. Za komutativno grupo namreˇc velja enakost (gs1)s2 = (gs2)s1 za poljuben g ∈G in s1, s2 ∈S. V ta namen si poglejmo naslednjo trditev.
Trditev 3.9. Naj bo Γ = Cay(G;S) Cayleyjev digraf, kjer je hSi = G, in naj bo S = {s1, s2, . . . , sn} za nek n ∈ N. Tedaj je grupa G komutativna natanko tedaj, ko v digrafu Γ velja, da za poljuben 1≤i < j ≤ n iz poljubnega vozliˇsˇca g ∈G pot vzdolˇz si-povezave in nato sj-povezave vedno pripelje do istega vozliˇsˇca kot pot vzdolˇz sj-povezave in nato si-povezave.
Dokaz. Najprej denimo, da za digraf Γ velja predpostavka trditve. Potem (ˇce si ogle- damo ustrezni poti iz e) za poljubna 1≤i < j ≤n velja sisj =sjsi, torej vsi elementi iz S komutirajo med seboj. S tem je G=hSikomutativna grupa.
Obratno, predpostavimo, da je grupa G komutativna. Potem zaradi komutativnosti za poljubna si, sj ∈ S velja enakost sisj = sjsi. Sledi, da nas dve poljubni povezavi za poljubna si in sj vedno pripeljeta iz istega zaˇcetnega vozliˇsˇca v isto konˇcno vozliˇsˇce, saj je (gsi)sj =g(sisj) =g(sjsi) = (gsj)si. V primeru komutativnosti grupe G nam torej poljubni dve barvi data alternirajoˇce 4- cikle, pri ˇcemer gremo dvakrat vzdolˇz usmeritve, dvakrat pa proti usmeritvi. V primeru, da grupa G ni komutativna, nam zaporedje dveh doloˇcenih barv povezav ne da 4-cikla, kar je prikazano na spodnji sliki 3.16.
g
sj si
sj si
gsi
(gsi)sj= (gsj)si
gsj
g si
si sj
sj
gsj gsi
(gsi)sj
(gsj)si
Slika 3.16: Komutativnost in nekomutativnost v Cayleyjevem digrafu.
.
Komentar. Komutativnost je torej razvidna iz vsakega vozliˇsˇca. V primeru, ko je grupa G na primer generirana s tremi elementi, moramo tako za vsak par izmed teh treh ele- mentov preveriti le ali nam generira ustrezne 4-cikle v eali ne, da lahko zagotovo trdimo, ali je grupa G komutativna. V primeru, da nam en izmed parov ne porodi 4-cikla, grupa G ni komutativna.
Zgled: Na sliki 3.17 sta upodobljena dva Cayleyjevega digrafa dveh neizomorfnih grup.
Prvi graf je reda 12, drugi pa reda 24. Zanima nas, ali je katera izmed pripadajoˇcih grup G, komutativna.
23
