„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
Karakterizáció: hatás |
→Karakterizáció: a színezés és a generátorhalmaz rekonstrukciója |
||
37. sor:
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 (csoportelmélet)|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 [[gráfszínezés|színezés]] rekonstrukciójához válasszunk egy ''v''<sub>1</sub> ∈ V(''Γ'') csúcsot, és színezzük meg ''c''<sub>1</sub>-gyel! Ez meghatározza ''Γ'' minden további ''v'' csúcsának színét, mivel egyértelműen van egy ''g'' elem, ami ''v''<sub>1</sub>-et ''v''-be viszi. Az ''S'' generátorhalmaz a ''v''<sub>1</sub> 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ó [[Lovász-sejtés|sejtése]], hogy minden Cayley-gráf tartalmaz Hamilton-kört.
== 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.
| |||