График Леви
| График Леви | |
|---|---|
 Граф Паппуса — граф Леви с 18 вершинами, сформированный из конфигурации Паппуса . Вершины, помеченные одиночными буквами, соответствуют точкам конфигурации; вершины, отмеченные тремя буквами, соответствуют линиям, проходящим через три точки. | |
| Обхват | ≥ 6 |
| Таблица графиков и параметров | |
В комбинаторной математике граф Леви или граф инцидентности представляет собой двудольный граф, связанный со структурой инцидентности . [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 ортогональных прямых, проходящих через них.
- Восьмиклетка Тутте представляет собой граф Леви конфигурации Кремоны – Ричмонда . Она также известна как (3,8)-клетка и является 3-регулярной с 30 вершинами.
- Четырехмерный граф гиперкуба — граф Леви конфигурации Мёбиуса, образованный точками и плоскостями двух взаимно инцидентных тетраэдров.
- Люблянский граф на 112 вершинах — это граф Леви люблянской конфигурации. [5]
Ссылки
[ редактировать ]- ^ Jump up to: а б с Грюнбаум, Бранко (2006), «Конфигурации точек и линий», The Coxeter Legacy , Провиденс, Род-Айленд: Американское математическое общество, стр. 179–225, MR 2209028 . См., в частности, стр. 181 .
- ^ Польстер, Буркард (1998), Книга с геометрическими картинками , Universitext, Нью-Йорк: Springer-Verlag, стр. 5, номер домена : 10.1007/978-1-4419-8526-2 , ISBN. 0-387-98437-2 , МР 1640615 .
- ^ Леви, Ф.В. (1942), Конечные геометрические системы , Калькутта: Калькуттский университет , MR 0006834 .
- ^ Гропп, Харальд (2007), «Конфигурации VI.7», в Колборне, Чарльз Дж.; Диниц, Джеффри Х. (ред.), Справочник по комбинаторным расчетам , Дискретная математика и ее приложения (Бока-Ратон) (второе изд.), Chapman & Hall/CRC, Бока-Ратон, Флорида, стр. 353–355 .
- ^ Кондер, Марстон ; Мальнич, Александр; Марушич, Драган ; Писански, Томаж ; Поточник, Примож (2002), Люблянский график (PDF) , Препринт IMFM 40-845, Математический факультет Люблянского университета .