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

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

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

Конструкции [ править ]

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

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

Алгебраические свойства [ править ]

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

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

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

Характеристический полином графа Дезарг является

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

Приложения [ править ]

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

Другие свойства [ править ]

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

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

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

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

Галерея [ править ]

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

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

  • Хроматического числа графа Дезарг 2.

Ссылки [ править ]

  1. ^ Вайсштейн, Эрик В. "График Дезарга" . MathWorld .
  2. ^ Kagno, IN (1947), "Дезарг и Папп графов и их группы", Американский журнал математики , The Johns Hopkins University Press, 69 (4): 859-863, DOI : 10,2307 / 2371806 , JSTOR 2371806 .
  3. ^ Frucht, R .; Graver, JE; Watkins, ME (1971), "Группы обобщенных графов Петерсена", Труды Кембриджского философского общества , 70 (02): 211-218, DOI : 10,1017 / S0305004100049811.
  4. ^ Балабан, AT; Fǎrcaşiu, D .; Bǎnic, R. (1966), "Графики множественных 1,2-сдвигов в ионах карбония и родственных системах", Rev. Roum. Чим. , 11 : 1205
  5. ^ Мислоу, Курт (1970), "Роль псевдовращения в стереохимии реакций нуклеофильного замещения", Acc. Chem. Res. , 3 (10): 321-331, DOI : 10.1021 / ar50034a001 CS1 maint: обескураженный параметр ( ссылка )
  6. ^ Клавжар, Санди; Липовец, Аленка (2003), «Частичные кубы как графы подразделений и как обобщенные графы Петерсена», Дискретная математика , 263 : 157–165, DOI : 10.1016 / S0012-365X (02) 00575-7
  7. ^ Вольц, Джессика, Разработка линейных макетов с помощью SAT. Магистерская работа, Тюбингенский университет, 2018 г.
  8. ^ Брауэр, AE ; Коэн, AM; и Ноймайер А. Дистанционно регулярные графы. Нью-Йорк: Springer-Verlag, 1989.