E-catalog        

Библиогр.: 15 назв.

Ищется медиана для нечётного числа отношений линейного порядка, заданных на конечном множестве A, также являющаяся линейным порядком на A. К подобной задаче приходим при исследовании некоторых задач группового выбора. В рассматриваемом случае бинарное отношение p, имеющее минимальное суммарное расстояние (по Хеммингу) до заданного набора бинарных отношений, является медианой для этих отношений, и притом единственной. Однако эта медиана не всегда является линейным порядком (или даже квазипорядком) и в этих случаях не может быть взята в качестве решения поставленной задачи. Тем не менее бинарное отношение p обязательно принадлежит множеству LA[n] (линейных асимметричных бинарных отношений на A), которому, в частности, принадлежат и все линейные порядки на A. Исследуются некоторые свойства бинарных отношений из LA[n]. Рассматривается отношение эквивалентности на множестве LA[n], позволяющее разбивать это множество на классы эквивалентности, количество которых Kn намного меньше числа элементов в LA[n]. Например, jLA[5]j = 1024, K5 = 12. Таким образом, каждое бинарное отношение из LA[n] эквивалентно в точности одному из Kn представителей классов эквивалентности, а следовательно, обладает его основными свойствами. Но тогда исследование широкого класса задач может быть сведено к рассмотрению сравнительно небольшого их набора. Процесс нахождения указанного набора представителей классов эквивалентности иллюстрируется для n = 2; 3; 4; 5. Приводится также метод решения поставленной задачи, использующий представление бинарных отношений в виде графов (метод выделения минимальных множеств представителей контуров в медиане p), имеющий экспоненциальную вычислительную сложность.