Структура инцидентности
Структура инцидентности — в математике тройка
- где P — это множество «точек», L — множество «линий», а — отношение инцидентности. Элементы называются флагами. Если
- , мы говорим, что точка p «лежит на» линии . Можно представить L как множество подмножеств P, и инцидентностью I будет включение ( в том и только в том случае, когда ), но можно думать более абстрактно.
Структуры инцидентности обобщают плоскости (такие как [англ.], проективные и плоскости Мёбиуса), как можно видеть из аксиоматических определений этих плоскостей. Структуры инцидентности также обобщают геометрические структуры более высокой размерности; при этом конечные структуры иногда называют конечными геометриями.
Сравнение с другими структурами
Изображение структуры инцидентности может выглядеть как граф, но в графах ребро имеет только две конечные точки, в то время как линия в структуре инцидентности может быть инцидентна более чем двум точкам. Таким образом, структуры инцидентности являются гиперграфами.
В структуре инцидентности нет понятия точки, лежащей между двумя другими точками. Порядок точек на линии не определён. Сравните с [англ.], которая имеет отношение «лежит между».
Двойственная структура
Если обменять роли «точек» и «линий» в структуре инцидентности
- 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, ISBN 0-8247-0609-9 .
- Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1986), Design Theory, Cambridge University Press, ISBN 3-411-01675-2
- Biliotti, Mauro; Jha, Vikram; Johnson, Norman L. (2001), Foundations of Translation Planes, , ISBN 0-8247-0609-9
- Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd ed.), Boca Raton: Chapman & Hall/ CRC, ISBN 1-58488-506-8
- Dembowski, Peter (1968), Finite geometries, , Band 44, Berlin, New York: Springer-Verlag, ISBN 3-540-61786-8, MR 0233275
- G. Eric Moorhouse (2014) Incidence Geometry via John Baez at
- Pisanski, Tomaž; (2013), Configurations from a Graphical Viewpoint, Springer, doi:10.1007/978-0-8176-8364-1, ISBN 978-0-8176-8363-4
Википедия, чтение, книга, библиотека, поиск, нажмите, истории, книги, статьи, wikipedia, учить, информация, история, скачать, скачать бесплатно, mp3, видео, mp4, 3gp, jpg, jpeg, gif, png, картинка, музыка, песня, фильм, игра, игры, мобильный, телефон, Android, iOS, apple, мобильный телефон, Samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Сеть, компьютер, Информация о Структура инцидентности, Что такое Структура инцидентности? Что означает Структура инцидентности?
Struktura incidentnosti v matematike trojka C P L I displaystyle C P L I gde P eto mnozhestvo tochek L mnozhestvo linij a I P L displaystyle I subseteq P times L otnoshenie incidentnosti Elementy I displaystyle I nazyvayutsya flagami Esli p l I displaystyle p l in I my govorim chto tochka p lezhit na linii l displaystyle l Mozhno predstavit L kak mnozhestvo podmnozhestv P i incidentnostyu I budet vklyuchenie p l I displaystyle p l in I v tom i tolko v tom sluchae kogda p l displaystyle p in l no mozhno dumat bolee abstraktno Struktury incidentnosti obobshayut ploskosti takie kak angl proektivnye i ploskosti Myobiusa kak mozhno videt iz aksiomaticheskih opredelenij etih ploskostej Struktury incidentnosti takzhe obobshayut geometricheskie struktury bolee vysokoj razmernosti pri etom konechnye struktury inogda nazyvayut konechnymi geometriyami Sravnenie s drugimi strukturamiIzobrazhenie struktury incidentnosti mozhet vyglyadet kak graf no v grafah rebro imeet tolko dve konechnye tochki v to vremya kak liniya v strukture incidentnosti mozhet byt incidentna bolee chem dvum tochkam Takim obrazom struktury incidentnosti yavlyayutsya gipergrafami V strukture incidentnosti net ponyatiya tochki lezhashej mezhdu dvumya drugimi tochkami Poryadok tochek na linii ne opredelyon Sravnite s angl kotoraya imeet otnoshenie lezhit mezhdu Dvojstvennaya strukturaEsli obmenyat roli tochek i linij v strukture incidentnosti C P L I poluchitsya dvojstvennaya struktura C L P I gde I binarnoe otnoshenie obratnoe k I Yasno chto C C Eta operaciya yavlyaetsya abstraktnoj versiej proektivnoj dvojstvennosti Struktura C izomorfnaya svoej dvojstvennoj strukture C nazyvaetsya samodvojstvennoj Sootvetstvie gipergrafamSem tochek yavlyayutsya elementami semi linij ploskosti Fano Kazhdyj gipergraf ili sistemu mnozhestv mozhno rassmatrivat kak strukturu incidentnosti v kotoroj universalnoe mnozhestvo igraet rol tochek sootvetstvuyushaya sistema mnozhestv igraet rol linij a otnoshenie incidencii eto prinadlezhnost Obratno lyubuyu strukturu incidencij mozhno rassmatrivat kak gipergraf Primer ploskost Fano V chastnosti pust 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 Sootvetstvuyushaya struktura incidentnosti nazyvaetsya ploskostyu Fano Linii v tochnosti podmnozhestva tochek sostoyashie iz tryoh tochek metki kotoryh dopolnyayutsya do nulya s pomoshyu nim summy Geometricheskoe predstavlenieStrukturu incidentnosti mozhno modelirovat s pomoshyu tochek i krivyh v evklidovoj geometrii so standartnym geometricheskim vklyucheniem v kachestve otnosheniya incidentnosti Nekotorye struktury incidentnosti dopuskayut predstavlenie s pomoshyu tochek i pryamyh odnako naprimer poverhnost Fano ne imeet takogo predstavleniya Graf Levi struktury incidentnostiGraf Hivuda s metkami Lyubaya struktura incidentnosti C sootvetstvuet dvudolnomu grafu nazyvaemomu grafom Levi ili grafom incidentnosti struktury Poskolku lyuboj dvudolnyj graf mozhno raskrasit v dva cveta vershiny grafa Levi mozhno raskrasit v belye i chyornye cveta gde chyornye vershiny sootvetstvuyut tochkam i belye vershiny sootvetstvuyut liniyam C Ryobra etogo grafa sootvetstvuyut flagam incidentnym param tochka liniya struktury incidentnosti Primer Graf Hivuda Graf Levi ploskosti Fano eto graf Hivuda Poskolku graf Hivuda svyaznyj i vershinno tranzitivnyj sushestvuet avtomorfizm takoj naprimer kak otrazhenie otnositelno vertikalnoj osi na risunke sprava obmenivayushij belye i chyornye vershiny Otsyuda sleduet chto ploskost Fano samodvojstvenna Sm takzheKonechnaya geometriya Binarnoe otnoshenie Kombinatornaya shema Matrica incidentnosti Incidentnost geometriya Konfiguraciya Pappa Proektivnaya konfiguraciya Mnogodolnyj grafSsylkiCRC 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 Beth Thomas Jungnickel Dieter Lenz Hanfried 1986 Design Theory Cambridge University Press ISBN 3 411 01675 2 Biliotti Mauro Jha Vikram Johnson Norman L 2001 Foundations of Translation Planes ISBN 0 8247 0609 9 Colbourn Charles J Dinitz Jeffrey H 2007 Handbook of Combinatorial Designs 2nd ed Boca Raton Chapman amp Hall CRC ISBN 1 58488 506 8 Dembowski Peter 1968 Finite geometries Band 44 Berlin New York Springer Verlag ISBN 3 540 61786 8 MR 0233275 G Eric Moorhouse 2014 Incidence Geometry via John Baez at Pisanski Tomaz 2013 Configurations from a Graphical Viewpoint Springer doi 10 1007 978 0 8176 8364 1 ISBN 978 0 8176 8363 4
