Структура инцидентности

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В математике структурой инцидентности называется тройка

C=(P,L,I).\,

где P — это множество «точек», L — множество «линий», а I \subseteq P \times L — отношение инцидентности[en]. Элементы I называются флагами. Если

(p,l) \in I,

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

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

Сравнение с другими структурами[править | править вики-текст]

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

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

Двойственная структура[править | править вики-текст]

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

C = (P,L,I),

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

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

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

C** = C.

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

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

Соответствие гиперграфам[править | править вики-текст]

Семь точек являются элементами семи линий поверхности Фано[en]

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

Пример: поверхность Фано[править | править вики-текст]

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

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} }.

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

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

Геометрическое представление[править | править вики-текст]

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

Граф Леви структуры инцидентности[править | править вики-текст]

Граф Хивуда с метками

Любая структура инцидентности 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 .