Математическая энциклопедия - инцидентности система

совокупность двух множеств Аи с отношением инцидентности I между их элементами, к-рое записывается как аIВ для в этом случае говорят, что элемент аинцидентен элементу Л, или Винцидентен а. Понятие "И. с." вводится с целью использования геометрич. языка при рассмотрении общих комбинаторных проблем существования и построения; при этом отношению инцидентности предписываются нек-рые свойства, приводящие к тем или иным комбинаторным конфигурациям.

Примером используемых в комбинаторике И. с. служат (конечные) геометрии: элементы (конечных) множеств Аи наз. соответственно точками и прямыми, а отношению I предписываются свойства, обычные в теории проективных или аффинных геометрий. Другим характерным примером И. с. являются блок-схемы, к-рые получаются, если потребовать, чтобы: 1) каждый элемент был инцидентен в точности r элементам из 2) каждый элемент был инцидентен в точности k элементам из А; 3) каждая пара {а, а' } различных элементов из Абыла инцидентна в точности l элементам из Часто в качестве берется нек-рое множество подмножеств множества А, тогда аIВ есть не что иное, как

И. с. и наз. изоморфны м и, если существуют такие взаимно однозначные соответствия a :. и b : что

Если А= {а, а2, ...} и = {В 1, В 2, ...} конечные множества, то удобно описывать свойства И. с. 5 с помощью матрицы инцидентности ||aij||, где aij=1, когда и aij=0 в противном случае; матрица ||aij|| определяет И. с. Sс точностью до изоморфизма.

Лит.:[1] Холл М., Комбинаторика, пер. с англ., М., 1970; [2] Dembowski P., Finite Geometries, В.-N.Y., 1968.

В. Е. Тараканов.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985