Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
В комбинаторной математике, граф Леви, или инцидентный граф, — это двудольный граф, связанный с инцидентной структурой. Из набора точек и прямых в инцидентной геометрии или проективной конфигурации формируется граф с одной вершиной для каждой точки, одной вершиной для каждой прямой и ребром для каждой пары точка-прямая, лежащих в отношении инцидентности. Графы названы в честь Фридриха Вильгельма Леви, который опубликовал работы о них в 1942 году. Граф Леви системы точек и прямых обычно имеет длину окружности не менее шести: любой 4-цикл соответствует двум прямым, проходящим через одни и те же две точки. Обратно, любой двудольный граф с длиной окружности не менее шести можно рассматривать как граф Леви абстрактной инцидентной структуры. Графы Леви также могут быть определены для других типов инцидентных структур, таких как отношения инцидентности между точками и плоскостями в евклидовом пространстве. Для каждого графа Леви существует эквивалентный гиперграф, и наоборот.
In combinatorial mathematics, a Levi graph or incidence graph is a bipartite graph associated with an incidence structure. From a collection of points and lines in an incidence geometry or a projective configuration, we form a graph with one vertex per point, one vertex per line, and an edge for every incidence between a point and a line. They are named for Friedrich Wilhelm Levi, who wrote about them in 1942. The Levi graph of a system of points and lines usually has girth at least six: Any 4 cycles would correspond to two lines through the same two points. Conversely any bipartite graph with girth at least six can be viewed as the Levi graph of an abstract incidence structure. Levi graphs may also be defined for other types of incidence structure, such as the incidences between points and planes in Euclidean space. For every Levi graph, there is an equivalent hypergraph, and vice versa.
Примеры
Граф Дезарге — это граф Леви конфигурации Дезарге, состоящий из 10 точек и 10 линий. На каждой прямой находится 3 точки, и через каждую точку проходят 3 линии. Граф Дезарге также можно рассматривать как обобщенный граф Петерсена G(10,3) или двудольный граф Кнезера с параметрами 5,2. Он 3-регулярен и имеет 20 вершин. Граф Хивуда — это граф Леви плоскости Фано. Он также известен как клетка (3,6) и 3-регулярен с 14 вершинами. Граф Мёбиуса — Кантора — это граф Леви конфигурации Мёбиуса — Кантора, системы из 8 точек и 8 линий, которые нельзя реализовать прямыми линиями в евклидовой плоскости. Он 3-регулярен и имеет 16 вершин. Граф Паппуса — это граф Леви конфигурации Паппуса, состоящий из 9 точек и 9 линий. Как и в конфигурации Дезарге, на каждой прямой находится 3 точки и через каждую точку проходят 3 линии. Он 3-регулярен и имеет 18 вершин. Граф Грея — это граф Леви конфигурации, которую можно реализовать в виде сетки из 27 точек и 27 ортогональных линий, проходящих через них. Клетка Тутте из восьми — это граф Леви конфигурации Кремона — Ричмонд. Он также известен как клетка (3,8) и 3-регулярен с 30 вершинами. Четырехмерный гиперкубический граф — это граф Леви конфигурации Мёбиуса, образованный точками и плоскостями двух взаимно пересекающихся тетраэдров. Люблянский граф на 112 вершинах — это граф Леви конфигурации Любляны.
The Desargues graph is the Levi graph of the Desargues configuration, composed of 10 points and 10 lines. There are 3 points on each line, and 3 lines passing through each point. The Desargues graph can also be viewed as the generalized Petersen graph G(10,3) or the bipartite Kneser graph with parameters 5,2. It is 3 regular with 20 vertices. The Heawood graph is the Levi graph of the Fano plane. It is also known as the (3,6) cage, and is 3 regular with 14 vertices. The Möbius–Kantor graph is the Levi graph of the Möbius–Kantor configuration, a system of 8 points and 8 lines that cannot be realized by straight lines in the Euclidean plane. It is 3 regular with 16 vertices. The Pappus graph is the Levi graph of the Pappus configuration, composed of 9 points and 9 lines. Like the Desargues configuration there are 3 points on each line and 3 lines passing through each point. It is 3 regular with 18 vertices. The Gray graph is the Levi graph of a configuration that can be realized in as a grid of 27 points and the 27 orthogonal lines through them. The Tutte eight cage is the Levi graph of the Cremona–Richmond configuration. It is also known as the (3,8) cage, and is 3 regular with 30 vertices. The four dimensional hypercube graph is the Levi graph of the Möbius configuration formed by the points and planes of two mutually incident tetrahedra. The Ljubljana graph on 112 vertices is the Levi graph of the Ljubljana configuration.