График Леви

В комбинаторной математике граф Леви или граф инцидентности представляет собой двудольный граф , связанный со структурой инцидентности . ^{[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. Леви, FW (1942), Конечные геометрические системы , Калькутта: Калькуттский университет , MR  0006834.
4. Гропп, Харальд (2007), «Конфигурации VI.7», в Колборне, Чарльз Дж.; Диниц, Джеффри Х. (ред.), Справочник по комбинаторным расчетам , Дискретная математика и ее приложения (Бока-Ратон) (второе изд.), Chapman & Hall/CRC, Бока-Ратон, Флорида, стр. 353–355..
5. Кондер, Марстон ; Мальнич, Александр; Марушич, Драган ; Писански, Томаж ; Поточник, Примож (2002), Люблянский график (PDF) , Препринт IMFM 40-845, Математический факультет Люблянского университета.

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

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