PROFILPELAJAR.COM

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

Граф Леві (також граф інцидентності) — двочастковий граф, відповідний структурі інцидентності^[1]^[2]. З набору точок і ліній у геометрії інцидентності або проєктивній конфігурації утворюється граф з однією вершиною для кожної точки, однією вершиною для кожної лінії і одного ребра для кожної інциденції точки і лінії (тобто відношення «точка лежить на лінії»). Ці графи назвали ім'ям Фрідріха Леві^[en] який описав їх 1942 року^[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 вершин.
Граф Грея є графом Леві конфігурації, яку можна отримати в R³ як 3×3×3 ґратку 27 точок і 27 ортогональних прямих, що проходять через ці точки.
8-клітка Татта є графом Леві конфігурації Кремони — Річмонда. Граф відомий також як (3,8)-клітка, є 3-регулярним і має 30 вершин.
Граф чотиривимірного гіперкуба Q₄ є графом Леві конфігурації Мебіуса, утвореної точками і площинами двох взаємно вписаних тетраедрів. Тут тетраедр вважається вписаним у інший, якщо всі його вершини лежать на площинах, що проходять через грані іншого тетраедра (не обов'язково на самих гранях).
Граф Любляни зі 112 вершинами є графом Леві конфігурації Любляни^[5].

Примітки

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