Граф Леві

Граф Леві (також граф інцидентності) — двочастковий граф, відповідний структурі інцидентності. З набору точок і ліній у геометрії інцидентності або проєктивній конфігурації утворюється граф з однією вершиною для кожної точки, однією вершиною для кожної лінії і одного ребра для кожної інциденції точки і лінії (тобто відношення «точка лежить на лінії»). Ці графи назвали ім'ям ^[en] який описав їх 1942 року.

Граф Ле́ви
Граф Паппа — граф Леві з 18 вершинами, утворений з конфігурації Паппа. Вершини, позначені однією буквою, відповідають точкам у конфігурації. Вершини, позначені трьома буквами, відповідають прямим, що проходять через три точки.
(Обхват)	≥ 6

Граф Леві системи точок і ліній зазвичай має обхват щонайменше шість: будь-який цикл довжини 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 вершин.

• Граф Грея є графом Леві конфігурації, яку можна отримати в R³ як 3×3×3 ґратку 27 точок і 27 ортогональних прямих, що проходять через ці точки.

• 8-клітка Татта є графом Леві конфігурації Кремони — Річмонда. Граф відомий також як (3,8)-клітка, є 3-регулярним і має 30 вершин.

• Граф чотиривимірного гіперкуба Q₄ є графом Леві конфігурації Мебіуса, утвореної точками і площинами двох взаємно вписаних тетраедрів. Тут тетраедр вважається вписаним у інший, якщо всі його вершини лежать на площинах, що проходять через грані іншого тетраедра (не обов'язково на самих гранях).

• Граф Любляни зі 112 вершинами є графом Леві конфігурації Любляни.

Примітки

1. Branko Grünbaum. The Coxeter Legacy. — Providence, RI : American Mathematical Society, 2006. — С. 179—225. Див., зокрема, стр. 181 [ 1 квітня 2018 у Wayback Machine.].
2. Burkard Polster. [1] — New York : Springer-Verlag, 1998. — С. 5. — (Universitext) — . — DOI:10.1007/978-1-4419-8526-2. з джерела 29 травня 2021
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. — 16 червня. з джерела 2 березня 2012. Процитовано 17 червня 2021.

Посилання

• Weisstein, Eric W. Граф Леві(англ.) на сайті Wolfram MathWorld.