У математиці структурою інцидентності називається трійка
де P — це множина «точок», L — множина «ліній», а — відношення інцидентності. Елементи називаються прапорами. Якщо
- ,
ми кажемо, що точка p «лежить на» лінії . Можна уявити L як множину підмножин P, і інцидентністю I буде включення ( тоді і тільки тоді, коли ), але можна думати більш абстрактно.
Структури інцидентності узагальнюють площини (такі як [en], проєктивні і площини Мебіуса), як можна бачити з аксіоматичних визначень цих площин. Структури інцидентності також узагальнюють геометричні структури вищої розмірності; при цьому скінченні структури іноді називають скінченними геометріями.
Порівняння з іншими структурами
Зображення структури інцидентності може мати вигляд графу, але в графах ребро має тільки дві кінцеві точки, тоді як лінія в структурі інцидентності може бути інцидентною більш ніж двом точкам. Таким чином, структури інцидентності є гіперграфами.
У структурі інцидентності немає поняття точки, що лежить між двома іншими точками. Порядок точок на лінії не визначено. Порівняйте з [en], в якій є відношення «лежить між».
Двоїста структура
Якщо обміняти ролі «точок» і «ліній» у структурі інцидентності
- 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}}.
Відповідна структура інцидентності називається поверхнею Фано.
Лінії — точно підмножини точок, що складаються з трьох точок, мітки яких доповнюються до нуля [en].
Геометричне подання
Структуру інцидентності можна моделювати за допомогою точок і кривих у евклідовій геометрії зі стандартним геометричним включенням як відношенням інцидентності. Деякі структури інцидентності допускають подання за допомогою точок і прямих, однак, наприклад, поверхня Фано не має такого подання.
Граф Леві структури інцидентності
Будь-яка структура інцидентності C відповідає двочастковому графу, званому графом Леві, або графом інцидентності структури. Оскільки будь-який двочастковий граф можна розфарбувати в два кольори, вершини графу Леві можна розфарбувати в білий і чорний кольори, де чорні вершини відповідають точкам і білі вершини відповідають лініям C. Ребра цього графу відповідають прапорам (інцидентним парам точка/лінія) структури інцидентності.
Приклад: граф Хівуда
Граф Леві поверхні Фано — це граф Хівуда. Оскільки граф Хівуда — зв'язний і вершинно-транзитивний, існує автоморфізм (такий, наприклад, як відбиття відносно вертикальної осі на малюнку справа), який обмінює білі й чорні вершини. Звідси випливає, що поверхня Фано самодвоїста.
Див. також
Посилання
- CRC Press (2000). Handbook of discrete and combinatorial mathematics, (Chapter 12.2),
- Mauro Biliotti, Vikram Jha, Norman L. Johnson (2001) Foundations of Translation Planes, Appendix V: Incidence Structures and Parallelisms, pp. 507-12,
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U matematici strukturoyu incidentnosti nazivayetsya trijka C P L I displaystyle C P L I de P ce mnozhina tochok L mnozhina linij a I P L displaystyle I subseteq P times L vidnoshennya incidentnosti Elementi I displaystyle I nazivayutsya praporami Yaksho p l I displaystyle p l in I mi kazhemo sho tochka p lezhit na liniyi l displaystyle l Mozhna uyaviti L yak mnozhinu pidmnozhin P i incidentnistyu I bude vklyuchennya p l I displaystyle p l in I todi i tilki todi koli p l displaystyle p in l ale mozhna dumati bilsh abstraktno Strukturi incidentnosti uzagalnyuyut ploshini taki yak en proyektivni i ploshini Mebiusa yak mozhna bachiti z aksiomatichnih viznachen cih ploshin Strukturi incidentnosti takozh uzagalnyuyut geometrichni strukturi vishoyi rozmirnosti pri comu skinchenni strukturi inodi nazivayut skinchennimi geometriyami Porivnyannya z inshimi strukturamiZobrazhennya strukturi incidentnosti mozhe mati viglyad grafu ale v grafah rebro maye tilki dvi kincevi tochki todi yak liniya v strukturi incidentnosti mozhe buti incidentnoyu bilsh nizh dvom tochkam Takim chinom strukturi incidentnosti ye gipergrafami U strukturi incidentnosti nemaye ponyattya tochki sho lezhit mizh dvoma inshimi tochkami Poryadok tochok na liniyi ne viznacheno Porivnyajte z en v yakij ye vidnoshennya lezhit mizh Dvoyista strukturaDokladnishe Dvoyistist proyektivna geometriya Yaksho obminyati roli tochok i linij u strukturi incidentnosti C P L I vijde dvoyista struktura C L P I de I binarne vidnoshennya obernene do I Zrozumilo sho C C Cya operaciya ye abstraktnoyu versiyeyu proyektivnoyi dvoyistosti Struktura C izomorfna svoyij dvoyistij strukturi C nazivayetsya samodvoyistoyu Vidpovidnist gipergrafamSim tochok ye elementami semi linij poverhni Fano Kozhen gipergraf abo sistemu mnozhin mozhna rozglyadati yak strukturu incidentnosti v yakij universalna mnozhina vidigraye rol tochok vidpovidna sistema mnozhin vidigraye rol linij a vidnoshennya incidenciyi ce nalezhnist Navpaki bud yaku strukturu incidencij mozhna rozglyadati yak gipergraf Priklad poverhnya Fano Zokrema nehaj 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 Vidpovidna struktura incidentnosti nazivayetsya poverhneyu Fano Liniyi tochno pidmnozhini tochok sho skladayutsya z troh tochok mitki yakih dopovnyuyutsya do nulya en Geometrichne podannyaStrukturu incidentnosti mozhna modelyuvati za dopomogoyu tochok i krivih u evklidovij geometriyi zi standartnim geometrichnim vklyuchennyam yak vidnoshennyam incidentnosti Deyaki strukturi incidentnosti dopuskayut podannya za dopomogoyu tochok i pryamih odnak napriklad poverhnya Fano ne maye takogo podannya Graf Levi strukturi incidentnostiGraf Hivuda z mitkami Bud yaka struktura incidentnosti C vidpovidaye dvochastkovomu grafu zvanomu grafom Levi abo grafom incidentnosti strukturi Oskilki bud yakij dvochastkovij graf mozhna rozfarbuvati v dva kolori vershini grafu Levi mozhna rozfarbuvati v bilij i chornij kolori de chorni vershini vidpovidayut tochkam i bili vershini vidpovidayut liniyam C Rebra cogo grafu vidpovidayut praporam incidentnim param tochka liniya strukturi incidentnosti Priklad graf Hivuda Graf Levi poverhni Fano ce graf Hivuda Oskilki graf Hivuda zv yaznij i vershinno tranzitivnij isnuye avtomorfizm takij napriklad yak vidbittya vidnosno vertikalnoyi osi na malyunku sprava yakij obminyuye bili j chorni vershini Zvidsi viplivaye sho poverhnya Fano samodvoyista Div takozhSkinchenna geometriya Binarne vidnoshennya Kombinatorna shema Matricya incidentnosti Incidentnist geometriya Konfiguraciya Pappa Proyektivna konfiguraciya Bagatochastkovij graf Chastkova geometriya Majzhe mnogokutnikPosilannyaCRC 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 ISBN 0 8247 0609 9