Структура инцидентности — в математике тройка где P — это множество «точек», L — множество «линий», а — отношение инцидентности. Элементы называются флагами. Если , мы говорим, что точка p «лежит на» линии . Можно представить L как множество подмножеств P, и инцидентностью I будет включение ( в том и только в том случае, когда ), но можно думать более абстрактно.
Структуры инцидентности обобщают плоскости (такие как , проективные и плоскости Мёбиуса), как можно видеть из аксиоматических определений этих плоскостей. Структуры инцидентности также обобщают геометрические структуры более высокой размерности; при этом конечные структуры иногда называют конечными геометриями.
Сравнение с другими структурами Изображение структуры инцидентности может выглядеть как граф, но в графах ребро имеет только две конечные точки, в то время как линия в структуре инцидентности может быть инцидентна более чем двум точкам. Таким образом, структуры инцидентности являются гиперграфами.
В структуре инцидентности нет понятия точки, лежащей между двумя другими точками. Порядок точек на линии не определён. Сравните с , которая имеет отношение «лежит между».
Двойственная структура Если обменять роли «точек» и «линий» в структуре инцидентности
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, Marcel Dekker ISBN 0-8247-0609-9 .
G. Eric Moorhouse (2014) Incidence Geometry via John Baez at University of California, Riverside
Категория:Геометрия инцидентности Категория:Классическая геометрия