Структура инцидентности
Структура инцидентности — в математике тройка
C = ( P , L , I ) . {displaystyle C=(P,L,I).} где P — это множество «точек», L — множество «линий», а I ⊆ P × L {displaystyle Isubseteq P imes L} — отношение инцидентности. Элементы I {displaystyle I} называются флагами. Если ( p , l ) ∈ I {displaystyle (p,l)in I} , мы говорим, что точка p «лежит на» линии l {displaystyle l} . Можно представить L как множество подмножеств P, и инцидентностью I будет включение ( ( p , l ) ∈ I {displaystyle (p,l)in I} в том и только в том случае, когда p ∈ l {displaystyle pin 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. Рёбра этого графа соответствуют флагам (инцидентным парам точка/линия) структуры инцидентности.
Пример: Граф Хивуда
Граф Леви плоскости Фано — это граф Хивуда. Поскольку граф Хивуда — связный и вершинно-транзитивный, существует автоморфизм (такой, например, как отражение относительно вертикальной оси на рисунке справа), обменивающий белые и чёрные вершины. Отсюда следует, что плоскость Фано самодвойственна.