Введение
Абстрактная математическая система, состоящая из двух типов объектов и отношения между ними.
В математике структура инцидентности — это абстрактная система, состоящая из двух типов объектов и единственного отношения между этими типами объектов. Рассмотрим точки и прямые евклидовой плоскости как два типа объектов и игнорируйте все свойства этой геометрии, кроме отношения принадлежности точек прямым для всех точек и прямых. В результате получается структура инцидентности евклидовой плоскости. Структуры инцидентности чаще всего рассматриваются в геометрическом контексте, откуда они абстрагируются и, следовательно, обобщают плоскости (такие как аффинные, проективные и плоскости Мёбиуса), но концепция очень широка и не ограничивается геометрическими задачами. Даже в геометрическом контексте структуры инцидентности не ограничиваются только точками и прямыми; можно использовать объекты более высокой размерности (плоскости, тела, n-мерные пространства, конические сечения и т. д.). Изучение конечных структур иногда называют конечной геометрией.
Формальное определение и терминология
Структура инцидентности — это тройка (P, L, I), где P — множество, элементы которого называются точками, L — отличное множество, элементы которого называются прямыми, и I ⊆ P × L — отношение инцидентности. Элементы I называются флагами. Если (p, l) принадлежит I, то можно сказать, что точка p "лежит на" прямой l или что прямая l "проходит через" точку p. Более "симметричная" терминология, отражающая симметричный характер этого отношения, заключается в том, что "p инцидентна l" или что "l инцидентна p", и используется обозначение p I l как синоним (p, l) ∈ I. В некоторых распространенных ситуациях L может быть множеством подмножеств P, в этом случае инцидентность I будет означать принадлежность (p I l тогда и только тогда, когда p является элементом l). Структуры инцидентности такого типа называются теоретико-множественными. Это не всегда так; например, если P — множество векторов, а L — множество квадратных матриц, мы можем определить…
Этот пример также показывает, что, хотя используется геометрическая терминология точек и прямых, типы объектов не обязательно должны быть этими геометрическими объектами.
Примеры
Инцидентная структура является однородной, если каждая прямая инцидентна одному и тому же числу точек. Каждый из этих примеров, за исключением второго, является однородным, содержащим по три точки на каждой прямой.
Графики
Любой граф (который не обязательно должен быть простым; допускаются петли и кратные ребра) является однородной структурой инцидентности с двумя точками на каждой линии. В этих примерах вершины графа образуют множество точек, ребра графа образуют множество линий, а инцидентность означает, что вершина является концом ребра.
Сети
Более специализированным примером является k-сеть. Это инцидентная структура, в которой линии разбиваются на k параллельных классов, так что две линии из одного и того же параллельного класса не имеют общих точек, а любые две линии из разных классов имеют ровно одну общую точку, и каждая точка принадлежит ровно одной линии из каждого параллельного класса. Примером k-сети является множество точек аффинной плоскости вместе с k параллельными классами аффинных линий.
Изобразительные изображения
Фигура инцидентности (то есть изображение структуры инцидентности) строится путем представления точек точками на плоскости и использования каких-либо визуальных средств для соединения этих точек, соответствующих линиям. С другой стороны, примеры 2 и 5, приведенные выше, реализуемы, и фигуры инцидентности, представленные там, это демонстрируют. Штайниц (1894) показал, что (структуры инцидентности с n точками и n линиями, тремя точками на каждой линии и тремя линиями, проходящими через каждую точку) либо реализуемы, либо требуют использования только одной кривой линии в их изображениях. Плоскость Фано является единственной (73), а конфигурация Мёбиуса — Кантора является единственной (83).
График заболеваемости (график Леви)
Каждая инцидентная структура C соответствует двудольному графу, называемому графом Леви или инцидентным графом структуры. Поскольку любой двудольный граф двухцветный, графу Леви можно задать раскраску вершин в черный и белый цвет, где черные вершины соответствуют точкам, а белые вершины – прямым структуры C. Ребра этого графа соответствуют флагам (пара точка/прямая) инцидентной структуры. Изначальный граф Леви был инцидентным графом обобщенного четырехугольника порядка два (пример 3 выше), но этот термин был расширен Х. С. М. Коксетером для обозначения инцидентного графа любой инцидентной структуры.
Примеры графика Леви
График Леви плоскости Фано является графом Хевуда. Поскольку граф Хевуда связен и вершинно-транзитивен, существует автоморфизм (например, определяемый отражением относительно вертикальной оси на рисунке графа Хевуда), который переставляет черные и белые вершины. Это, в свою очередь, означает, что плоскость Фано является самодвойственной. Конкретное представление слева графа Леви конфигурации Мёбиуса–Кантора (пример 4 выше) иллюстрирует, что вращение вокруг центра (по часовой стрелке или против часовой стрелки) диаграммы переставляет синие и красные вершины и отображает ребра в ребра. Иными словами, для этого графа существует автоморфизм, меняющий цвета вершин. Следовательно, инцидентная структура, известная как конфигурация Мёбиуса–Кантора, является самодвойственной.
Обобщение
Можно обобщить понятие инцидентной структуры, чтобы включить более двух типов объектов. Структура с k типами объектов называется инцидентной структурой ранга k или геометрией ранга k. Формально они определяются как k + 1 кортежей S = (P1, P2, ..., Pk, I) с условием Pi ∩ Pj = ∅ и
Граф Леви для этих структур определяется как многодольный граф, вершины которого, соответствующие каждому типу объектов, окрашены в один и тот же цвет.