Cayley-gráf
matematikai fogalom a gráfelméletben / From Wikipedia, the free encyclopedia
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.
Gyors adatok
Bezárás
Adott csoport és generátorhalmaz esetében a Cayley-gráf a következő színezett, irányított gráf:
- Minden g ∈ G elem megfelel egy vg ∈ V csúcsnak a gráfban.
- Minden s ∈ S elem megfelel egy cs színnek.
- Minden g ∈ G és s ∈ S esetében a vg és a vgs csúcsok között létezik egy cs 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.