Граф Келі

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

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

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

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

Нехай G — деяка група і S — система її породжуючих(генеруючих) елементів. Визначимо T = S\cup S^{-1}.

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

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

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

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


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

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

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