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

Примеры структур заболеваемости:
Пример 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{ is an eigenvector of matrix }}M\}.

Этот пример также показывает, что, хотя используется геометрический язык точек и линий, типы объектов не обязательно должны быть этими геометрическими объектами.

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

Некоторые примеры структур заболеваемости

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

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

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

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

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

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

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

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

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

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

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

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

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

C=(P,L,I)

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

C^{*}=(L,P,I^{*})

где

я *

является отношением I

.

обратным Из определения сразу следует, что:

C^{**}=C

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

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

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

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

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

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

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

конструкция представляет собой набор $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}}

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

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

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

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

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

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

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

$я$	$л$	$м$	$н$	$тот$	$п$	$д$
$А$	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

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

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

С метками, как указано в примере № 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
↑ Перейти обратно: Перейти обратно: ^а ^б Бет, Юнгникель и Ленц, 1986 , с. 17
^ Пизански и Серватиус 2013 , с. 222
^ Э. Стейниц (1894), О построении конфигураций $№ 3$ , диссертация, Бреслау
^ Гропп, Харальд (1997), «Конфигурации и их реализации», Дискретная математика , 174 : 137–151, doi : 10.1016/s0012-365x(96)00327-5
^ Леви, FW (1942), Конечные геометрические системы , Калькутта: Калькуттский университет, MR 0006834
^ Коксетер, HSM (1950), «Самодвойственные конфигурации и регулярные графы», Бюллетень Американского математического общества , 56 : 413–455, doi : 10.1090/s0002-9904-1950-09407-5
↑ Перейти обратно: Перейти обратно: ^а ^б Пизанский и Серватиус 2013 , с. 158

Библиография [ править ]

Бет, Томас; Юнгникель, Дитер; Ленц, Ханфрид (1986), Теория дизайна , Издательство Кембриджского университета, ISBN 3-411-01675-2
Билиотти, Мауро; Джа, Викрам; Джонсон, Норман Л. (2001), Основы плоскостей перемещения , Марсель Деккер , ISBN 0-8247-0609-9
Колборн, Чарльз Дж.; Диниц, Джеффри Х. (2007), Справочник по комбинаторным планам (2-е изд.), Бока-Ратон: Chapman & Hall/CRC, ISBN 1-58488-506-8
Дембовский, Питер (1968), Конечная геометрия , результаты математики и ее пограничные области , Том 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

Дальнейшее чтение [ править ]

ЦРК Пресс (2000). Справочник по дискретной и комбинаторной математике , (глава 12.2), ISBN 0-8493-0149-1
Гарольд Л. Дорварт (1966) Геометрия падения , Прентис Холл

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

[1] Колборн и Диниц 2007 , с. 702

[Demb1-2] Перейти обратно: Перейти обратно: ^а ^б Дембовский 1968 , стр. 1–2.

[3] Билиотти, Джа и Джонсон 2001 , стр. 508

[4] Термин «линейное пространство» также используется для обозначения векторных пространств, но это редко вызывает путаницу.

[5] Мурхаус 2014 , с. 5

[Beth17-7] Перейти обратно: Перейти обратно: ^а ^б Бет, Юнгникель и Ленц, 1986 , с. 17

[8] Пизански и Серватиус 2013 , с. 222

[9] Э. Стейниц (1894), О построении конфигураций $№ 3$ , диссертация, Бреслау

[10] Гропп, Харальд (1997), «Конфигурации и их реализации», Дискретная математика , 174 : 137–151, doi : 10.1016/s0012-365x(96)00327-5

[11] Леви, FW (1942), Конечные геометрические системы , Калькутта: Калькуттский университет, MR 0006834

[12] Коксетер, HSM (1950), «Самодвойственные конфигурации и регулярные графы», Бюллетень Американского математического общества , 56 : 413–455, doi : 10.1090/s0002-9904-1950-09407-5

[Pisanski158-13] Перейти обратно: Перейти обратно: ^а ^б Пизанский и Серватиус 2013 , с. 158

[1]

[2]

[3]

[4]

[5]

[а]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

v т и Структуры заболеваемости
Представительство	Матрица заболеваемости График заболеваемости
Поля	Комбинаторика Блочный дизайн Система Штейнера Геометрия Заболеваемость Проекционная плоскость Теория графов Гиперграф Статистика Блокировка
Конфигурации	Полный четырехугольник Самолет Фано Конфигурация Мёбиуса – Кантора Конфигурация Паппуса Конфигурация Гессена Конфигурация Дезарга Конфигурация Рейе Шлефли дабл шесть Конфигурация Кремона – Ричмонд Конфигурация печали Конфигурация Грюнбаума – Ригби Конфигурация Кляйна Двойной
Теоремы	Теорема Сильвестра–Кулда Теорема де Брейна–Эрдеша Теорема Семереди – Троттера Теорема Бека Теорема Брука–Райзера–Чоулы
Приложения	Планирование экспериментов Проблема школьницы Киркмана