Структура заболеваемости

Примеры структур инцидентности:
Пример 1: точки и линии евклидовой плоскости (вверху),
Пример 2: точки и окружности (в середине),
Пример 3: конечная структура инцидентности, определяемая матрицей инцидентности (внизу).

В математике структура инцидентности — это абстрактная система, состоящая из двух типов объектов и единственного отношения между этими типами объектов. Рассмотрим точки и прямые евклидовой плоскости как два типа объектов и проигнорируем все свойства этой геометрии, за исключением отношения того, какие точки инцидентны каким прямым для всех точек и прямых. Остается структура инцидентности евклидовой плоскости.

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

Формальное определение и терминология

Структура инцидентности — это тройка ( $P, L, I$ ), где $P$ — множество, элементы которого называются точками , $L$ — отдельное множество, элементы которого называются прямыми , а $I \subseteq P \times L$ — отношение инцидентности . Элементы $I$ называются флагами. Если ( $p$ $,$ $l$ ) принадлежит $I$ , то можно сказать, что точка $p$ «лежит на» прямой $l$ или что прямая $l$ «проходит через» точку $p$ . Более «симметричная» терминология, отражающая симметричную природу этого отношения, заключается в том, что « p инцидентен $l$ » или $что$ « $l$ инцидентен $p$ », и использует обозначение $p$ $I$ $l$ как синоним $($ $p$ $,$ $l$ $) \in$ $I.$ ^[2]

В некоторых общих ситуациях $L$ может быть множеством подмножеств $P$ , в этом случае инцидентность $I$ будет включением ( $p I l$ тогда и только тогда, когда $p$ является членом $l$ ). Структуры инцидентности такого типа называются теоретико-множественными . ^[3] Это не всегда так, например, если $P$ — множество векторов, а $L —$ множество квадратных матриц , мы можем определить Этот пример также показывает, что хотя используется геометрический язык точек и линий, типы объектов не обязательно должны быть этими геометрическими объектами. $I=\{(v,M):{\vec {v}}{\text{ — собственный вектор матрицы }}M\}.$

Примеры

Некоторые примеры структур инцидентности

Структура инцидентности равномерна , если каждая линия инцидентна с одинаковым числом точек. Каждый из этих примеров, за исключением второго, равномерен с тремя точками на линию.

Графики

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

Линейные пространства

Структуры инцидентности редко изучаются в их полной общности; типично изучать структуры инцидентности, которые удовлетворяют некоторым дополнительным аксиомам. Например, частичное линейное пространство является структурой инцидентности, которая удовлетворяет:

Любые две различные точки инцидентны не более чем одной общей прямой, и
Каждая прямая инцидентна по крайней мере двум точкам.

Если первую аксиому заменить более сильной:

Любые две различные точки инцидентны ровно одной общей прямой,

структура инцидентности называется линейным пространством . ^[4]^[5]

Сетки

Более специализированным примером является $k$ -сеть . Это структура инцидентности, в которой линии попадают в $k$ параллельных классов , так что две линии в одном параллельном классе не имеют общих точек, но две линии в разных классах имеют ровно одну общую точку, и каждая точка принадлежит ровно одной линии из каждого параллельного класса. Примером $k$ -сети является множество точек аффинной плоскости вместе с $k$ параллельными классами аффинных линий.

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

$Если поменять местами$ роли «точек» и «линий» в , то получим двойственную структуру , где $I$ $*$ — обратное отношение I . Из определения немедленно следует, что: $C=(P,L,I)$ $C^{*}=(L,P,I^{*})$ $С^{**}=С$

Это абстрактная версия проективной двойственности . ^[2]

Структура $C$ , изоморфная своей дуальной $C *,$ называется самодуальной . Плоскость Фано выше является самодуальной структурой инцидентности.

Другая терминология

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

Гиперграфы

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

Блочные конструкции

(Общая) блочная конструкция — это множество $X$ вместе с семейством $F$ подмножеств X (повторяющиеся подмножества допускаются). Обычно блочная конструкция требуется для удовлетворения условий числовой регулярности. Как структура инцидентности, $X$ — это множество точек, а $F —$ $это$ множество линий, обычно называемых блоками в этом контексте (повторяющиеся блоки должны иметь различные имена, поэтому $F$ на самом деле является множеством, а не мультимножеством). Если все подмножества в $F$ имеют одинаковый размер, блочная конструкция называется равномерной . Если каждый элемент $X$ появляется в том же количестве подмножеств, блочная конструкция называется регулярной . Двойственная однородной конструкция является регулярной конструкцией и наоборот.

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

