Граф Келі

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Граф Келі вільної групи на двох генераторах a та b.

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

Визначення[ред.ред. код]

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

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

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

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

Приклади[ред.ред. код]

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


Див. також[ред.ред. код]

Джерела[ред.ред. код]

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