график Леви

В комбинаторной математике граф Леви или граф инцидентности — это двудольный граф , связанный со структурой инцидентности . ^{[1] [2]} Из набора точек и линий в геометрии инцидентности или проективной конфигурации мы формируем граф с одной вершиной на точку, одной вершиной на линию и ребром для каждого инцидента между точкой и линией. Они названы в честь Фридриха Вильгельма Леви , который писал о них в 1942 году. ^{[1] [3]}

Граф Леви системы точек и линий обычно имеет обхват не менее шести: любые 4- циклы будут соответствовать двум линиям, проходящим через те же две точки. Наоборот, любой двудольный граф с обхватом не менее шести можно рассматривать как граф Леви абстрактной структуры инцидентности. ^[1] Графы Леви конфигураций являются бирегулярными , и каждый бирегулярный граф с обхватом не менее шести можно рассматривать как граф Леви абстрактной конфигурации. ^[4]

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

Примеры

Граф Хивуда и плоскость Фано
Вершина 3 является частью кругового ребра (3, 5, 6) , диагонального ребра (3, 7, 4) и бокового ребра (1, 3, 2) .

• Граф Дезарга — это граф Леви конфигурации Дезарга , состоящий из 10 точек и 10 прямых. На каждой прямой лежит 3 точки, и через каждую точку проходит 3 прямые. Граф Дезарга можно также рассматривать как обобщенный граф Петерсена G(10,3) или двудольный граф Кнезера с параметрами 5,2. Он является 3-регулярным с 20 вершинами.
• Граф Хивуда — это граф Леви плоскости Фано . Он также известен как (3,6) -клетка и является 3-регулярным с 14 вершинами.
• Граф Мёбиуса–Кантора — это граф Леви конфигурации Мёбиуса–Кантора , системы из 8 точек и 8 линий, которые не могут быть реализованы прямыми линиями на евклидовой плоскости. Он является 3-регулярным с 16 вершинами.
• Граф Паппуса — это граф Леви конфигурации Паппуса , состоящий из 9 точек и 9 прямых. Как и в конфигурации Дезарга, на каждой прямой есть 3 точки и через каждую точку проходит 3 прямые. Он 3-регулярный с 18 вершинами.
• Граф Грея — это граф Леви конфигурации, которую можно реализовать в виде сетки из 27 точек и 27 ортогональных линий, проходящих через них. ${\displaystyle \mathbb {R} ^{3}}$ ${\displaystyle 3\times 3\times 3}$
• Восьмеричная клетка Тутта — это граф Леви конфигурации Кремоны–Ричмонда . Она также известна как (3,8)-клетка и является 3-регулярной с 30 вершинами.
• Четырехмерный граф гиперкуба представляет собой граф Леви конфигурации Мёбиуса , образованной точками и плоскостями двух взаимно инцидентных тетраэдров. ${\displaystyle Q_{4}}$
• Граф Любляны на 112 вершинах — это граф Леви конфигурации Любляны. ^[5]

Ссылки

1. Грюнбаум, Бранко (2006), «Конфигурации точек и линий», The Coxeter Legacy , Провиденс, Род-Айленд: Американское математическое общество, стр. 179–225, MR  2209028. См. в частности стр. 181.
2. Польстер, Буркард (1998), Книга с геометрическими картинками, Universitext, Нью-Йорк: Springer-Verlag, стр. 5, номер домена : 10.1007/978-1-4419-8526-2, ISBN 0-387-98437-2, МР  1640615.
3. Леви, Ф. В. (1942), Конечные геометрические системы , Калькутта: Университет Калькутты , MR  0006834.
4. Гропп, Харальд (2007), «VI.7 Конфигурации», в Колборн, Чарльз Дж.; Диниц, Джеффри Х. (ред.), Справочник комбинаторных конструкций , Дискретная математика и ее приложения (Бока-Ратон) (Второе издание), Чапман и Холл/CRC, Бока-Ратон, Флорида, стр. 353–355.
5. Кондер, Марстон ; Мальнич, Александр; Марушич, Драган ; Писански, Томаж ; Поточник, Примож (2002), Люблянский график (PDF) , Препринт IMFM 40-845, Математический факультет Люблянского университета.

Внешние ссылки

• Вайсштейн, Эрик В. «Граф Леви». MathWorld .