Инцидентности система

- совокупность [img: http://localhost:8080/file/021020-41.jpg] двух множеств Аи [img: http://localhost:8080/file/021020-42.jpg] с отношением инцидентности I между их элементами, к-рое записывается как аIВ для [img: http://localhost:8080/file/021020-43.jpg] в этом случае говорят, что элемент аинцидентен элементу Л, или Винцидентен а. Понятие "И. с." вводится с целью использования геометрич. языка при рассмотрении общих комбинаторных проблем существования и построения; при этом отношению инцидентности предписываются нек-рые свойства, приводящие к тем или иным комбинаторным конфигурациям. Примером используемых в комбинаторике И. с. служат (конечные) геометрии: элементы (конечных) множеств Аи [img: http://localhost:8080/file/021020-44.jpg] наз. соответственно точками и прямыми, а отношению I предписываются свойства, обычные в теории проективных или аффинных геометрий. Другим характерным примером И. с. являются блок-схемы, к-рые получаются, если потребовать, чтобы: 1) каждый элемент [img: http://localhost:8080/file/021020-45.jpg] был инцидентен в точности r элементам из [img: http://localhost:8080/file/021020-46.jpg] 2) каждый элемент [img: http://localhost:8080/file/021020-47.jpg] был инцидентен в точности k элементам из А; 3) каждая пара {а, а' } различных элементов из Абыла инцидентна в точности l элементам из [img: http://localhost:8080/file/021020-48.jpg] Часто в качестве [img: http://localhost:8080/file/021020-49.jpg] берется нек-рое множество подмножеств множества А, тогда аIВ есть не что иное, как [img: http://localhost:8080/file/021020-50.jpg] И. с. [img: http://localhost:8080/file/021020-51.jpg] и [img: http://localhost:8080/file/021020-52.jpg] наз. изоморфны м и, если существуют такие взаимно однозначные соответствия a: [img: http://localhost:8080/file/021020-53.jpg]. и b: [img: http://localhost:8080/file/021020-54.jpg] что [img: http://localhost:8080/file/021020-55.jpg] Если А= {а, а2,...} и [img: http://localhost:8080/file/021020-56.jpg] = {В 1, В 2,...} - конечные множества, то удобно описывать свойства И. с. 5 с помощью матрицы инцидентности ||aij||, где aij=1, когда [img: http://localhost:8080/file/021020-57.jpg] и aij=0 - в противном случае; матрица ||aij|| определяет И. с. Sс точностью до изоморфизма.