Граф Леви
двудольный граф, соответствующий структуре инцидентности / Материал из Википедии — свободной encyclopedia
Граф Ле́ви (также граф инциде́нтности) — двудольный граф, соответствующий структуре инцидентности[1][2]. Из набора точек и линий в геометрии инцидентности или проективной конфигурации образуется граф с одной вершиной для каждой точки, одной вершиной для каждой линии и одного ребра для каждой инциденции точки и линии (то есть отношения «точка лежит на линии»). Эти графы назвали именем Фридриха Леви[англ.], который описал их в 1942 году[1][3].
Граф Леви системы точек и линий обычно имеет обхват по меньшей мере шесть: любой цикл длины 4 должен соответствовать двум линиям, проходящим через те же самые две точки. Следовательно, любой двудольный граф с обхватом по меньшей мере шесть можно рассматривать как граф Леви абстрактной структуры инцидентности[1]. Графы Леви конфигураций являются бирегулярными[англ.] и любой бирегулярнй граф с обхватом как минимум шесть можно рассматривать как граф Леви абстрактной конфигурации[4].
Графы Леви можно также определить для других типов структур инциденций, таких как инциденции между точками и плоскостями в евклидовом пространстве. Для любого графа Леви существует эквивалентный гиперграф и наоборот.