Cayleys graf

I matematikk er en Cayley-graf (oppkalt etter Arthur Cayley ) en graf som koder strukturen til en gruppe . Det er et viktig verktøy for studiet av kombinatorikk og geometrien til grupper .

Definisjon

Familier av grafer definert av deres automorfismer
avstandstransitiv	→	vanlig distanse	←	sterkt vanlig
↓
symmetrisk (bue-transitiv)	←	t -transitiv, ( t  ≥ 2)		symmetrisk venstre  (i)
↓
(hvis tilkoblet) vertex-transitive og edge-transitive	→	vanlig og kantovergang	→	kantovergang
↓		↓		↓
topp-transitive	→	regelmessig	→	(hvis tosidig) dobbeltregulert
↑
Cayley-graf	←	null-symmetrisk		asymmetrisk

Gitt en gruppe og en genererende del av denne gruppen, er grafen til Cayley Cay (G, S) konstruert slik: (G,∗){\ displaystyle (G, *)} S{\ displaystyle S}

• Til hvert element i forbinder vi et toppunkt .g{\ displaystyle g}G{\ displaystyle G}vg{\ displaystyle v_ {g}}
• Hvert element i , vi forbinder en farge .s{\ displaystyle s}S{\ displaystyle S}vs.s{\ displaystyle c_ {s}}
• For alle og , tegner vi en orientert farget kant fra toppen til toppen .g∈G{\ displaystyle g \ in G}s∈S{\ displaystyle s \ in S}vs.s{\ displaystyle c_ {s}}vg{\ displaystyle v_ {g}}vg∗s{\ displaystyle v_ {g * s}}

Vi kan også knytte hver generator til en retning i stedet for en farge, men det er noen ganger umulig å representere grafen i planet. I noen sammenhenger bruker vi venstre hånd i stedet for høyre multiplikasjon (kantene går fra til ). vg{\ displaystyle v_ {g}}vs∗g{\ displaystyle v_ {s * g}}

Eiendommer

• Ettersom det genererende settet til en gruppe ikke er unikt, er strukturen til Cayley-grafene til en gitt gruppe ikke unik.
• Hvis generatorsettet har elementer, har hvert toppunkt innkommende kanter og utgående kanter.ikke{\ displaystyle n}ikke{\ displaystyle n}ikke{\ displaystyle n}
• Syklusene i grafen tilsvarer forholdene som er bekreftet av generatorene.
• Hvis og begge er i generatorsettet, erstatter vi ofte hvert par orienterte kanter som tilsvarer og med en enkelt uorientert kant.s{\ displaystyle s}s-1{\ displaystyle s ^ {- 1}}s{\ displaystyle s}s-1{\ displaystyle s ^ {- 1}}

Eksempler

Cayley-grafen til den gratis gruppen med to generatorer vises øverst til høyre på siden. ( er det nøytrale elementet). Ett trinn mot høyre tilsvarer en multiplikasjon med , til venstre med , opp ved og ned. Siden det ikke er noen relasjoner i den frie gruppen (per definisjon), er Cayley-grafen dens syklisk. e{\ displaystyle e}på{\ displaystyle a}på-1{\ displaystyle a ^ {- 1}}b{\ displaystyle b}b-1{\ displaystyle b ^ {- 1}}

Til høyre er en tegning av Cayley-grafen til en ordre 18-gruppe med presentasjon . Den genereres av tre elementer av rekkefølge 2, som derfor er representert av ikke-orienterte kanter i tre forskjellige farger; hvert toppunkt er knyttet til en kant av hver farge. Ved å følge kantene kan vi bekrefte at de andre forholdene er tilfredsstilt. Hvis vi for eksempel velger generatorene x , y og z henholdsvis fargene rød, grønn og blå (men det spiller ingen rolle, er presentasjonen perfekt symmetrisk), ser vi at med utgangspunkt i ethvert toppunkt, sekvens rød- grønn-rød-grønn-rød-grønn setter oss tilbake til utgangspunktet vårt (da ( xy ) 3 = 1), og også rød-grønn-blå-rød-grønn-blå sekvens (deretter ( xyz ) 2 = 1). <x,y,z|x2=y2=z2=(xy)3=(xz)3=(yz)3=(xyz)2=1>{\ displaystyle <x, y, z | x ^ {2} = y ^ {2} = z ^ {2} = (xy) ^ {3} = (xz) ^ {3} = (yz) ^ {3 } = (xyz) ^ {2} = 1>}

Se også

Relatert artikkel

Beregning av ord

Ekstern lenke

(no) Eric W. Weisstein , “  Cayley Graph  ” , på MathWorld

Bibliografi

• (no) Arthur Cayley , “  Om teorien om grupper  ” , Proc. London matematikk. Soc. , n o  9,1878, s.  126-133
• (en) HSM Coxeter og WOJ Moser  (de) , generatorer og relasjoner for diskrete grupper , Springer ,1972( Rep.  2013), 3- e  ed. ( 1 st  ed. 1957), 164  s. ( ISBN  978-3-662-21946-1 , online presentasjon ) , “3. Grafer, kart og Cayley-diagrammer” , s.  18-32.

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">