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