Interested Article - Граф Клебша
![](/images/006/660/6660799/1.jpg?rand=89898)
![](https://cdn.wafarin.com/avatars/70e42d83c1a00db8ab791df2b4844af4.jpg)
- 2021-08-20
- 2
В теории графов под графом Клебша понимается один из двух дополняющих друг друга графов, имеющих 16 вершин. Один из них имеет 40 рёбер и является 5- регулярным графом , другой имеет 80 рёбер и является 10-регулярным графом. 80-рёберный вариант — это 5-го порядка. Назван графом Клебша в 1968 году ввиду его связи с конфигурацией прямых поверхности четвёртого порядка, открытой 1868 году немецким математиком Альфредом Клебшем . 40-рёберный вариант – это 5 порядка. Он известен также под именем граф Гринвуда — Глизона после работы Гринвуда и Глизона , в которой они использовали этот граф для вычисления числа Рамсея R (3,3,3) = 17 .
Построение
стягиванием каждой пары противоположных вершин.
5-го порядка (5-регулярный граф Клебша) может быть построен добавлением рёбер между противоположными вершинами графа 4-мерного гиперкуба (В n -мерном гиперкубе пара вершин противоположна, если кратчайшее расстояние между ними содержит n рёбер). Его можно построить также из графа 5-мерного гиперкубаЕщё одно построение, дающее тот же граф, заключается в создании вершины для каждого элемента конечного поля GF (16) и соединении двух вершин ребром, если разность соответствующих элементов поля является кубом .
дополнение 5-регулярного графа. Его можно также построить из вершин 5-мерного гиперкуба путём соединения пар вершин, между которыми расстояние Хэмминга равно точно двум. Это построение образует два подмножества по 16 вершин в каждом, не связанных друг с другом. Оба полученных графа изоморфны 10-регулярному графу Клебша.
5-го порядка (10-регулярный граф Клебша) — этоСвойства
5-регулярный граф Клебша является сильно регулярным графом 5-й степени с параметрами . Его дополнение, 10-регулярный граф Клебша, тоже сильно регулярен .
5-регулярный граф Клебша является гамильтоновым , непланарным и не эйлеровым . Оба графа являются 5- вершинно связными и 5- рёберно связными . Подграф, порождённый десятью вершинами, не являющихся соседями какой-либо вершины в этом графе, изоморфен графу Петерсена .
Рёбра полного графа K 16 можно разделить на три несвязных копии 5-регулярного графа Клебша. Поскольку граф Клебша не содержит треугольников , это показывает, что существует трёхцветное раскрашивание без треугольников рёбер графа K 16 . Таким образом, число Рамсея R (3,3,3), описывающее минимальное число вершин в полном графе при трёхцветном раскрашивании без треугольников, не может быть меньше 17. Гринвуд и Глизон использовали это построение как часть своего доказательства равенства R (3,3,3) = 17 .
5-регулярный граф Клебша является графом Келлера размерности два, и входит в семейство графов, используемых для поиска покрытия Евклидовых пространств большой размерности гиперкубами , не имеющими общих граней.
Алгебраические свойства
Характеристический многочлен 5-регулярного графа Клебша — это . Таким образом, граф Клебша является целым графом – его спектр состоит полностью из целых чисел . Граф Клебша является единственным графом с таким характеристическим полиномом.
5-регулярный граф Клебша является графом Кэли c группой автоморфизмов порядка 1920, изоморфной группе Коксетера . Как в любом графе Кэли, группа автоморфизмов действует транзитивно на его вершины, делая его вершинно-транзитивным . Фактически он является симметричным графом , а потому он рёберно-транзитивен и дистанционно-транзитивен .
Галерея
-
Граф Клебша является гамильтоновым .
-
графа Клебша равно 8.
-
Хроматическое число графа Клебша равно 4.
-
Хроматический класс графа Клебша равен 5.
-
Конструирование графа Клебша из графа гиперкуба .
Примечания
- ↑ . Eric W. Weisstein. From MathWorld — A Wolfram Web Resource. Дата обращения: 13 августа 2009. 7 февраля 2009 года.
- J. J. Seidel, Strongly regular graphs with (−1,1,0) adjacency matrix having eigenvalue 3, Lin. Alg. Appl. 1 (1968) 281—298.
- ↑ R. E. Greenwood, Andrew Gleason. // Canadian Journal of Mathematics. — 1955. — Т. 7 . — С. 1—7 . — doi : .
- A. Clebsch. Ueber die Flächen vierter Ordnung, welche eine Doppelcurve zweiten Grades besitzen // J. für Math. — 1868. — Т. 69 . — С. 142—184 .
- ↑ . Дата обращения: 25 октября 2013. 29 октября 2013 года.
- De Clerck, Frank . Summer School on Finite Geometries 6 (1997). Дата обращения: 25 октября 2013. 15 июня 2011 года.
- Problems in algebraic combinatorics // Т. 2 . — С. 3 . . — 1995. —
- Peter J. Cameron от 29 октября 2013 на Wayback Machine on DesignTheory.org, 2001
- Hugo S. Sun, M. E. Cohen. An easy proof of the Greenwood–Gleason evaluation of the Ramsey number R (3,3,3) // The Fibonacci Quarterly. — 1984. — Т. 22 , вып. 3 . — С. 235—238 .
![](https://cdn.wafarin.com/avatars/70e42d83c1a00db8ab791df2b4844af4.jpg)
- 2021-08-20
- 2