Граф Леві
двочастковий граф, відповідний структурі інцидентності / З Вікіпедії, безкоштовно encyclopedia
Граф Леві (також граф інцидентності) — двочастковий граф, відповідний структурі інцидентності[1][2]. З набору точок і ліній у геометрії інцидентності або проєктивній конфігурації утворюється граф з однією вершиною для кожної точки, однією вершиною для кожної лінії і одного ребра для кожної інциденції точки і лінії (тобто відношення «точка лежить на лінії»). Ці графи назвали ім'ям Фрідріха Леві[en] який описав їх 1942 року[3].
Граф Ле́ви | |
---|---|
Граф Паппа — граф Леві з 18 вершинами, утворений з конфігурації Паппа. Вершини, позначені однією буквою, відповідають точкам у конфігурації. Вершини, позначені трьома буквами, відповідають прямим, що проходять через три точки. | |
Обхват | ≥ 6 |
Граф Леві системи точок і ліній зазвичай має обхват щонайменше шість: будь-який цикл довжини 4 має відповідати двом лініям, що проходять через ті самі дві точки. Отже, будь-який двочастковий граф з обхватом щонайменше шість можна розглядати як граф Леві абстрактної структури інцидентності[1]. Графи Леві конфігурацій є бірегулярними і будь-який бірегулярнй граф з обхватом принаймні шість можна розглядати як граф Леві абстрактної конфігурації[4].
Графи Леві можна також визначити для інших типів структур інціденцій, таких як інціденції між точками і площинами в евклідовому просторі. Для будь-якого графу Леві існує еквівалентний гіперграф і навпаки.