Граф M22 — Википедия

Граф M₂₂

Граф M₂₂, Граф Меснера ^[1]^[2]^[3]
Граф Матьё M22^[англ.], Граф Меснера
Вершин	77
Рёбер	616

Граф M₂₂, называемый также графом Меснера^[1]^[2]^[3], это единственный сильно регулярный граф с параметрами (77, 16, 0, 4)^[4]. Граф строится из системы Штейнера (3, 6, 22), принимая его 77 блоков в качестве вершин и соединяя две вершины тогда и только тогда, когда они не имеют общих элементов. Граф можно получить также удалением вершины и её соседей из графа Хигмана — Симса^[5]^[6].

Граф является одним из семи известных строго регулярных графов без треугольников^[7]. Его спектр равен $(-6)^{21}2^{55}16^{1}$ ^[5], а его группой автоморфизмов служит группа Матьё M22^[англ.]^[4].

См. также

Литература

↑ ¹ ² "Mesner graph with parameters (77,16,0,4). The automorphism group is of order 887040 and is isomorphic to the stabilizer of a point in the automorphism group of NL2(10)" (неопр.). Дата обращения: 30 января 2019. Архивировано 1 мая 2018 года.
↑ ¹ ² Slide 5 list of triangle-free SRGs says "Mesner graph" (неопр.). Дата обращения: 30 января 2019. Архивировано 15 ноября 2018 года.
↑ ¹ ² Section 3.2.6 Mesner graph (неопр.). Дата обращения: 30 января 2019. Архивировано 15 ноября 2018 года.
↑ ¹ ² Andries E. Brouwer Technische Universiteit Eindhoven M₂₂ Graph Архивная копия от 18 февраля 2019 на Wayback Machine Accessed=29 May 2018.
↑ ¹ ² Weisstein, Eric W. “M22 Graph.” MathWorld, http://mathworld.wolfram.com/M22Graph.html Архивная копия от 18 февраля 2019 на Wayback Machine. Accessed 29 May 2018.
↑ Vis, Timothy. University of Colorado Denver, The Higman–Sims Graph Архивная копия от 24 июля 2010 на Wayback Machine. Accessed 29 May 2018.
↑ Weisstein Eric W. «Strongly Regular Graph» From Wolfram MathWorld, mathworld.wolfram.com/StronglyRegularGraph.html

Ссылки

M₂₂ graph at MathWorld

Похожие исследовательские статьи

<span class="mw-page-title-main">Регулярный граф</span> граф, степени всех вершин которого равны

Регуля́рный (одноро́дный) граф — граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Степень регулярности является инвариантом графа и обозначается $\text{[math]}$ . Для нерегулярных графов $\text{[math]}$ не определено. Регулярные графы представляют особую сложность для многих алгоритмов.

В теории графов под графом Клебша понимается один из двух дополняющих друг друга графов, имеющих 16 вершин. Один из них имеет 40 рёбер и является 5-регулярным графом, другой имеет 80 рёбер и является 10-регулярным графом. 80-рёберный вариант — это половинный граф куба 5-го порядка. Назван графом Клебша в 1968 году Зайделем ввиду его связи с конфигурацией прямых поверхности четвёртого порядка, открытой 1868 году немецким математиком Альфредом Клебшем. 40-рёберный вариант – это складной граф куба 5 порядка. Он известен также под именем граф Гринвуда — Глизона после работы Гринвуда и Глизона, в которой они использовали этот граф для вычисления числа Рамсея R (3,3,3) = 17 .

В теории графов двусвязный граф — это связный и неделимый граф, в том смысле, что удаление любой вершины не приведёт к потере связности. Теорема Уитни утверждает, в частности, что граф двусвязен тогда и только тогда, когда между любыми двумя его вершинами есть минимум два непересекающихся пути. Таким образом, двусвязный граф не имеет шарниров.

В теории графов графом МакГи, или (3-7)-клеткой, называется 3-регулярный граф с 24 вершинами и 36 рёбрами.

В теории графов спичечным графом называется граф, который можно нарисовать на плоскости таким образом, что все его рёбра представляют собой отрезки прямой длиной единица и рёбра не пересекаются. Таким образом, этот граф имеет вложение в плоскость одновременно в виде графа единичных расстояний и планарного графа. Говоря неформально, спичечный граф можно выложить непересекающимися на плоской поверхности спичками, откуда и название.

<span class="mw-page-title-main">Сильно регулярный граф</span> регулярный граф с v вершинами и степенью k, у которого число общих соседей зависит только от смежности пары вершин

Сильно регулярный граф — вариация понятия регулярный граф.

Граф Коксетера — 3-регулярный граф с 28 вершинами и 42 рёбрам Все кубические дистанционно-регулярные графы известны, граф Коксетера — один из 13-ти таких графов.

