Граф Келі вільної групи на двох генераторах a та b.

Граф Келі — граф, який будується для групи із скінченною системою генеруючих елементів. Названий на честь англійського математика Артура Келі.

ВизначенняРедагувати

Види графів за їхніми автоморфізмами
відстанево-транзитивний[en] відстанево-регулярний[en] сильно регулярний[en]
 
симетричний (дуго-транзитивний) t-транзитивний, t ≥ 2
 (якщо зв'язний)
вершинно- та реберно-транзитивний[en] реберно-транзитивний і регулярний реберно-транзитивний
  
вершинно-транзитивний регулярний
 
граф Келікососиметричний[en]асиметричний

Нехай   — деяка група і   — система її породжуючих (генеруючих) елементів. Визначимо  

Тоді граф Келі для даної групи Γ = Γ(G, T) будується таким чином:

  • Кожному елементу   відповідає одна вершина графа.
  • Кожному елементу   відповідає певний колір ct
  • Для будь-яких   та   вершини g і gt з'єднуються орієнтованим ребром кольору ct.

ПрикладиРедагувати

  • Графом Келі для нескінченної циклічної групи Z є нескінченний ланцюг.
  • Графом Келі для скінченної циклічної групи Zn є цикл з n вершинами.
  • Графом Келі для прямого добутку двох груп є прямий добуток відповідних графів Келі.


Див. такожРедагувати

ДжерелаРедагувати

  • Громов М. Л. Гиперболические группы. 2002. — С.160