Рассмотрим блок-схему/гиперграф, представленную следующим образом: ${\begin{aligned}P&=\{1,2,3,4,5,6,7\},\\[2pt]L&=\left\{{\begin{array}{ll}\{1,2,3\},&\{1,4,5\},\\\{1,6,7\},&\{2,4,6\},\\\{2,5,7\},&\{3,4,7\},\\\{3,5,6\}\end{array}}\right\}.\end{aligned}}$

Эта структура падения называется плоскостью Фано . Как блочная конструкция она является и однородной, и регулярной.

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

Представления

Структуры инцидентности могут быть представлены многими способами. Если множества $P$ и $L$ конечны, эти представления могут компактно кодировать всю соответствующую информацию, касающуюся структуры.

Матрица инцидентности

Матрица инцидентности (конечной) структуры инцидентности — это матрица (0,1) , строки которой индексированы точками ${p i}$ , а столбцы — линиями ${l j}$ , где $ij$ -й элемент равен 1, если $p i I l j,$ и 0 в противном случае. ^[a] Матрица инцидентности не определяется однозначно, поскольку она зависит от произвольного порядка точек и линий. ^[6]

Неравномерная структура падения, изображенная выше (пример номер 2), определяется следующим образом: ${\begin{aligned}P&=\{A,B,C,D,E,P\}\\[2pt]L&=\left\{{\begin{array}{ll}l=\{C,P,E\},&m=\{P\},\\n=\{P,D\},&o=\{P,A\},\\p=\{A,B\},&q=\{P,B\}\end{array}}\right\}\end{aligned}}$

Матрица инцидентности для этой структуры имеет вид: что соответствует таблице инцидентности: ${\begin{pmatrix}0&0&0&1&1&0\\0&0&0&0&1&1\\1&0&0&0&0&0\\0&0&1&0&0&0\\1&0&0&0&0&0\\1&1&1&1&0&1\end{pmatrix}}$

Если структура инцидентности $C$ имеет матрицу инцидентности $M$ , то двойственная структура $C *$ имеет транспонированную матрицу $M$ ^T в качестве своей матрицы инцидентности (и определяется этой матрицей).

Структура инцидентности является самодвойственной, если существует такое упорядочение точек и линий, что матрица инцидентности, построенная с таким порядком, является симметричной матрицей .

При метках, указанных в примере номер 1 выше, и с точками, упорядоченными как $A, B, C, D, G, F, E$ , и линиями, упорядоченными как $l, p, n, s, r, m, q$ , плоскость Фано имеет матрицу инцидентности: Поскольку это симметричная матрица, плоскость Фано является самодвойственной структурой инцидентности. ${\begin{pmatrix}1&1&1&0&0&0&0\\1&0&0&1&1&0&0\\1&0&0&0&0&1&1\\0&1&0&1&0&1&0\\0&1&0&0&1&0&1\\0&0&1&1&0&0&1\\0&0&1&0&1&1&0\end{pmatrix}}.$

Графические изображения

Фигура инцидентности (то есть изображение структуры инцидентности) строится путем представления точек точками на плоскости и наличия некоторых визуальных средств соединения точек для соответствия линиям. ^[6] Точки могут быть размещены любым образом, нет никаких ограничений на расстояния между точками или какие-либо отношения между точками. В структуре инцидентности нет понятия точки, находящейся между двумя другими точками; порядок точек на линии не определен. Сравните это с упорядоченной геометрией , в которой есть понятие промежуточности. Те же утверждения можно сделать об изображениях линий. В частности, линии не обязательно должны быть изображены «отрезками прямых линий» (см. примеры 1, 3 и 4 выше). Как и в случае с графическим представлением графов , пересечение двух «линий» в любом месте, кроме точки, не имеет смысла с точки зрения структуры инцидентности; это всего лишь случайность представления. Эти фигуры инцидентности могут иногда напоминать графы, но они не являются графами, если структура инцидентности не является графом.

Реализуемость

Структуры инцидентности могут быть смоделированы точками и кривыми на евклидовой плоскости с обычным геометрическим значением инцидентности. Некоторые структуры инцидентности допускают представление точками и (прямыми) линиями. Структуры, которые могут быть, называются реализуемыми . Если не указано окружающее пространство, то предполагается евклидова плоскость. Плоскость Фано (пример 1 выше) не реализуема, так как для нее требуется по крайней мере одна кривая. Конфигурация Мёбиуса–Кантора (пример 4 выше) не реализуема на евклидовой плоскости, но реализуема на комплексной плоскости . ^[7] С другой стороны, примеры 2 и 5 выше реализуемы, и приведенные там цифры инцидентности демонстрируют это. Штейниц (1894) ^[8] показал, что $n 3$ -конфигурации (структуры инцидентности с $n$ точками и $n$ линиями, тремя точками на линию и тремя линиями, проходящими через каждую точку) либо реализуемы, либо требуют использования только одной кривой линии в своих представлениях. ^[9] Плоскость Фано является единственной ( $73$ ), а конфигурация Мёбиуса–Кантора является единственной ( $83$ ).

