Граф Леві (також граф інцидентності) — двочастковий граф, відповідний структурі інцидентності Див., зокрема, стр. 181 .. З набору точок і ліній у геометрії інцидентності або проєктивній конфігурації утворюється граф з однією вершиною для кожної точки, однією вершиною для кожної лінії і одного ребра для кожної інциденції точки і лінії (тобто відношення «точка лежить на лінії»). Ці графи назвали ім'ям який описав їх 1942 року.
Граф Леві системи точок і ліній зазвичай має обхват щонайменше шість: будь-який цикл довжини 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 вершинами є графом Леві конфігурації Любляни.
Примітки
Посилання