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

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

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

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

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

Структура заболеваемости является тройка ( Р , Л , я ) , где Р представляет собой набор, элементы которого называются точки , L представляет собой определенный набор, элементы которого называются линии , и я ⊆ P × L является частота отношение . Элементы I называются флагами. Если ( p , l ) находится в I, то можно сказать, что точка p "лежит на" прямой l или что прямая l«проходит через» точку р . Более «симметричны» терминологию, чтобы отразить симметричный характер этой связи, является то , что « р является падающей с л » или что « л является случай с р » и использует обозначения р I л синонимично с ( р , л ) ∈ I . ^[2]

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

Примеры [ править ]

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

Графики [ править ]

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

Линейные пробелы [ править ]

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

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

Если первая аксиома выше заменяется более сильной:

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

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

Сети [ править ]

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

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

Если поменять местами «точки» и «линии» в

С = ( P , L , I )

получаем дуальную структуру ,

C ^∗ = ( L , P , I ^∗ ) ,

где I ^* есть обратное соотношение из I . Непосредственно из определения следует, что:

C ^** = C .

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

Структура C , изоморфная своей двойственной C ^∗ , называется самодвойственной . Плоскость Фано выше представляет собой самодуальную структуру падения.

Другая терминология [ править ]

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

Гиперграфы [ править ]

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

Блочные конструкции [ править ]

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

Пример: самолет Фано [ править ]

Рассмотрим блочный дизайн / гиперграф, заданный следующим образом:

${\ Displaystyle P = \ влево \ {1,2,3,4,5,6,7 \ вправо \}}$,

${\ Displaystyle L = \ left \ {\ {1,2,3 \}, \ {1,4,5 \}, \ {1,6,7 \}, \ {2,4,6 \}, \ {2,5,7 \}, \ {3,4,7 \}, \ {3,5,6 \} \ right \}}$.

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

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

Представления [ править ]

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

Матрица заболеваемости [ править ]

Матрица инцидентности из (конечной) падения структуры является (0,1) матрицей , которая имеет свои ряды индексированных точек { р _я } и столбцы , индексированных по линиям { л _J } , где Ij -й элементом является 1 , если p _i I l _j и 0 в противном случае. ^[6] Матрица инцидентности не определяется однозначно, поскольку она зависит от произвольного порядка точек и линий. ^[7]

Неоднородная структура заболеваемости, изображенная выше (пример номер 2), определяется следующим образом:

P = { A , B , C , D , E , P }

L = {  l = { C , P , E }, m = { P }, n = { P , D }, o = { P , A }, p = { A , B }, q = { P , B } } .

Матрица инцидентности для этой структуры:

${\ displaystyle \ left ({\ begin {matrix} 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 & 1 & 0 & 1 \ right end {matrix}}}$

что соответствует таблице заболеваемости:

я	л	м	п	о	п	q
А	0	0	0	1	1	0
B	0	0	0	0	1	1
C	1	0	0	0	0	0
D	0	0	1	0	0	0
E	1	0	0	0	0	0
п	1	1	1	1	0	1

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

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

С метками, указанными в примере 1 выше, и с точками в порядке A , B , C , D , G , F , E и линиями в порядке l , p , n , s , r , m , q , плоскость Фано имеет угол падения матрица:

${\displaystyle \left({\begin{matrix}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{matrix}}\right).}$

Поскольку это симметричная матрица, плоскость Фано представляет собой самодуальную структуру падения.

Графические изображения [ править ]

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

Реализуемость [ править ]

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

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

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

Примеры графов Леви [ править ]

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

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

Обобщение [ править ]

Можно обобщить понятие структуры инцидентности, чтобы включить более двух типов объектов. Структура с k типами объектов называется структурой инцидентности ранга k или геометрией ранга k . ^[13] Формально они определены как k + 1 набор S = ( P ₁ , P ₂ , ..., P _k , I ), где P _i ∩ P _j = ∅ и

${\displaystyle I\subseteq \bigcup _{i<j}P_{i}\times P_{j}.}$

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

См. Также [ править ]

• Заболеваемость (геометрия)
• Геометрия падения
• Проективная конфигурация

Заметки [ править ]

Ссылки [ править ]

• Бет, Томас; Юнгникель, Дитер; Ленц, Ханфрид (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, MR  0233275
• Г. Эрик Мурхаус (2014) Геометрия заболеваемости через Джона Баэза в Калифорнийском университете, Риверсайд
• Писанский, Томаж; Серватиус, Бриджит (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) Геометрия падения , Прентис Холл