Граф Леви

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Граф Леви
Граф Паппа — граф Леви с 18 вершинами, образованный из конфигурации Паппа. Вершины, помеченные одной буквой, соответствуют точкам в конфигурации. Вершины, помеченные тремя буквами, соответствуют прямым, проходящим через три точки.
Граф Паппа — граф Леви с 18 вершинами, образованный из конфигурации Паппа. Вершины, помеченные одной буквой, соответствуют точкам в конфигурации. Вершины, помеченные тремя буквами, соответствуют прямым, проходящим через три точки.
Обхват

≥ 6

Граф Леви (также граф инцидентности) — двудольный граф, соответствующий структуре инцидентности.[1][2] Из набора точек и линий в геометрии инцидентности[en] или проективной конфигурации[en] образуется граф с одной вершиной для каждой точки, одной вершиной для каждой линии и одного ребра для каждой инциденции точки и линии (то есть отношения «точка лежит на линии»). Эти графы назвали именем Фридриха Леви[en], который описал их в 1942 году[1][3].

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

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

Примеры[править | править исходный текст]

  • Граф Паппа является графом Леви конфигурации Паппа, состоящей из 9 точек и 9 прямых. Как и в конфигурации Дезарга на каждой прямой находятся 3 точки и через каждую точку проходят 3 прямые. Граф является 3-регулярным и имеет 18 вершин.
  • Граф Грея является графом Леви конфигурации, которую можно получить в R3 как 3×3×3 решётку 27 точек и 27 ортогональных прямых, проходящих через эти точки.
  • Граф четырёхмерного гиперкуба Q4 является графом Леви конфигурации Мёбиуса, образованной точками и плоскостями двух взаимно вписанных тетраэдров. Здесь тетраэдр считается вписанным в другой, если все его вершины лежат на плоскостях, проходящих через грани другого тетраэдра (не обязательно на самих гранях).

Примечания[править | править исходный текст]

  1. 1 2 3 Branko Grünbaum The Coxeter Legacy. — Providence, RI: American Mathematical Society, 2006. — С. 179–225.. Смотрите, в частности, стр. 181.
  2. Burkard Polster A Geometrical Picture Book. — New York: Springer-Verlag, 1998. — С. 5. — (Universitext). — ISBN 0-387-98437-2 — DOI:10.1007/978-1-4419-8526-2.
  3. F. W. Levi Finite Geometrical Systems. — Calcutta: University of Calcutta, 1942.
  4. Harald Gropp Handbook of combinatorial designs / Charles J. Colbourn, Jeffrey H. Dinitz. — Second. — Chapman & Hall/CRC, Boca Raton, FL, 2007. — С. 353–355. — (Discrete Mathematics and its Applications (Boca Raton))..
  5. M. Conder, A. Malnič, D. Marušič, T. Pisanski, З. Potočnik. The Ljubljana Graph. — University of Ljubljana Department of Mathematics, 2002.

Ссылки[править | править исходный текст]