Cayley-gráf – Wikipédia

Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye.

Gráfcsaládok automorfizmusukkal meghatározva
távolságtranzitív	${\displaystyle {\boldsymbol {\rightarrow }}}$	távolságreguláris	${\displaystyle {\boldsymbol {\leftarrow }}}$	erősen reguláris
${\displaystyle {\boldsymbol {\downarrow }}}$
szimmetrikus	${\displaystyle {\boldsymbol {\leftarrow }}}$	t-tranzitív, t ≥ 2		ferdeszimmetrikus
${\displaystyle {\boldsymbol {\downarrow }}}$
(ha összefüggő) csúcs- és éltranzitív	${\displaystyle {\boldsymbol {\rightarrow }}}$	éltranzitív és reguláris	${\displaystyle {\boldsymbol {\rightarrow }}}$	éltranzitív
${\displaystyle {\boldsymbol {\downarrow }}}$		${\displaystyle {\boldsymbol {\downarrow }}}$		${\displaystyle {\boldsymbol {\downarrow }}}$
csúcstranzitív	${\displaystyle {\boldsymbol {\rightarrow }}}$	reguláris	${\displaystyle {\boldsymbol {\rightarrow }}}$	(ha páros) bireguláris
${\displaystyle {\boldsymbol {\uparrow }}}$
Cayley-gráf	${\displaystyle {\boldsymbol {\leftarrow }}}$	zérószimmetrikus		aszimmetrikus

A matematikában azon gráfokat nevezik Cayley-gráfoknak, amelyek egy csoport struktúráját reprezentálják. A Cayley-gráfok központi szerepet játszanak a kombinatorikában és a geometriai csoportelméletben. Arthur Cayley brit matematikus nevét őrzi az elnevezés.

Adott ${\displaystyle G}$ csoport és ${\displaystyle S}$ generátorhalmaz esetében a Cayley-gráf a következő színezett, irányított gráf:

1. Minden g ∈ G elem megfelel egy v_g ∈ V csúcsnak a gráfban.
2. Minden s ∈ S elem megfelel egy c_s színnek.
3. Minden g ∈ G és s ∈ S esetében a v_g és a v_gs csúcsok között létezik egy c_s színű él.

A geometriai csoportelméletben általában felteszik, hogy az S generátorhalmaz véges és szimmetrikus (azaz S = S^-1) és nem tartalmazza a csoport neutrális elemét. Ebben az esetben G egy hurokélektől mentes irányítatlan gráf.