График заболеваемости (график Леви)

Каждая структура инцидентности $C$ соответствует двудольному графу , называемому графом Леви или графом инцидентности структуры. Поскольку любой двудольный граф является двуцветным, графу Леви можно придать черно-белую раскраску вершин , где черные вершины соответствуют точкам, а белые вершины соответствуют линиям $C.$ Ребра этого графа соответствуют флагам (парам инцидентная точка/линия) структуры инцидентности. Исходный граф Леви был графом инцидентности обобщенного четырехугольника второго порядка (пример 3 выше), ^[10], но этот термин был расширен HSM Coxeter ^[11] для обозначения графа инцидентности любой структуры инцидентности. ^[12]

Примеры графиков Леви

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

Конкретное представление слева графа Леви конфигурации Мёбиуса–Кантора (пример 4 выше) иллюстрирует, что поворот на $π /4$ вокруг центра (по часовой стрелке или против часовой стрелки) диаграммы меняет местами синие и красные вершины и отображает ребра в ребра. То есть существует автоморфизм смены цветов этого графа. Следовательно, структура инцидентности, известная как конфигурация Мёбиуса–Кантора, является самодвойственной.

Обобщение

Можно обобщить понятие структуры инцидентности, включив в нее более двух типов объектов. Структура с $k$ типами объектов называется структурой инцидентности ранга $k$ или геометрией ранга $k$ . ^[12] Формально они определяются как $k$ $+ 1$ кортежей $S$ $= ($ $P$ $1$ $,$ $P$ $2$ $, ...,$ $P$ $k$ $,$ $I$ $)$ с $P$ $i$ $\cap$ $P$ $j$ $= \emptyset$ и $I\subseteq \bigcup _{i<j}P_{i}\times P_{j}.$

Граф Леви для этих структур определяется как многодольный граф , вершины которого, соответствующие каждому типу, окрашены одинаково.

Смотрите также

Примечания

^ Также широко используется другой способ индексации строк по линиям, а столбцов по точкам.

Ссылки

^ Колборн и Диниц 2007, с. 702
^ аб Дембовский 1968, стр. 1–2.
^ Билиотти, Джа и Джонсон 2001, стр. 508
^ Термин «линейное пространство» также используется для обозначения векторных пространств, но это редко вызывает путаницу.
^ Мурхаус 2014, стр. 5
^ ab Бет, Юнгникель и Ленц 1986, стр. 17
^ Пизански и Серватиус 2013, с. 222
^ Э. Стейниц (1894), Über die Construction der Configurationen $n 3$ , Диссертация, Бреслау
^ Гропп, Харальд (1997), «Конфигурации и их реализации», Дискретная математика , 174 : 137–151, doi : 10.1016/s0012-365x(96)00327-5
^ Леви, Ф. В. (1942), Конечные геометрические системы , Калькутта: Университет Калькутты, MR 0006834
^ Коксетер, HSM (1950), «Самодвойственные конфигурации и регулярные графы», Бюллетень Американского математического общества , 56 : 413–455, doi : 10.1090/s0002-9904-1950-09407-5
^ ab Pisanski & Servatius 2013, с. 158

Библиография

Бет, Томас; Юнгникель, Дитер; Ленц, Ханфрид (1986), Теория дизайна , Cambridge University Press, ISBN 3-411-01675-2
Билиотти, Мауро; Джа, Викрам; Джонсон, Норман Л. (2001), Основы плоскостей перемещения , Марсель Деккер , ISBN 0-8247-0609-9
Колборн, Чарльз Дж.; Диниц, Джеффри Х. (2007), Справочник комбинаторных конструкций (2-е изд.), Бока-Ратон: Chapman & Hall/CRC, ISBN 1-58488-506-8
Дембовский, Питер (1968), Конечные геометрии , Ergebnisse der Mathematik und ihrer Grenzgebiete , Band 44, Берлин, Нью-Йорк: Springer-Verlag , ISBN 3-540-61786-8, МР 0233275
Мурхаус, Г. Эрик (2014). «Геометрия инцидентности» (PDF) – через Джона Баеза из Калифорнийского университета в Риверсайде .
Писански, Томаж; Серватиус, Бригитта (2013), Конфигурации с графической точки зрения , Springer, doi :10.1007/978-0-8176-8364-1, ISBN 978-0-8176-8363-4

Дальнейшее чтение

CRC Press (2000). Справочник по дискретной и комбинаторной математике , (Глава 12.2), ISBN 0-8493-0149-1
Гарольд Л. Дорварт (1966) Геометрия инцидентности , Prentice Hall