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

У математиці структурою інцидентності називається трійка

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

де P — це множина «точок», L — множина «ліній», а $I\subseteq P\times L$ — відношення інцидентності. Елементи $I$ називаються прапорами. Якщо

$(p,l)\in I$,

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

Структури інцидентності узагальнюють площини (такі як афінні, проєктивні і площини Мебіуса), як можна бачити з аксіоматичних визначень цих площин. Структури інцидентності також узагальнюють геометричні структури вищої розмірності; при цьому скінченні структури іноді називають скінченними геометріями.

Порівняння з іншими структурами

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

У структурі інцидентності немає поняття точки, що лежить між двома іншими точками. Порядок точок на лінії не визначено. Порівняйте з упорядкованою геометрією, в якій є відношення «лежить між».

Двоїста структура

Якщо обміняти ролі «точок» і «ліній» у структурі інцидентності

C = (P, L, I), вийде двоїста структура

C* = (L, P, I*), де I* — бінарне відношення, обернене до I. Зрозуміло, що

C** = C.

Ця операція є абстрактною версією проєктивної двоїстості.

Структура C, ізоморфна своїй двоїстій структурі C* називається самодвоїстою.

Відповідність гіперграфам

Сім точок є елементами семи ліній поверхні Фано

Кожен гіперграф або систему множин можна розглядати як структуру інцидентності, в якій універсальна множина відіграє роль «точок», відповідна система множин відіграє роль «ліній», а відношення інціденції — це належність «∈». Навпаки, будь-яку структуру інціденцій можна розглядати як гіперграф.

Приклад: поверхня Фано

Зокрема, нехай

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

Відповідна структура інцидентності називається поверхнею Фано.

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

Геометричне подання

Структуру інцидентності можна моделювати за допомогою точок і кривих у евклідовій геометрії зі стандартним геометричним включенням як відношенням інцидентності. Деякі структури інцидентності допускають подання за допомогою точок і прямих, однак, наприклад, поверхня Фано не має такого подання.

Граф Леві структури інцидентності

Граф Хівуда з мітками

Будь-яка структура інцидентності 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