Loading AI tools
двудольный граф, соответствующий структуре инцидентности Из Википедии, свободной энциклопедии
Граф Ле́ви (также граф инциде́нтности) — двудольный граф, соответствующий структуре инцидентности[1][2]. Из набора точек и линий в геометрии инцидентности или проективной конфигурации образуется граф с одной вершиной для каждой точки, одной вершиной для каждой линии и одного ребра для каждой инциденции точки и линии (то есть отношения «точка лежит на линии»). Эти графы назвали именем Фридриха Леви[англ.], который описал их в 1942 году[1][3].
Граф Ле́ви | |
---|---|
| |
Обхват | ≥ 6 |
Граф Леви системы точек и линий обычно имеет обхват по меньшей мере шесть: любой цикл длины 4 должен соответствовать двум линиям, проходящим через те же самые две точки. Следовательно, любой двудольный граф с обхватом по меньшей мере шесть можно рассматривать как граф Леви абстрактной структуры инцидентности[1]. Графы Леви конфигураций являются бирегулярными[англ.] и любой бирегулярнй граф с обхватом как минимум шесть можно рассматривать как граф Леви абстрактной конфигурации[4].
Графы Леви можно также определить для других типов структур инциденций, таких как инциденции между точками и плоскостями в евклидовом пространстве. Для любого графа Леви существует эквивалентный гиперграф и наоборот.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.