Граф Келі

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

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

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

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

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

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

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

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

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


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

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

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