„Cayley-gráf” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a →Elemi tulajdonságok: magyarítás |
Karakterizáció: hatás |
||
34. sor:
* Az ''a'', ''b'' elemekkel generált [[szabad csoport]] az ''S'' = {''a'', ''b'', ''a''<sup>‒1</sup>, ''b''<sup>‒1</sup>} 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ör (gráfelmélet)|körmentes]] Cayley-gráf kulcsfontosságú a [[Banach–Tarski-paradoxon]] bizonyításában.
==Karakterizáció==
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.''
== Csoportelméleti vonatkozások ==
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.
| |||