Граф Леві

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

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

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

Графи Леві можна також визначити для інших типів структур інціденцій, таких як інціденції між точками і площинами в евклідовому просторі. Для будь-якого графу Леві існує еквівалентний гіперграф і навпаки.

Приклади

  • Граф Паппа є графом Леві конфігурації Паппа, що складається з 9 точок і 9 прямих. Як і в конфігурації Дезарга, на кожній прямій містяться 3 точки і через кожну точку проходять 3 прямі. Граф є 3-регулярним і має 18 вершин.
  • Граф Грея є графом Леві конфігурації, яку можна отримати в R3 як 3×3×3 ґратку 27 точок і 27 ортогональних прямих, що проходять через ці точки.

Примітки

  1. 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. — 3 листопада.

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.