Граф Леві
Граф Леві (також граф інцидентності) — двочастковий граф, відповідний структурі інцидентності[1][2]. З набору точок і ліній у геометрії інцидентності або проєктивній конфігурації утворюється граф з однією вершиною для кожної точки, однією вершиною для кожної лінії і одного ребра для кожної інциденції точки і лінії (тобто відношення «точка лежить на лінії»). Ці графи назвали ім'ям Фрідріха Леві який описав їх 1942 року[3].
| Граф Ле́ви | |
|---|---|
 Граф Паппа — граф Леві з 18 вершинами, утворений з конфігурації Паппа. Вершини, позначені однією буквою, відповідають точкам у конфігурації. Вершини, позначені трьома буквами, відповідають прямим, що проходять через три точки. | |
| Обхват | ≥ 6 |
Граф Леві системи точок і ліній зазвичай має обхват щонайменше шість: будь-який цикл довжини 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 вершин.
- Граф Грея є графом Леві конфігурації, яку можна отримати в R3 як 3×3×3 ґратку 27 точок і 27 ортогональних прямих, що проходять через ці точки.
- 8-клітка Татта є графом Леві конфігурації Кремони — Річмонда. Граф відомий також як (3,8)-клітка, є 3-регулярним і має 30 вершин.
- Граф чотиривимірного гіперкуба Q4 є графом Леві конфігурації Мебіуса, утвореної точками і площинами двох взаємно вписаних тетраедрів. Тут тетраедр вважається вписаним у інший, якщо всі його вершини лежать на площинах, що проходять через грані іншого тетраедра (не обов'язково на самих гранях).
- Граф Любляни зі 112 вершинами є графом Леві конфігурації Любляни[5].
Примітки
- Branko Grünbaum. The Coxeter Legacy. — Providence, RI : American Mathematical Society, 2006. — С. 179—225. Див., зокрема, стр. 181.
- Burkard Polster. A Geometrical Picture Book. — New York : Springer-Verlag, 1998. — С. 5. — (Universitext) — ISBN 0-387-98437-2. — DOI:
- F. W. Levi. Finite Geometrical Systems. — Calcutta : University of Calcutta, 1942.
- 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))
- M. Conder, A. Malnič, D. Marušič, T. Pisanski, З. Potočnik. The Ljubljana Graph. — University of Ljubljana Department of Mathematics, 2002. — 3 листопада.