„Cayley-gráf” változatai közötti eltérés
| [nem ellenőrzött változat] | [nem ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a Bot: következő hozzáadása: zh:凱萊圖 |
Kieg. {{fordítás|en|Cayley graph|242782845}} forrásból: Példákat és két képet adtam hozzá. Definíciót fogalmaztam. |
||
1. sor:
[[Image:Cayley graph of F2.svg|right|thumb|Az ''a'' and ''b'' elemekkel generált szabad csoport egy Cayley-gráfja]]
A matematikában azon gráfokat nevezik '''Cayley-gráf'''oknak, amelyek egy [[csoport]] struktúráját reprezentálják. A Cayley-gráfok központi szerepet játszanak a [[kombinatorika|kombinatorikában]] és a [[geometriai csoportelmélet]]ben. [[Arthur Cayley]] brit matematikus nevét őrzi az elnevezés.
Adott <math>G</math> csoport és <math>S</math> [[generátorhalmaz]] esetében a Cayley-gráf
# Minden
# Minden
# Minden ''g'' ∈ ''G'' és ''s'' ∈ ''S'' esetében a v<sub>g</sub> és a v<sub>gs</sub> csúcsok között létezik egy c<sub>s</sub> színű él.
A geometriai csoportelméletben általában felteszik, hogy az ''S'' generátorhalmaz véges és szimmetrikus (azaz ''S'' = ''S<sup>-1</sup>'') és nem tartalmazza a csoport [[neutrális elem]]ét. Ebben az esetben ''G'' egy [[hurokél]]ektől mentes irányítatlan gráf.
== Elemi tulajdonságok ==
10 ⟶ 14 sor:
* 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 tartalmazza az egységelemet, akkor minden csúcs rendelkezik egy hurokéllel, ezért gyakran már a definícióban megkövetelik, hogy a generátorhalmaz ne tartalmazza az egységelemet.
== Példák ==
* Ha <math>G=(\mathbb{Z}, +)</math> az egész számok csoportja az összeadás műveletre nézve a generátorhalmaz pedig <math>S = \{ 1, -1 \}</math>, akkor a Cayley-gráf egy végtelen lánc.
* Hasonlóan ha <math>G=(\mathbb{Z}_n, +)</math> 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 <math>C_n</math> [[körgráf]].
* Két csoport direkt szorzatának Cayley-gráfja azonos a csoportok Cayley-gráfjainak direkt szorzatával. Ezért a <math>\mathbb{Z}^2</math> [[Abel-csoport]] a (±1, ±1) négyelemű generátorhalmazzal a végtelen síkbeli rácsgráfot generálja, a '''Z'''<sub>''n''</sub> × '''Z'''<sub>''m''</sub> direkt szorzat hasonló generátorhalmazzal a <math>C_n \times C_m</math> gráfot (az <math>n \times m</math> [[tórusz|tórikus]] rácsgráfot) generálja.
[[Image:Cayley_Graph_of_Dihedral_Group_D4.svg|200px|right|thumb|A ''D''<sub>4</sub> diéder csoport Cayley-gráfja az α and β generátorokkal]]
* A ''D''<sub>4</sub> [[diéder csoport]] Cayley-gráfja az α and β generátorokkal jobb oldalt látható. A piros nyilak mutatják a balról való szorzást az α elemmel. Mivel β önmaga inverze, a kék élek, amelyek a balról β-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''<sub>4</sub> [[Cayley-táblázat]]a származtatható a következő [[csoportprezentációból]]
: <math> \langle \alpha, \beta | \alpha^4 = \beta^2 = e, \alpha \beta = \beta \alpha^3 \rangle. </math>
* 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.
== 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.
== Lásd még ==
# [[Csúcstranzitív gráf]]
# [[Generátorhalmaz]]
# [[Lovász-sejtés]]
# [[Generátorhalmaz]]
== Jegyzetek ==
* {{fordítás|en|Cayley graph|242782845}}
{{csonk-mat}}
| |||