• Egy adott csoporthoz tartozó Cayley-gráf nem egyértelmű, mert egy adott csoport generátorhalmaza sem egyértelmű.
• Ha a generátorhalmaz n elemű, akkor minden csúcsból pontosan n él indul ki és pontosan n él érkezik minden csúcsba. Ha a generátorhalmaz szimmetrikus, azaz minden elemének inverzét is tartalmazza, akkor reguláris gráf keletkezik.
• Ha a generátorhalmaz tartalmazza az egységelemet, akkor minden csúcsra illeszkedik hurokél, ezért gyakran már a definícióban megkövetelik, hogy a generátorhalmaz ne tartalmazza az egységelemet.
• A Cayley-gráf körei megfelelnek a csoport elemei közötti relációknak.
• Ha ${\displaystyle f:G'\to G}$ szürjektív homomorfizmus, ami injektív G’ S’ generátorhalmazán, akkor f a

${\displaystyle {\bar {f}}:\Gamma (G',S')\to \Gamma (G,S),\quad }$ ahol S = f(S’)

gráf fedését indukálja.

• Ha a G csoportot n generátor generálja, amik egyike sem önmaga inverze, és az S generátorhalmaz szimmetrikus, akkor a Γ(G,S) Cayley-gráf lefedhető az S generátorhalmazhoz tartozó szabad csoporthoz tartozó 2n fokú végtelen fával, a 2n fokú Bethe-ráccsal.

• Ha az S részhalmaz nem generátorrendszer, akkor is elkészíthető a Γ(G,S) gráf, de ez nem lesz összefüggő, és nem tekintik Cayley-gráfnak. Ekkor Γ(G,S) minden összefüggőségi komponense megfelel az S által generált részcsoport egy mellékosztályának.

• Ha ${\displaystyle G=(\mathbb {Z} ,+)}$ az egész számok csoportja az összeadás műveletre nézve a generátorhalmaz pedig ${\displaystyle S=\{1,-1\}}$, akkor a Cayley-gráf egy végtelen lánc.
• Hasonlóan ha ${\displaystyle G=(\mathbb {Z} _{n},+)}$ az n elemű véges, ciklikus csoport, a generátorhalmaz pedig a csoport standard generátoreleméből és annak inverzéből áll, akkor a Cayley-gráf pontosan a ${\displaystyle C_{n}}$ körgráf.
• Két csoport direkt szorzatának Cayley-gráfja azonos a csoportok Cayley-gráfjainak direkt szorzatával. Ezért a ${\displaystyle \mathbb {Z} ^{2}}$ Abel-csoport a (±1, ±1) négyelemű generátorhalmazzal a végtelen síkbeli rácsgráfot generálja, a Z_n × Z_m direkt szorzat hasonló generátorhalmazzal a ${\displaystyle C_{n}\times C_{m}}$ gráfot (az ${\displaystyle n\times m}$ tórikus rácsgráfot) generálja.

• A D₄ diédercsoport Cayley-gráfja az a and b generátorokkal jobboldalt látható. A piros nyilak mutatják a balról való szorzást az a elemmel. Mivel b önmaga inverze, a kék élek, amelyek a balról b-val szorzást jelölik, irányítatlanok. A gráf vegyes: 8 csúcsa van, 8 irányított éle, és 4 irányítatlan éle. A D₄ Cayley-táblázata származtatható a következő csoportprezentációból

${\displaystyle \langle a,b|a^{4}=b^{2}=e,ab=ba^{3}\rangle .}$

• Az a, b elemekkel generált szabad csoport az S = {a, b, a^‒1, b^‒1} generátorhalmazzal a cikk tetején szereplő Cayley-gráfot implikálja. A neutrális elemet az e betű jelzi. Egy élen jobbra lépés a-val való szorzást jelent, egy felfelé lépés a b-vel való szorzást. Ez a körmentes Cayley-gráf kulcsfontosságú a Banach–Tarski-paradoxon bizonyításában.

Mikor lehet egy adott gráf egy csoport Cayley-gráfja?

Hasson a G csoport önmagán balról szorzással! Ez a hatás hatás lesz a Cayley-gráfon is. Konkrétan, a h ∈ G elem a g ∈ V(Γ) csúcsot a hg ∈ V(Γ) csúcsba küldi. Hasonlóan, a (g,gs) él a (hg,hgs) élbe megy át. A balról szorzás (egyszeresen) tranzitív hatás; ennek megfelelően a Cayley-gráf csúcstranzitív.

Eszerint:

A Γ gráf akkor és csak akkor Cayley-gráfja a G csoportnak, ha Γ automorfizmuscsoportja tartalmazza G egy (egyszeresen) tranzitív hatását. Azaz, ha van homomorfizmus a G csoportból Γ automorfizmuscsoportjába.

A színezés rekonstrukciójához válasszunk egy v₁ ∈ V(Γ) csúcsot, és színezzük meg c₁-gyel! Ez meghatározza Γ minden további v csúcsának színét, mivel egyértelműen van egy g elem, ami v₁-et v-be viszi. Az S generátorhalmaz a v₁ csúcs szomszédainak színéhez tartozó elemekből fog állni. S akkor és csak akkor lesz véges, ha Γ lokálisan véges, vagyis minden csúcsnak véges sok szomszédja van.

Megfordítva azonban nem igaz, hogy minden csúcstranzitív gráf egy G csoport egy Cayley-gráfja, és a fenti tétel nem válaszolja meg a Cayley-gráfok struktúrájának összes kérdését. Például még nincs bizonyítva Lovász László sejtése, hogy minden Cayley-gráf tartalmaz Hamilton-kört.

A Cayley-gráf szomszédsági mátrixának vizsgálatával, különösen a spektrális gráfelmélet eredményeit felhasználva, következtetni lehet a csoport szerkezetére.

A geometriai csoportelméletben a végtelen csoportok jellemzésére alapvető fontosságú a Cayley-gráf durva geometriája, vagy annak kváziizometriai ekvivalenciaosztálya. Végesen generált csoportokra ez független a generátorrendszer választásától, tehát a csoport tulajdonságának tekinthető. Ez véges csoportok esetén érdektelen, ugyanis ezek kváziizometrikusak az egy pontból álló térrel, hiszen a generátorcsoport választható az egész csoportnak.

A Cayley-gráf egy csoport metrikus képe a szómetrikával. Ezt a generátorok egyértelműen meghatározzák.

A Cayley-komplexus cellakomplexus, aminek 1-váza a Cayley-gráf, de 2-cellákkal is el van látva. A 2-cellákhoz relátorokra is szükség van úgy, hogy az S generátorhalmaz és a relátorok R halmaza együtt a csoport prezentációját adja.

Például a Z² csoport Cayley-komplexusa a ${\displaystyle \langle \alpha ,\beta |\alpha \beta \alpha ^{-1}\beta ^{-1}=e\rangle }$ prezentációval a sík egységnégyzetekkel való parkettázása, aminek 1-váza a Z² csoport Cayley-gráfja.

A Schreier-gráf a Cayley-gráf általánosítása. Egy G csoport Schreier-gráfjának megadásához a generátorokon kívül egy részcsoportot is rögzíteni kell; jelölje ezt a részcsoportot H! Ekkor a Σ(G,H,S) Schreier-gráf csúcsai megfelelnek a H-val vett jobb mellékosztályoknak, élei a Cayley-gráf éleinek. Maga a Cayley-gráf az a Schreier-gráf, amit a H=1 triviális részcsoport ad.

• Csúcstranzitív gráf
• Generátorhalmaz
• Lovász-sejtés

• Ez a szócikk részben vagy egészben a Cayley graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.