Структура инцидентности — в математике тройка

${\displaystyle C=(P,L,I).}$ где P — это множество «точек», L — множество «линий», а ${\displaystyle I\subseteq P\times L}$ — отношение инцидентности . Элементы ${\displaystyle I}$ называются флагами . Если

${\displaystyle (p,l)\in I}$ , мы говорим, что точка p «лежит на» линии ${\displaystyle l}$ . Можно представить L как множество подмножеств P, и инцидентностью I будет включение ( ${\displaystyle (p,l)\in I}$ в том и только в том случае, когда ${\displaystyle p\in l}$ ), но можно думать более абстрактно.

Структуры инцидентности обобщают плоскости (такие как , проективные и плоскости Мёбиуса ), как можно видеть из аксиоматических определений этих плоскостей. Структуры инцидентности также обобщают геометрические структуры более высокой размерности; при этом конечные структуры иногда называют конечными геометриями .

Сравнение с другими структурами

Изображение структуры инцидентности может выглядеть как граф , но в графах ребро имеет только две конечные точки, в то время как линия в структуре инцидентности может быть инцидентна более чем двум точкам. Таким образом, структуры инцидентности являются гиперграфами .

В структуре инцидентности нет понятия точки, лежащей между двумя другими точками. Порядок точек на линии не определён. Сравните с , которая имеет отношение «лежит между».

Двойственная структура

Если обменять роли «точек» и «линий» в структуре инцидентности

C = ( P , L , I ),

получится двойственная структура

C * = ( L , P , I *),

где I * — бинарное отношение, обратное к I . Ясно, что

C ** = C .

Эта операция является абстрактной версией проективной двойственности .

Структура C , изоморфная своей двойственной структуре C * называется самодвойственной .

Соответствие гиперграфам

Каждый гиперграф или систему множеств можно рассматривать как структуру инцидентности, в которой универсальное множество играет роль «точек», соответствующая система множеств играет роль «линий», а отношение инциденции — это принадлежность «∈». Обратно, любую структуру инциденций можно рассматривать как гиперграф.

Пример: плоскость Фано

В частности, пусть

P = {1, 2, 3, 4, 5, 6, 7},

L = { {1,2,3}, {1,4,5}, {1,6,7}, {2,4,6}, {2,5,7}, {3,4,7}, {3,5,6} }.

Соответствующая структура инцидентности называется плоскостью Фано .

Линии — в точности подмножества точек, состоящие из трёх точек, метки которых дополняются до нуля с помощью ним-суммы .

Геометрическое представление

Структуру инцидентности можно моделировать с помощью точек и кривых в евклидовой геометрии со стандартным геометрическим включением в качестве отношения инцидентности. Некоторые структуры инцидентности допускают представление с помощью точек и прямых, однако, например, поверхность Фано не имеет такого представления.

Граф Леви структуры инцидентности

Любая структура инцидентности C соответствует двудольному графу , называемому графом Леви , или графом инцидентности структуры. Поскольку любой двудольный граф можно раскрасить в два цвета, вершины графа Леви можно раскрасить в белые и чёрные цвета, где чёрные вершины соответствуют точкам и белые вершины соответствуют линиям C . Рёбра этого графа соответствуют флагам (инцидентным парам точка/линия) структуры инцидентности.

Пример: Граф Хивуда

Граф Леви плоскости Фано — это граф Хивуда . Поскольку граф Хивуда — связный и вершинно-транзитивный , существует автоморфизм (такой, например, как отражение относительно вертикальной оси на рисунке справа), обменивающий белые и чёрные вершины. Отсюда следует, что плоскость Фано самодвойственна.

См. также

• Конечная геометрия
• Бинарное отношение
• Комбинаторная схема
• Матрица инцидентности
• Инцидентность (геометрия)
• Конфигурация Паппа
• Проективная конфигурация
• Многодольный граф

Ссылки

• CRC Press (2000). Handbook of discrete and combinatorial mathematics , (Chapter 12.2), ISBN 0-8493-0149-1
• Mauro Biliotti, Vikram Jha, Norman L. Johnson (2001) Foundations of Translation Planes, Appendix V: Incidence Structures and Parallelisms , pp. 507-12, ISBN 0-8247-0609-9 .
• Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1986), , Cambridge University Press, ISBN 3-411-01675-2
• Biliotti, Mauro; Jha, Vikram; Johnson, Norman L. (2001), Foundations of Translation Planes , , ISBN 0-8247-0609-9
• Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), (2nd ed.), Boca Raton: Chapman & Hall/ CRC, ISBN 1-58488-506-8
• Dembowski, Peter (1968), , , Band 44, Berlin, New York: Springer-Verlag , ISBN 3-540-61786-8 , MR
• G. Eric Moorhouse (2014) via John Baez at
• Pisanski, Tomaž; (2013), Configurations from a Graphical Viewpoint , Springer, doi : , ISBN 978-0-8176-8363-4