График дезарга - Desargues graph

График дезарга
Названный в честь	Жерар Дезарг
Вершины	20
Края	30
Радиус	5
Диаметр	5
Обхват	6
Автоморфизмы	240 (S5× Z/2Z)
Хроматическое число	2
Хроматический индекс	3
Род	2
Толщина книги	3
Номер очереди	2
Свойства	Кубический Дистанционно-регулярный Гамильтониан Двудольный Симметричный
Таблица графиков и параметров

в математический поле теория графов, то График дезарга это дистанционно-переходный кубический граф с 20 вершинами и 30 ребрами.^[1] Он назван в честь Жирар Дезарг, возникает из нескольких различных комбинаторных конструкций, имеет высокий уровень симметрии, является единственным известным непланарный кубический частичный куб, и был применен в химических базах данных.

Название «граф Дезарга» также использовалось для обозначения десятивершинного графа, дополнения Граф Петерсена, который также может быть сформирован как двудольная половина 20-вершинного графа Дезарга.^[2]

Конструкции

Есть несколько разных способов построения графа Дезарга:

• Это обобщенный граф Петерсена г(10, 3). Чтобы сформировать граф Дезарга таким образом, соедините десять вершин в правильный десятиугольник, а остальные десять вершин соединить в десятиугольную звезду, которая соединяет пары вершин на расстоянии три во втором десятиугольнике. Граф Дезарга состоит из 20 ребер этих двух многоугольников вместе с дополнительными 10 ребрами, соединяющими точки одного десятиугольника с соответствующими точками другого.
• Это Граф Леви из Конфигурация дезарга. Эта конфигурация состоит из десяти точек и десяти строк, описывающих два перспективные треугольники, их центр перспективы и их ось перспективы. Граф Дезарга имеет по одной вершине для каждой точки, по одной вершине для каждой линии и по одному ребру для каждой пары инцидентных точек и линий. Теорема дезарга, названный в честь французского математика 17 века Жерар Дезарг, описывает набор точек и линий, образующих эту конфигурацию, а конфигурация и граф получили свое название от него.
• Это двусторонняя двойная обложка из Граф Петерсена, образованный заменой каждой вершины графа Петерсена парой вершин и каждого ребра графа Петерсена парой скрещенных ребер.
• Это двудольный граф Кнезера ЧАС_5,2. Его вершины могут быть помечены десятью двухэлементными подмножествами и десятью трехэлементными подмножествами пятиэлементного набора с ребром, соединяющим две вершины, когда одно из соответствующих наборов является подмножеством другого. Эквивалентно граф Дезарга - это индуцированный подграф 5-мерного гиперкуба, определяемого вершинами веса 2 и веса 3.
• Граф Дезарга имеет вид Гамильтониан и может быть построен из Обозначение LCF: [5,−5,9,−9]⁵. Так как Erds предположил, что при положительном k подграф 2k + 1-мерного гиперкуба, индуцированный вершинами веса k и k + 1, является гамильтоновым, гамильтоничность графа Дезарга неудивительна. (Из более сильной гипотезы Ловаса также следует, что, за исключением нескольких известных контрпримеров, все вершинно-транзитивные графы имеют гамильтоновы циклы.)

Алгебраические свойства

Граф Дезарга - это симметричный граф: он имеет симметрии, которые переводят любую вершину в любую другую вершину и любое ребро в любое другое ребро. Его группа симметрии имеет порядок 240 и изоморфна произведению симметричная группа на 5 баллов с группой порядка 2.

Это представление продукта группы симметрии можно интерпретировать в терминах конструкций графа Дезарга: симметрическая группа по пяти точкам - это группа симметрии конфигурации Дезарга, а подгруппа порядка 2 меняет местами роли вершин, представляющих точки конфигурации Дезарга и вершины, представляющие линии. В качестве альтернативы, в терминах двудольного графа Кнезера, симметрическая группа на пяти точках действует отдельно на двухэлементные и трехэлементные подмножества пяти точек, а дополнение подмножеств образует группу второго порядка, которая преобразует один тип подмножества в другой. Симметрическая группа на пяти точках также является группой симметрии графа Петерсена, а подгруппа порядка 2 меняет местами вершины внутри каждой пары вершин, образованных в конструкции двойного покрытия.

Обобщенный граф Петерсена г(п, k) вершинно-транзитивно тогда и только тогда, когда п = 10 и k = 2 или если k² ≡ ± 1 (мод.п) и является реберно-транзитивным только в следующих семи случаях: (п, k) = (4, 1), (5, 2), (8, 3), (10, 2), (10, 3), (12, 5), (24, 5).^[3] Итак, граф Дезарга - один из семи симметричных обобщенных графов Петерсена. Среди этих семи графиков есть кубический график г(4, 1), Граф Петерсена г(5, 2), График Мёбиуса – Кантора г(8, 3), додекаэдрический граф г(10, 2) и Науру график  г(12, 5).

В характеристический многочлен графа Дезарга есть

${ displaystyle (x-3) (x-2) ^ {4} (x-1) ^ {5} (x + 1) ^ {5} (x + 2) ^ {4} (x + 3). ,}$

Следовательно, граф Дезарга является интегральный график: его спектр полностью состоит из целых чисел.

Приложения

В химия, граф Дезарга известен как Граф Дезарга – Леви; он используется для организации систем стереоизомеры из 5-лиганд соединения. В этом приложении тридцать ребер графа соответствуют псевдовращения лигандов.^[4][5]

Другие свойства

Граф Дезарга имеет номер прямолинейного перехода 6, и является наименьшим кубическим графом с этим числом пересечения (последовательность A110507 в OEIS ). Это единственная известная неплоская кубическая частичный куб.^[6]

Граф Дезарга имеет хроматическое число 2, хроматический индекс 3, радиус 5, диаметр 5 и обхват 6. Это также 3-вершинно-связанный и 3-реберный Гамильтонов граф. Она имеет толщина книги 3 и номер очереди 2.^[7]

Все кубический дистанционно регулярные графы известны.^[8] Граф Дезарга - один из 13 таких графов.

Граф Дезарга может быть вложен как само-Петри двойной обычная карта в неориентируемом многообразии рода 6 с декагональными гранями.

Галерея

• 

  График Дезарга раскрашен для выделения различных циклов.

• 

  В хроматический индекс графа Дезарга равно 3.

• 

  В хроматическое число графа Дезарга равно 2.

использованная литература