Loading AI tools
двудольный неориентированный граф с 54 вершинами и 81 рёбрами Из Википедии, свободной энциклопедии
Граф Грея — двудольный неориентированный граф с 54 вершинами и 81 рёбрами. Граф является кубическим — любая вершина принадлежит ровно трём рёбрам. Граф был открыт Греем[англ.] в 1932 году (без публикации), затем открыт независимо Баувером (Bouwer) в 1968 году в ответ на вопрос, поставленный Фолкманом[англ.] в 1967 году. Граф Грея примечателен как исторически первый пример кубического графа, имеющего алгебраическое свойство рёберной, но не вершинной транзитивности.
Граф Грея | |
---|---|
Назван в честь | Марион Камерон Грей[англ.] |
Вершин | 54 |
Рёбер | 81 |
Радиус | 6 |
Диаметр | 6 |
Обхват | 8 |
Автоморфизмы | 1296 |
Хроматическое число | 2 |
Хроматический индекс | 3 |
Свойства |
гамильтонов |
Медиафайлы на Викискладе |
Хроматическое число графа Грея равно 2, хроматический индекс — 3, радиус и диаметр равны 6. Он также является вершинно 3-связным и рёберно 3-связным непланарным графом.
Граф Грея можно построить[1] из 27 точек решётки размером 3×3×3 и 27 прямых, параллельных осям и проходящих через эти точки. Этот набор точек и прямых образует проективную конфигурацию — через каждую точку проходят ровно три прямых и на каждой прямой лежат ровно три точки. Граф Грея является графом Леви этой конфигурации. Граф имеет вершину для каждой точки и для каждой прямой этой конфигурации и ребро для каждой пары точка-прямая, если точка лежит на прямой. Эта конструкция может быть обобщена (Баувер, 1972) на любую размерность , давая -валентные графы Леви с алгебраическими свойствами, похожими на свойства графа Грея.
Также может быть построен как граф Леви для рёбер и треугольных граней некоторого локально тороидального абстрактного правильного 4-многогранника[2].
Марушич и Писански[3] дали некоторые альтернативные методы построения графа Грея. Как и у любой другой двудольный граф, граф Грея не содержит циклов нечётной длины, а также не содержит циклов с четырьмя или шестью вершинами, так что обхват графа Грея равен 8. Самая простая ориентированная поверхность, в которую граф Грея можно вложить, имеет род 7[4].
Граф Грея являетсяs гамильтоновым и может быть построен из LCF-нотации:
Группа автоморфизмов графа Грея — это группа порядка 1296. Она действует транзитивно на рёбра графа, но не на его вершины — имеются автоморфизмы, переводящие любое ребро в любое другое ребро, но нет автоморфизмов, которые переводят любую вершину в любую другую. Вершины, соответствующие конфигурации, лежащей в основе графа, могут быть симметричны только вершинам, соответствующим точкам конфигурации, а вершины, соответствующие прямым, симметричны только вершинам, соответствующим прямым. Таким образом, граф Грея является полусимметричной группой[англ.] и является наименьшим возможным кубическим полусимметричным графом.
Характеристический многочлен графа Грея равен:
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.