Loading AI tools
Из Википедии, свободной энциклопедии
Граф Шрикханде — граф, найденный С. С. Шрикханде (англ.) в 1959 году[1][2]. Граф сильно регулярен, имеет 16 вершин и 48 рёбер и каждая вершина имеет степень 6. Каждая пара узлов имеет ровно два общих соседа, независимо от того, связана эта пара ребром или нет.
граф Шрикханде | |
---|---|
![]() | |
Назван в честь | С. С. Шрикханде |
Вершин | 16 |
Рёбер | 48 |
Радиус | 2 |
Диаметр | 2 |
Обхват | 3 |
Автоморфизмы | 192 |
Хроматическое число | 4 |
Хроматический индекс | 6 |
Свойства |
Сильно регулярный Гамильтонов Симметричный Эйлеров Целый |
Книжная толщина | 4 |
Число очередей | 3 |
![]() |
Граф Шрикханде можно построить как граф Кэли, в котором множество вершин — это , а две вершины связаны тогда и только тогда, когда разность находится в .
В графе Шрикханде любые две вершины I и J имеют двух различных общих соседей (исключая сами вершины I и J), что выполняется вне зависимости от того, смежны ли I и J, или нет. Другими словами, граф сильно регулярен и его параметрами являются: {16,6,2,2}, то есть . Из этого равенства следует, что граф ассоциирован с симметричными сбалансированными неполными блок-схемами (англ. Balanced Incomplete Block Designs, BIBD). Граф Шрикханде разделяет эти параметры с точно одним другим графом, 4×4 ладейным графом, то есть рёберным графом L(K4,4) полного двудольного графа K4,4. Последний граф является единственным рёберным графом L(Kn, n), для которого параметры сильной регулярности не определяют этот граф единственным образом, и граф делит их с другим графом, а именно графом Шрикханде (который не является ладейным графом)[2][3].
Граф Шрикханде локально шестиуголен. То есть соседи каждой вершины образуют цикл из шести вершин. Как и любой локально цикличный граф, граф Шрикханде является 1-мерным остовом[англ.] триангуляции Уитни некоторой поверхности. В случае графа Шрикханде эта поверхность является тором, в котором каждая вершина окружена шестью треугольниками[4] Таким образом, граф Шрикханде — это тороидальный граф. Вложение образует регулярное отображение в тор с 32 треугольными гранями. Остов дуального графа этого отображения (как вложенного в тор) — граф Дика, кубический симметричный граф.
Граф Шрикханде не является дистанционно-транзитивным. Это самый маленький дистанционно-регулярный граф, не являющийся дистанционно-транзитивным[5].
Группа автоморфизмов графа Шрикханде имеет порядок 192. Она действует транзитивно на вершины, на рёбра и дуги графа. Поэтому граф Шрикханде является симметричным графом.
Характеристический многочлен графа Шрикханде равен . Таким образом, граф Шрикханде является целым графом — его спектр состоит всецело из целых чисел.
Граф имеет книжную толщину 4 и число очередей 3[6].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.