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

Поделись знанием:
Перейти к: навигация, поиск

В математике структурой инцидентности называется тройка

<math>C=(P,L,I).</math>

где P — это множество «точек», L — множество «линий», а <math>I \subseteq P \times L</math> — отношение инцидентности[en]. Элементы <math>I</math> называются флагами. Если

<math>(p,l) \in I</math>,

мы говорим, что точка p «лежит на» линии <math>l</math>. Можно представить L как множество подмножеств P, и инцидентностью I будет включение (<math>(p,l) \in I</math> в том и только в том случае, когда <math>p \in l</math>), но можно думать более абстрактно.

Структуры инцидентности обобщают плоскости (такие как аффинные[en], проективные и плоскости Мёбиуса), как можно видеть из аксиоматических определений этих плоскостей. Структуры инцидентности также обобщают геометрические структуры более высокой размерности; при этом конечные структуры иногда называют конечными геометриями.





Сравнение с другими структурами

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

В структуре инцидентности нет понятия точки, лежащей между двумя другими точками. Порядок точек на линии не определён. Сравните с упорядоченной геометрией[en], которая имеет отношение «лежит между».

Двойственная структура

Если обменять роли «точек» и «линий» в структуре инцидентности

C = (P,L,I),

получится двойственная структура

C* = (L,P,I*),

где I* — бинарное отношение, обратное[en] к I. Ясно, что

C** = C.

Эта операция является абстрактной версией проективной двойственности.

Структура C, изоморфная своей двойственной структуре C* называется самодвойственной.

Соответствие гиперграфам

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

Пример: поверхность Фано

В частности, пусть

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

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

Геометрическое представление

Структуру инцидентности можно моделировать с помощью точек и кривых в евклидовой геометрии со стандартным геометрическим включением в качестве отношения инцидентности. Некоторые структуры инцидентности допускают представление с помощью точек и прямых, однако, например, поверхность Фано не имеет такого представления.

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

Любая структура инцидентности 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 .

Отрывок, характеризующий Структура инцидентности

Один из игроков сказал, что, он надеется, ему можно поверить.
– Поверить можно, но боюсь спутаться; прошу класть деньги на карты, – отвечал Долохов. – Ты не стесняйся, мы с тобой сочтемся, – прибавил он Ростову.
Игра продолжалась: лакей, не переставая, разносил шампанское.
Все карты Ростова бились, и на него было написано до 800 т рублей. Он надписал было над одной картой 800 т рублей, но в то время, как ему подавали шампанское, он раздумал и написал опять обыкновенный куш, двадцать рублей.
– Оставь, – сказал Долохов, хотя он, казалось, и не смотрел на Ростова, – скорее отыграешься. Другим даю, а тебе бью. Или ты меня боишься? – повторил он.
Ростов повиновался, оставил написанные 800 и поставил семерку червей с оторванным уголком, которую он поднял с земли. Он хорошо ее после помнил. Он поставил семерку червей, надписав над ней отломанным мелком 800, круглыми, прямыми цифрами; выпил поданный стакан согревшегося шампанского, улыбнулся на слова Долохова, и с замиранием сердца ожидая семерки, стал смотреть на руки Долохова, державшего колоду. Выигрыш или проигрыш этой семерки червей означал многое для Ростова. В Воскресенье на прошлой неделе граф Илья Андреич дал своему сыну 2 000 рублей, и он, никогда не любивший говорить о денежных затруднениях, сказал ему, что деньги эти были последние до мая, и что потому он просил сына быть на этот раз поэкономнее. Николай сказал, что ему и это слишком много, и что он дает честное слово не брать больше денег до весны. Теперь из этих денег оставалось 1 200 рублей. Стало быть, семерка червей означала не только проигрыш 1 600 рублей, но и необходимость изменения данному слову. Он с замиранием сердца смотрел на руки Долохова и думал: «Ну, скорей, дай мне эту карту, и я беру фуражку, уезжаю домой ужинать с Денисовым, Наташей и Соней, и уж верно никогда в руках моих не будет карты». В эту минуту домашняя жизнь его, шуточки с Петей, разговоры с Соней, дуэты с Наташей, пикет с отцом и даже спокойная постель в Поварском доме, с такою силою, ясностью и прелестью представились ему, как будто всё это было давно прошедшее, потерянное и неоцененное счастье. Он не мог допустить, чтобы глупая случайность, заставив семерку лечь прежде на право, чем на лево, могла бы лишить его всего этого вновь понятого, вновь освещенного счастья и повергнуть его в пучину еще неиспытанного и неопределенного несчастия. Это не могло быть, но он всё таки ожидал с замиранием движения рук Долохова. Ширококостые, красноватые руки эти с волосами, видневшимися из под рубашки, положили колоду карт, и взялись за подаваемый стакан и трубку.
– Так ты не боишься со мной играть? – повторил Долохов, и, как будто для того, чтобы рассказать веселую историю, он положил карты, опрокинулся на спинку стула и медлительно с улыбкой стал рассказывать:
– Да, господа, мне говорили, что в Москве распущен слух, будто я шулер, поэтому советую вам быть со мной осторожнее.
– Ну, мечи же! – сказал Ростов.
– Ох, московские тетушки! – сказал Долохов и с улыбкой взялся за карты.
– Ааах! – чуть не крикнул Ростов, поднимая обе руки к волосам. Семерка, которая была нужна ему, уже лежала вверху, первой картой в колоде. Он проиграл больше того, что мог заплатить.
– Однако ты не зарывайся, – сказал Долохов, мельком взглянув на Ростова, и продолжая метать.


Через полтора часа времени большинство игроков уже шутя смотрели на свою собственную игру.
Вся игра сосредоточилась на одном Ростове. Вместо тысячи шестисот рублей за ним была записана длинная колонна цифр, которую он считал до десятой тысячи, но которая теперь, как он смутно предполагал, возвысилась уже до пятнадцати тысяч. В сущности запись уже превышала двадцать тысяч рублей. Долохов уже не слушал и не рассказывал историй; он следил за каждым движением рук Ростова и бегло оглядывал изредка свою запись за ним. Он решил продолжать игру до тех пор, пока запись эта не возрастет до сорока трех тысяч. Число это было им выбрано потому, что сорок три составляло сумму сложенных его годов с годами Сони. Ростов, опершись головою на обе руки, сидел перед исписанным, залитым вином, заваленным картами столом. Одно мучительное впечатление не оставляло его: эти ширококостые, красноватые руки с волосами, видневшимися из под рубашки, эти руки, которые он любил и ненавидел, держали его в своей власти.
«Шестьсот рублей, туз, угол, девятка… отыграться невозможно!… И как бы весело было дома… Валет на пе… это не может быть!… И зачем же он это делает со мной?…» думал и вспоминал Ростов. Иногда он ставил большую карту; но Долохов отказывался бить её, и сам назначал куш. Николай покорялся ему, и то молился Богу, как он молился на поле сражения на Амштетенском мосту; то загадывал, что та карта, которая первая попадется ему в руку из кучи изогнутых карт под столом, та спасет его; то рассчитывал, сколько было шнурков на его куртке и с столькими же очками карту пытался ставить на весь проигрыш, то за помощью оглядывался на других играющих, то вглядывался в холодное теперь лицо Долохова, и старался проникнуть, что в нем делалось.