Граф Леви - Levi graph

Граф Леви
Граф Леви из Pappus Configuration.png
В График Паппа, граф Леви с 18 вершинами, образованный Конфигурация Pappus. Вершины, помеченные одиночными буквами, соответствуют точкам в конфигурации; вершины, помеченные тремя буквами, соответствуют линиям, проходящим через три точки.
Обхват≥ 6
Таблица графиков и параметров

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

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

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

Примеры

Рекомендации

  1. ^ а б c Грюнбаум, Бранко (2006), «Конфигурации точек и линий», Наследие Кокстера, Провиденс, Род-Айленд: Американское математическое общество, стр. 179–225, Г-Н  2209028. См. В частности п. 181.
  2. ^ Polster, Burkard (1998), Геометрическая книга с картинками, Universitext, New York: Springer-Verlag, p. 5, Дои:10.1007/978-1-4419-8526-2, ISBN  0-387-98437-2, Г-Н  1640615.
  3. ^ Леви, Ф. В. (1942), Конечные геометрические системы, Калькутта: Калькуттский университет, Г-Н  0006834.
  4. ^ Gropp, Harald (2007), «Конфигурации VI.7», в Colbourn, Charles J .; Диниц, Джеффри Х. (ред.), Справочник комбинаторных планов, Дискретная математика и ее приложения (Бока-Ратон) (второе изд.), Chapman & Hall / CRC, Бока-Ратон, Флорида, стр. 353–355..
  5. ^ Кондер, Марстон; Малнич, Александр; Марушич, Драган; Писанский, Томаж; Поточник, Примож (2002), Люблянский график (PDF), Препринт МВФМ 40-845, факультет математики Люблянского университета.

внешняя ссылка