„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
fordítás a en:Cayley graph szócikkből |
a belső hiv. + pontosítások |
||
1. sor:
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
Adott <math>G</math> csoport és <math>S</math> [[generátorhalmaz]] esetében a Cayley-gráf konstrukciója a következő:
6. sor:
# Pontosan akkor létezik <math>c_i</math> színű irányított él a <math>v_1</math> csúcsból a <math>v_2</math> csúcsba, ha <math>g_2 = g_1 * s_i</math>.
==
* 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.
14. sor:
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.
Csoportok direkt szorzatának sztenderd Cayley-gráfja megfelel a csoportok Cayley-gráfjainak direkt szorzata. Például a <math>C_n</math> [[körgráf]] a <math>Z_n</math> ciklikus csoport Cayley-gráfja, így a <math>C_n \times C_m</math> gráf (az <math>n \times m</math> tórikus rácsgráf) a <math>Z_n \times Z_m</math> csoport Cayley-gráfja.
== Lásd még ==
| |||