Полиэдральный граф — неориентированный граф, образованный из вершин и рёбер выпуклого многогранника, или, в контексте теории графов — вершинно 3-связный планарный граф.

<span class="mw-page-title-main">Многоугольник Петри</span>

Многоугольник Петри для правильного многогранника в размерности $\text{[math]}$ — это пространственный многоугольник, такой что любые $\text{[math]}$ последовательных ребра принадлежат одной $\text{[math]}$ -мерной грани. В частности,

Многоугольник Петри правильного многоугольника — это сам правильный многоугольник.
Многоугольник Петри трёхмерного правильного многогранника — это пространственный многоугольник, такой, что любые две последовательные стороны принадлежат одной из граней.

<span class="mw-page-title-main">Ребро (геометрия)</span> отрезок, соединяющий две вершины политопа

Ребро в геометрии — отрезок, соединяющий две вершины многоугольника или многогранника. В многоугольниках ребро является отрезком, лежащим на границе и чаще называется стороной многоугольника. В трёхмерных многогранниках и в многогранниках большей размерности ребро — это отрезок, общий для двух граней. Отрезок, соединяющий две вершины и проходящий через внутренние или внешние точки, ребром не является и называется диагональю.

Ранг неориентированного графа имеет два не связанных друг с другом определения. Пусть n равно числу вершин графа.

В терминах теории матриц ранг r неориентированного графа определяется как ранг его матрицы смежности.

Аналогично, дефект графа определяется как дефект ядра его матрицы смежности, что равно n − r.

В терминах теории матроидов графов ранг неориентированного графа определяется как число n − c, где c — число связных компонент графа. Эквивалентно, ранг графа — это ранг ориентированной матрицы инцидентности, ассоциированной с графом.

Аналогично, дефект графа — это дефект ядра ориентированной матрицы инцидентности, который задаётся формулой m − n + c, где n и c определены выше, а m — число рёбер графа. Дефект равен первому числу Бетти графа. Сумма ранга и дефекта даёт число рёбер.

Граф Хигмана — Симса — это 22-регулярный неориентированный граф со 100 вершинами и 1100 рёбрами. Граф является уникальным сильно регулярным графом srg(100,22,0,6), т.е. никакая соседняя пара вершин не имеет общих соседей и любая несоседняя пара вершин имеет шесть общих соседей. Граф был впервые построен Меснером и был переоткрыт в 1968 Дональдом Дж. Хигманом и Чарльзом Симсом как путь определения группы Хигмана — Симса и эта группа является подгруппой с индексом два в группе автоморфизмов графа Хигмана — Симса.

Графы Чана — набор из трёх 12-регулярных неориентированных графов, каждый с 28 вершинами и 168 рёбрами. Все они сильно регулярны и имеют те же параметры и спектр, что и рёберный граф L(K₈) полного графа K₈. Графы Чана названы именем Ли-Чиена Чана, который доказал, что, за исключением этих трёх графов, любой рёберный граф полного графа единственным образом определяется его параметрами сильно регулярного графа.

Граф Хоффмана является 4-регулярным графом с 16 вершинами и 32 рёбрами, который открыл Алан Хоффман и опубликовал в 1963. Граф коспектрален графу гиперкуба Q₄.

Граф Робертсона или (4,5)-клетка — это 4-регулярный неориентированный граф с 19 вершинами и 38 рёбрами, названный именем Нейла Робертсона.

Граф Робертсона — Вегнера — 5-регулярный неориентированный граф с 30 вершинами и 75 рёбрами, названный именами Нейла Робертсона и Дж. Вегнера.

Граф Гевирца — сильно регулярный граф с 56 вершинами и валентностью 10. Граф назван именем математика Аллана Гевирца, описавшего граф в своей диссертации.

Целый граф — граф, спектр матрицы смежности которого состоит полностью из целых чисел. Другими словами, граф является целым графом, при условии, что все корни характеристического многочлена его матрицы смежности являются целыми числами. Понятие ввели в 1974 году Харари и Швенк.

Граф Брауэра — Хемерса — 20-регулярный неориентированный граф с 81 вершиной и 810 рёбрами. Это сильно регулярный, дистанционно-транзитивный граф и граф Рамануджана. Хотя его построение является математическим фольклором, он был назван именами Андреаса Брауэра и Уиллема Х. Хемерса, которые доказали его единственность в качестве строго регулярного графа.

Граф Берлекэмпа — ван Линта — Зейделя — это локально линейный сильно регулярный граф с параметрами (243,22,1,2), это означает, что граф имеет 243 вершины, 22 ребра на вершину, в точности одну общую вершину для каждой пары смежных вершин и в точности две общие вершины для любой пары несмежных. Граф построили Элвин Берлекэмп, Дж. Г. ван Линт и Йохан Якоб Зайдель как граф смежности троичных кодов Голея.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.