![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/2/2e/Levi_graph_of_Pappus_Configuration.png/640px-Levi_graph_of_Pappus_Configuration.png&w=640&q=50)
Граф Леви
двудольный граф, соответствующий структуре инцидентности / Материал из Википедии — свободной encyclopedia
Граф Ле́ви (также граф инциде́нтности) — двудольный граф, соответствующий структуре инцидентности[1][2]. Из набора точек и линий в геометрии инцидентности или проективной конфигурации образуется граф с одной вершиной для каждой точки, одной вершиной для каждой линии и одного ребра для каждой инциденции точки и линии (то есть отношения «точка лежит на линии»). Эти графы назвали именем Фридриха Леви[англ.], который описал их в 1942 году[1][3].
Граф Ле́ви | |
---|---|
![]() Граф Паппа — граф Леви с 18 вершинами, образованный из конфигурации Паппа. Вершины, помеченные одной буквой, соответствуют точкам в конфигурации. Вершины, помеченные тремя буквами, соответствуют прямым, проходящим через три точки. | |
Обхват | ≥ 6 |
Граф Леви системы точек и линий обычно имеет обхват по меньшей мере шесть: любой цикл длины 4 должен соответствовать двум линиям, проходящим через те же самые две точки. Следовательно, любой двудольный граф с обхватом по меньшей мере шесть можно рассматривать как граф Леви абстрактной структуры инцидентности[1]. Графы Леви конфигураций являются бирегулярными[англ.] и любой бирегулярнй граф с обхватом как минимум шесть можно рассматривать как граф Леви абстрактной конфигурации[4].
Графы Леви можно также определить для других типов структур инциденций, таких как инциденции между точками и плоскостями в евклидовом пространстве. Для любого графа Леви существует эквивалентный гиперграф и наоборот.